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), thenX wins,O winsordraw.
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])