Game-playing AI: minimax
Play an unbeatable tic-tac-toe AI, peek at how it scores every move, and see how alpha-beta pruning skips most of the work.
- Explain how minimax picks a move by assuming the opponent plays perfectly
- Describe a game tree and why it explodes in size
- Explain what alpha-beta pruning saves and why real game engines also need evaluation functions
In 1997 IBM’s Deep Blue beat world chess champion Garry Kasparov. In 2016 DeepMind’s AlphaGo beat Go champion Lee Sedol. Both stand on an idea from the 1920s-1950s: minimax.
Games like tic-tac-toe and chess are search problems with a twist - there’s an opponent who wants the opposite of what you want. Minimax handles that by assuming the opponent is perfect:
- MAX (you) picks the move with the highest score.
- MIN (the opponent) picks the move with the lowest score.
- At the end of the game, the score is simple: +1 for a win, 0 for a draw, −1 for a loss.
Start at the finished games at the bottom of the game tree and pass scores upward, level by level. The value at the top is the best result you can guarantee, whatever the opponent does.
1def minimax(node, maximizing):
2 if isinstance(node, int): # a leaf: the final score of a game
3 return node
4 values = [minimax(child, not maximizing) for child in node]
5 return max(values) if maximizing else min(values)
6
7# You (MAX) pick a branch, then your opponent (MIN) picks a leaf.
8tree = [[3, 12, 8], [2, 4, 6], [14, 5, 2]]
9for move, branch in enumerate(tree):
10 print("move", move, "is worth", minimax(branch, False))
11print("best you can guarantee:", minimax(tree, True))move 0 is worth 3 move 1 is worth 2 move 2 is worth 2 best you can guarantee: 3
Notice that move 2 contains the juiciest leaf (14), but a perfect opponent would never let you have it - they’d answer with 2. Minimax is pessimistic on purpose: it plays for the best guaranteed outcome, not the best hoped-for one.
Try it
Can you beat minimax?
You are X. Turn on Peek at minimax to see what the AI sees: every empty square is labelled with the result of perfect play if you move there. Try to win (spoiler: you can’t), then try to lose on purpose and watch how fast the labels turn red. The bar chart shows how many positions the AI examined for its move, with and without alpha-beta pruning.
Your move - you are X.
Positions the AI examined for its last move
Make a move and the AI will show its homework. From an empty board, plain minimax checks 549,946 positions!
The game tree explosion
1LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6),
2 (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
3
4def winner(board):
5 for a, b, c in LINES:
6 if board[a] != " " and board[a] == board[b] == board[c]:
7 return board[a]
8 return None
9
10def count_games(board, player):
11 if winner(board) or " " not in board:
12 return 1 # the game is over: one finished game
13 total = 0
14 for square in range(9):
15 if board[square] == " ":
16 child = board[:square] + player + board[square + 1:]
17 total += count_games(child, "O" if player == "X" else "X")
18 return total
19
20print(count_games(" " * 9, "X"), "different games of tic-tac-toe")255168 different games of tic-tac-toe
A quarter of a million games - for a 3×3 grid! Chess has an estimated possible games (the Shannon number), far more than the roughly atoms in the observable universe. No computer will ever search all of it. Two tricks make game AI possible anyway:
- Alpha-beta pruning - stop exploring a branch as soon as you can prove it won’t change the decision. In the tree above, once move 1 reveals a leaf worth 2, it can never beat the 3 you already have, so its other leaves (4 and 6) are skipped. Same answer, much less work - in tic-tac-toe, about 96% less.
- Evaluation functions - search only a few moves ahead, then estimate how good the position is (in chess: material, king safety, mobility…). Deep Blue searched around 200 million positions per second this way.
Key takeaways
Minimax: MAX picks the highest score, MIN the lowest; scores flow up from finished games to the current move.
It assumes a perfect opponent, so the result is the best outcome you can guarantee.
Game trees explode: 255,168 tic-tac-toe games, about chess games.
Alpha-beta pruning skips branches that can’t change the decision; evaluation functions let engines stop early and estimate.
Lesson quiz
7 questions · pass with 5 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: write Python
Write Python in the editor and run it against sample inputs. Python runs locally in your browser using a WebAssembly runtime.
Referee a tic-tac-toe board
The input is three lines of three characters: X, O or . for an empty square. Print X wins, O wins, draw (the board is full with no winner) or game on (no winner yet and empty squares remain).
- Top row
- Full board
- Diagonal
- Still playing
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Minimax on any tree
The input is one line: a game tree written as nested Python lists of integers, like [[3, 12, 8], [2, 4, 6], [14, 5, 2]]. You are MAX and choose among the top-level children; the levels below alternate MIN, MAX, MIN… Plain integers are final scores.
Print value: V (the minimax value) and best move: I (the index of the first top-level child with that value).
- The lesson tree
- Two branches
- Three levels
- Last move wins
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…