Introduction
Search so far assumed the agent controls every action. In a game, an opponent chooses half the moves, and wants the opposite result. A plan such as "move here, then there" is useless if the opponent can spoil it. Game-playing programs, from tic-tac-toe to chess engines, solve this with minimax: choose the move whose worst outcome is best.
How it works
A two-player, turn-taking, zero-sum game with perfect information is described by:
- the initial state and whose turn it is;
- the legal moves in each state;
- a terminal test: is the game over?
- a utility for terminal states, from the point of view of the first player, called MAX (in tic-tac-toe: +1 if X wins, −1 if O wins, 0 for a draw).
The positions form a game tree. The minimax value of a position is:
- its utility, if it is terminal;
- the largest value of its children, if MAX is to move;
- the smallest value of its children, if MIN is to move.
It is computed bottom-up by a recursive function: try each move, compute the value of the resulting position for the other player, undo the move, and take the max or min. The best move for MAX is a child with the largest value.
Minimax is optimal against a perfect opponent: MAX gets at least the minimax value whatever MIN does. Against a weaker opponent it is still safe, though it may not exploit the opponent's mistakes.
The cost is the size of the tree: about b^m positions for b moves per position and m moves per game. Tic-tac-toe has fewer than 550,000 positions in its full tree, so it can be searched completely; chess has about 10^40 legal positions, so engines search only a few plies ahead and replace the utility with an evaluation function that estimates how good a position is.
Syntax
def minimax(state, player):
if terminal(state): return utility(state)
values = [minimax(result(state, m), other(player)) for m in moves(state)]
return max(values) if player == MAX else min(values)
Example
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)]
searched = 0
def winner(board):
for a, b, c in LINES:
if board[a] != "." and board[a] == board[b] == board[c]:
return board[a]
return None
def minimax(board, player):
global searched
searched += 1
won = winner(board)
if won:
return 1 if won == "X" else -1
if "." not in board:
return 0
values = []
for i in range(9):
if board[i] == ".":
board[i] = player
values.append(minimax(board, "O" if player == "X" else "X"))
board[i] = "."
return max(values) if player == "X" else min(values)
board = list("X...O...X")
print("X . .\n. O .\n. . X\nO to move; +1 means X wins, 0 a draw, -1 O wins")
results = {}
for i in range(9):
if board[i] == ".":
board[i] = "O"
results[i] = minimax(board, "X")
board[i] = "."
print(f" O at row {i // 3 + 1}, column {i % 3 + 1}: {results[i]:>2}")
best = min(results, key=lambda i: (results[i], i))
print(f"best for O: row {best // 3 + 1}, column {best % 3 + 1}; positions searched: {searched}")Line by line
winnerchecks the eight lines;minimaxreturns +1, −1 or 0 for a finished board, and otherwise the max (X) or min (O) of its children.- The board has X in two opposite corners and O in the centre, with O to move.
- The loop tries each move for O and computes its minimax value with X to reply.
- Every corner loses for O (1, an X win): X takes another corner and threatens two lines at once, a fork. Every edge square leads to a draw (0).
- O's best move is the first edge square, and the whole analysis searched about a thousand positions.
Expected result
X . .
. O .
. . X
O to move; +1 means X wins, 0 a draw, -1 O wins
O at row 1, column 2: 0
O at row 1, column 3: 1
O at row 2, column 1: 0
O at row 2, column 3: 0
O at row 3, column 1: 1
O at row 3, column 2: 0
best for O: row 1, column 2; positions searched: 1052
In the real world
Chess engines such as Stockfish are built on minimax with alpha-beta pruning (the next lesson), searching tens of millions of positions per second. Checkers was completely solved by search in 2007: perfect play is a draw. The same idea appears outside games, in planning against an adversary such as worst-case security analysis.
Common mistakes
- Scoring positions from the point of view of the player to move at some levels and of MAX at others.
- Forgetting to undo a move after trying it, which corrupts the board.
- Not checking for a win before checking for a full board, so a winning last move counts as a draw.
- Picking the move with the best average instead of the best worst case.
Best practices
- Write the terminal test and utility first and test them on finished boards.
- Count the positions searched; it shows why pruning and depth limits are needed.
- Break ties between equally good moves in a fixed order, so results are reproducible.
Summary
Minimax handles an opponent by assuming they play perfectly: MAX takes the largest child value, MIN the smallest, and terminal positions are scored by their utility. It gives optimal play in small games such as tic-tac-toe; larger games need depth limits and evaluation functions.
Quick check
Key takeaways
- MAX picks the child with the largest value, MIN the child with the smallest.
- Minimax assumes the opponent plays perfectly, so it never relies on a mistake.
- Full game trees are enormous; real programs search a few plies and estimate.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.