An oracle for noughts and crosses (tic-tac-toe) must announce the best move and what it leads to.
The board is a string of 9 characters, row by row, so the squares are numbered
0 1 2
3 4 5
6 7 8
Each character is "X", "O" or "." (empty). "X" always moves first, so the player to move is
"X" when both have the same number of marks and "O" otherwise. Three of one player's marks in a
row, column or diagonal win at once; a full board without such a line is a draw.
Assume that from now on both players play perfectly, with these priorities: win if possible,
otherwise draw, otherwise lose; among wins, win in as few moves as possible; among losses, lose as
late as possible. Return a tuple (square, result, moves):
square: the best square for the player to move. When several squares are equally good under these priorities, return the lowest number.result:"win","draw"or"loss"for the player to move.moves: how many marks will be placed from now until the game ends, including this move.
Examples
Input: board = "XX.OO...."
Output: (2, "win", 1)
Explanation: X completes the top row at once.
Input: board = "X...O...X"
Output: (1, "draw", 6)
Explanation: O must take an edge square; a corner loses to a double threat.
Squares 1, 3, 5 and 7 all draw, and 1 is the lowest.
Input: board = "........."
Output: (0, "draw", 9)
Constraints
boardis a position reachable in a real game: no one has won yet and at least one square is empty.
Goals
- Search a small game to the very end with memoised recursion
- Prefer quicker wins and slower losses by folding the game length into the score
- Break ties between equally good moves in a fixed, documented order