Game Trees and Minimax
Postorder With an Adversary
You already know postorder traversal: go to the leaves, compute values, pull them up to the root. Minimax is exactly that — with one twist. Instead of always combining with the same function (like max(left, right) for height, or left + right for sum), you alternate between max and min at each level.
That's it. Adversarial search is postorder traversal on a game tree where the combine function alternates between max and min.
The Game Tree
Two players take turns. Player A wants to maximize the score. Player B wants to minimize it. At each turn, the current player picks one of several moves, each leading to a new game state. The game eventually ends at terminal states with known scores.
Draw this as a tree: - Root: the current game state (Player A's turn). - Children of any node: the game states reachable by making one move. - Leaves: terminal states with scores. - Odd levels (from root): Player A chooses (maximizing). - Even levels: Player B chooses (minimizing).
Consider this game tree with 8 terminal values:
The leaves have scores: \([3, 5, 2, 9, 12, 5, 23, 2]\).
The Algorithm: Pull Values Up
Start at the leaves. They have fixed scores. Then work upward:
- At a MAX node: pick the child with the higher value. (The maximizing player will always choose the best option.)
- At a MIN node: pick the child with the lower value. (The minimizing player will always choose the worst option for you.)
This is postorder. You can't compute a node's value until both children are resolved.
Full Trace
| Level | Nodes | Operation | Values |
|---|---|---|---|
| 3 (leaves) | \(L_0..L_7\) | terminal | \(3, 5, 2, 9, 12, 5, 23, 2\) |
| 2 (MAX) | \(N_0\) = max(3,5), \(N_1\) = max(2,9), \(N_2\) = max(12,5), \(N_3\) = max(23,2) | max of children | \(5, 9, 12, 23\) |
| 1 (MIN) | \(N_4\) = min(5,9), \(N_5\) = min(12,23) | min of children | \(5, 12\) |
| 0 (MAX) | root = max(5,12) | max of children | 12 |
The optimal value for the maximizing player is 12.
What does this mean? If both players play perfectly, the maximizing player guarantees a score of at least 12, and the minimizing player guarantees the score is at most 12. The game's outcome is determined before a single move is made.
Manual verification from the maximizing player's perspective: - At root (MAX), player A goes right (toward the subtree with value 12). - At level 1 (MIN), player B goes left (toward 12 instead of 23 — B wants to minimize). - At level 2 (MAX), player A picks 12 (between 12 and 5). - Score: 12. Confirmed.
Tic-Tac-Toe: A Real Game
The abstract tree above is clean, but how does this work for an actual game? Take tic-tac-toe on a \(3 \times 3\) board.
The game tree's root is the empty board. X goes first (maximizing). Each node has as many children as there are empty cells. The tree branches explosively — up to 9 children at the root, 8 at level 1, and so on.
Terminal states score: \(+1\) if X wins, \(-1\) if O wins, \(0\) for a draw.
The first three levels look something like this (showing just one branch):
Level 0 (X plays): [empty board]
| | | ...
Level 1 (O plays): [X in center]
| | | ...
Level 2 (X plays): [X center, O corner]
| | | ...
At the deepest level, you evaluate who won. Then you pull values up — min at O's levels, max at X's levels. The root's value tells you the outcome with perfect play. (For tic-tac-toe, it's 0: a draw.)
The total tree has about \(9! = 362{,}880\) leaves. That's small enough to solve completely. Chess has roughly \(10^{44}\) leaves — far too many. That's where pruning comes in.
Alpha-Beta Pruning: Cutting Subtrees
You don't always need to explore every leaf. If you've already found that one branch guarantees the maximizing player a score of 12, and you start exploring another branch where the minimizing player can force the score down to 5, you can stop exploring that branch. The maximizing player will never choose it.
This is alpha-beta pruning. Two values travel top-down through the tree:
- \(\alpha\): the best score the maximizing player is guaranteed so far (starts at \(-\infty\)).
- \(\beta\): the best score the minimizing player is guaranteed so far (starts at \(+\infty\)).
At any node, if \(\beta \leq \alpha\), stop exploring. The current branch is irrelevant — one player already has a better option elsewhere.
The connection to backtracking: Alpha-beta pruning is the same idea as backtracking pruning from Lesson 3. In backtracking, you abandon a branch when you detect it can't lead to a valid solution. In alpha-beta, you abandon a branch when you detect it can't lead to a better outcome than what's already found. Both are "cutting subtrees" during a DFS.
Trace With Alpha-Beta
Same tree, same values: \([3, 5, 2, 9, 12, 5, 23, 2]\). Now with pruning.
| Node | Type | \(\alpha\) | \(\beta\) | Children explored | Value | Pruned? |
|---|---|---|---|---|---|---|
| Root | MAX | \(-\infty\) | \(+\infty\) | both | 12 | No |
| Left MIN | MIN | \(-\infty\) | \(+\infty\) | both | 5 | No |
| Left-Left MAX | MAX | \(-\infty\) | \(+\infty\) | leaf 3, leaf 5 | 5 | No |
| Left-Right MAX | MAX | \(-\infty\) | 5 | leaf 2, stop | 2 | Yes |
| Right MIN | MIN | 5 | \(+\infty\) | both | 12 | No |
| Right-Left MAX | MAX | 5 | \(+\infty\) | leaf 12, leaf 5 | 12 | No |
| Right-Right MAX | MAX | 5 | 12 | leaf 23, stop | 23 | Yes |
At "Left-Right MAX": after seeing leaf 2, the MAX node has value \(\geq 2\). But its parent (Left MIN) already has \(\beta = 5\) from the left sibling. Since we're at a MAX node and haven't exceeded \(\beta\) yet — actually, the MIN parent will take \(\min(5, \text{this node})\). Once this MAX node sees 2, it could go higher with the second child, but even if it does, the MIN parent picks \(\min(5, \text{something} \geq 2) \leq 5\). The root already has \(\alpha = -\infty\), so no pruning yet. Wait — let me re-trace carefully.
After Left MIN returns 5, the root (MAX) sets \(\alpha = 5\). Now exploring Right MIN with \(\alpha = 5\). Right-Left MAX returns 12. Right MIN updates: current best = 12, \(\beta\) stays \(+\infty\) — actually \(\beta = \min(+\infty, 12) = 12\). Now Right-Right MAX starts with \(\alpha = 5\), \(\beta = 12\). It sees leaf 23. Value = 23. \(\alpha = \max(5, 23) = 23\). Now \(\alpha = 23 > \beta = 12\). Prune. Skip second child.
Leaves visited: \(3, 5, 2, 9, 12, 5, 23\). Leaf 2 (the last one) was never evaluated. One leaf pruned out of 8. On larger trees, pruning can reduce the effective branching factor from \(b\) to \(\sqrt{b}\).
The Code
int minimax(vector<int>& leafValues, int nodeIndex, int depth, bool isMaximizing) {
if (depth == 0) return leafValues[nodeIndex];
int leftResult = minimax(leafValues, nodeIndex * 2, depth - 1, !isMaximizing);
int rightResult = minimax(leafValues, nodeIndex * 2 + 1, depth - 1, !isMaximizing);
if (isMaximizing) return max(leftResult, rightResult);
return min(leftResult, rightResult);
}
int minimaxAlphaBeta(vector<int>& leafValues, int nodeIndex, int depth,
bool isMaximizing, int alpha, int beta) {
if (depth == 0) return leafValues[nodeIndex];
if (isMaximizing) {
int bestValue = (int)-2e9;
for (int child = 0; child < 2; child++) {
int childValue = minimaxAlphaBeta(leafValues, nodeIndex * 2 + child,
depth - 1, false, alpha, beta);
bestValue = max(bestValue, childValue);
alpha = max(alpha, bestValue);
if (beta <= alpha) break;
}
return bestValue;
}
int bestValue = (int)2e9;
for (int child = 0; child < 2; child++) {
int childValue = minimaxAlphaBeta(leafValues, nodeIndex * 2 + child,
depth - 1, true, alpha, beta);
bestValue = min(bestValue, childValue);
beta = min(beta, bestValue);
if (beta <= alpha) break;
}
return bestValue;
}
Complexity: Minimax: \(O(b^d)\) where \(b\) is the branching factor and \(d\) is the depth. Alpha-beta: \(O(b^{d/2})\) in the best case (optimal move ordering), \(O(b^d)\) in the worst case.
The Mental Model
Strip away the game theory jargon and here's what's left:
- A game tree is a regular tree.
- Minimax is postorder traversal.
- The combine function alternates: \(\max\) at even depths, \(\min\) at odd depths.
- Alpha-beta pruning is cutting subtrees you know can't affect the answer — the same idea as backtracking.
Every "AI" in classic board games (chess engines before neural networks, tic-tac-toe solvers, connect-four bots) is built on this postorder traversal with alternating combine functions. The rest is engineering: better evaluation functions at non-terminal nodes, transposition tables to cache repeated states, iterative deepening to manage time.
Adversarial search is just postorder where the combine function alternates between max and min. Once you see it as a tree algorithm, the mystique disappears.
Try It
Predict before running: What if all leaf values are equal (say, all 7s)? Every min and max returns 7. The game is a guaranteed draw at score 7, regardless of moves.
Challenge: Modify the minimax to also return the move (left or right at the root) that the maximizing player should make. Not just the value — the actual decision.
Edge Cases to Watch For
- Immediate win at root: If the game is already over at the root (terminal state), minimax returns the terminal value immediately without recursing. Make sure your base case checks for terminal states before generating children — otherwise you'll recurse into an already-decided game.
- Odd vs even number of levels: The root's role (MAX or MIN) determines who "goes first." Swapping the starting player inverts the tree's value. Make sure
isMaximizingmatches the intended first player — getting this wrong silently inverts the result. - Alpha-beta with worst-case ordering: If leaves are ordered from worst to best for alpha-beta, no pruning occurs and performance equals vanilla minimax. Optimal ordering (best moves first) achieves \(O(b^{d/2})\) — move ordering logic is required for alpha-beta to actually help.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 486 --- Predict the Winner | leetcode.com/problems/predict-the-winner | Medium |
| LC 877 --- Stone Game | leetcode.com/problems/stone-game | Medium |
| LC 1140 --- Stone Game II | leetcode.com/problems/stone-game-ii | Medium |