Minimax Search
Motivation
Minimax search is the direct algorithmic realization of the minimax value on a game tree: a depth-first traversal that returns the value each player can guarantee under optimal play (Russell and Norvig 2020). It is the foundation of classical game-playing programs and the conceptual baseline against which all adversarial search algorithms — including alpha-beta search, expectimax, and Monte Carlo tree search — are compared.
Problem
A two-player zero-sum game with perfect information consists of:
- A set of states \(S\), with an initial state \(s_0\).
- A function \(\text{Player}(s) \in \{\text{MAX}, \text{MIN}\}\) identifying whose turn it is.
- A function \(\text{Actions}(s)\) giving legal moves and \(\text{Result}(s, a)\) giving the resulting state.
- A terminal test \(\text{Terminal}(s)\) and utility \(u(s)\) for terminal states.
MAX wants \(u\) large; MIN wants \(u\) small. The task is to return the optimal action at \(s_0\) assuming both players play optimally thereafter.
Key Ideas
The defining recursion is I move best assuming you respond best. At a MAX node, I get to pick — so the value is the maximum over my moves. At a MIN node, the opponent gets to pick — so the value is the minimum over their moves, since they will choose the move that hurts me most. Alternating max and min plies down the tree captures exactly the worst-case-against-optimal-opponent guarantee.
This worst-case framing is the load-bearing assumption. Minimax does not model an opponent who is weak, predictable, or stochastic — it assumes adversarial perfection. The value it returns is the guarantee under that assumption, and the move it picks is the one that protects against the worst response the opponent could make.
The recursion is also pure depth-first: each subtree returns a single scalar to its parent, and the recursion uses \(O(bd)\) stack space rather than the \(O(b^d)\) that storing the whole tree would require.
Algorithm
function MINIMAX(s):
if Terminal(s): return u(s)
if Player(s) == MAX:
return max over a in Actions(s) of MINIMAX(Result(s, a))
else:
return min over a in Actions(s) of MINIMAX(Result(s, a))To recover the move, the root call records which action achieved the optimal value:
function MINIMAX-DECISION(s):
return argmax over a in Actions(s) of MINIMAX(Result(s, a))This is a textbook recursive depth-first search; the only adversarial content is alternating max and min at successive plies.
Walkthrough
A two-ply tree
A depth-2 game tree with branching factor 3. Leaves are utilities (positive favors MAX). The MIN nodes pick the smallest leaf in their subtree; MAX at the root picks the largest of those. The optimal move is highlighted.
Each MIN child computes its own minimum: \(B = \min(3, 12, 8) = 3\), \(C = \min(7, 4, 5) = 4\), \(D = \min(6, 2, 9) = 2\). The root then takes the max of those: \(\max(3, 4, 2) = 4\). The optimal move is to \(C\), leading to the leaf with utility \(4\) — note that MAX does not steer toward leaf \(9\) (under \(D\)) or \(12\) (under \(B\)), because MIN would not allow those leaves to be reached.
Correctness
By induction on tree depth, MINIMAX\((s)\) returns the minimax value \(V(s)\). Base case: terminal \(u(s) = V(s)\). Step: the recursion mirrors the defining equation
\[ V(s) = \begin{cases} \max_a V(\text{Result}(s, a)) & \text{MAX,} \\ \min_a V(\text{Result}(s, a)) & \text{MIN,} \end{cases} \]
so the value returned is exactly \(V(s)\).
Complexity and Tradeoffs
Let \(b\) be the branching factor and \(d\) the depth of the tree. The full search visits every leaf, so the time complexity is \(O(b^d)\) and the space complexity is \(O(bd)\) (one stack frame per ply, each remembering \(b\) children to examine).
This is intractable for nontrivial games: chess has \(b \approx 35\) and the typical depth is far beyond what can be searched fully. Practical play depends on three modifications, all of which preserve the algorithm’s structure.
Depth-limited search and evaluation functions
When the tree cannot be searched to terminals, replace the terminal test with a depth cutoff and the utility with a heuristic evaluation function \(\hat{V}(s)\):
function MINIMAX(s, depth):
if Terminal(s) or depth == 0: return EVAL(s)
...\(\hat{V}(s)\) estimates the minimax value of \(s\) — for chess, a weighted sum of material, mobility, king safety, pawn structure, etc. Once the depth is large enough, the quality of play depends much more on \(\hat{V}\) than on the search itself; a deep search with a poor evaluator plays worse than a shallow search with a good one.
The horizon effect
A depth-limited search may misjudge positions where a decisive event lies just beyond the cutoff: capturing a queen at depth \(d+1\) is invisible to a search of depth \(d\). This horizon effect motivates quiescence search — extending the search past the cutoff at “noisy” positions (captures, checks, threats) until the position is quiet enough that a static evaluation is meaningful.
Move ordering and pruning
A pure minimax must examine every node at depth \(\le d\), but most of those nodes are irrelevant: once one branch refutes a candidate move, the others contribute nothing. Alpha-beta search detects this case and prunes, reducing the effective branching factor from \(b\) to \(\sqrt{b}\) when moves are ordered well — and ordering moves well is itself a major engineering concern in game-playing programs.
When to Use It
| Situation | Use minimax? |
|---|---|
| Small game tree, search to terminals feasible | Yes — exact, simple, and the right baseline. |
| Large tree, evaluation function available | Use depth-limited minimax + alpha-beta + quiescence; iterative deepening for time control. |
| Stochastic game (dice, chance nodes) | Use expectimax — replace MIN with expectation. |
| Massive branching factor, no good evaluator (e.g., Go) | Prefer Monte Carlo tree search. |
| Imperfect information (poker, hidden state) | Not directly applicable — minimax assumes perfect information. |
Variants
- Negamax. Replaces the alternating max/min with a single recursion that negates the value at each level, exploiting \(\min(x, y) = -\max(-x, -y)\). Equivalent to minimax but cleaner to implement.
- Expectimax. Replaces MIN nodes with chance nodes that take an expectation, used for games with stochastic elements (backgammon, dice rolls).
- Iterative deepening minimax. Runs minimax to depth \(1, 2, 3, \ldots\) until time runs out, using each iteration’s results to order moves in the next. The default control structure for tournament chess engines.