AI: The best tic-tac-toe move

Use minimax to play tic-tac-toe perfectly.

What to build

A program that finds the best move in a tic-tac-toe position and the result with perfect play.

Requirements

  • The player to move is X if both have made the same number of moves, otherwise O. With perfect play from both sides, find the value of each move; the best move for X has the largest value, for O the smallest. If several moves are equally good, choose the first in reading order (row by row, left to right).
  • Print best move R C (row and column from 1), then X wins, O wins or draw.

Input

Three lines of three characters: X, O or ..

Output

Two lines.

Constraints

The game is not over yet.

Example

Input:

XX.
OO.
...

Output:

best move 1 3
X wins

Why it works

Minimax assumes both players choose perfectly at every turn, so its value is the result neither side can improve on alone.

Examples

Example 1 · Input
XX.
OO.
...
Expected output
best move 1 3
X wins
Example 2 · Input
XX.
O..
X.O
Expected output
best move 1 3
draw

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

X moves first, so X is to move when the counts of X and O are equal.

Hint 2

Score finished boards +1 (X wins), −1 (O wins) or 0, and run minimax over every empty square.

Solution

Show one correct solution (try it yourself first)
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
board = list("".join(input().strip() for _ in range(3)))
player = "X" if board.count("X") == board.count("O") else "O"


def winner(b):
    for a, c, d in LINES:
        if b[a] != "." and b[a] == b[c] == b[d]:
            return b[a]
    return None


def minimax(b, turn):
    won = winner(b)
    if won:
        return 1 if won == "X" else -1
    if "." not in b:
        return 0
    values = []
    for i in range(9):
        if b[i] == ".":
            b[i] = turn
            values.append(minimax(b, "O" if turn == "X" else "X"))
            b[i] = "."
    return max(values) if turn == "X" else min(values)


best_move, best_value = None, None
for i in range(9):
    if board[i] == ".":
        board[i] = player
        v = minimax(board, "O" if player == "X" else "X")
        board[i] = "."
        if best_value is None or (v > best_value if player == "X" else v < best_value):
            best_move, best_value = i, v
print(f"best move {best_move // 3 + 1} {best_move % 3 + 1}")
print({1: "X wins", -1: "O wins", 0: "draw"}[best_value])

Lesson: Game playing with minimax →