Minimax and Alpha-Beta Pruning: How Computers Play Games

The Core Idea: Assume Your Opponent Plays Perfectly

Minimax models a two-player, zero-sum, perfect-information game as a tree. Nodes are positions; edges are legal moves; the two players alternate turns. One player (call them MAX) wants to maximize the final score; the other (MIN) wants to minimize it. Leaves carry a numeric value — either a true game outcome (+1 win, 0 draw, −1 loss) or, when the tree is too deep to reach the end, a heuristic evaluation of the position.

The algorithm's central assumption — and its defining invariant — is that each player plays optimally against the other. The value of a MAX node is the maximum over its children's values; the value of a MIN node is the minimum. Formally, for a node n:

minimax(n) =
   eval(n)                         if n is a leaf / cutoff
   max over c in children(n) of minimax(c)   if n is a MAX node
   min over c in children(n) of minimax(c)   if n is a MIN node

This is backward induction: Zermelo's 1913 theorem guarantees that in a finite, perfect-information zero-sum game this recursively-computed value is the game's optimal outcome under perfect play (von Neumann's 1928 minimax theorem is the companion result for simultaneous-move games with mixed strategies). The best move at the root is the child that achieves the root's minimax value. Crucially, minimax is pessimistic and safe: it never assumes the opponent blunders, so the move it picks guarantees at least the computed value regardless of what the opponent actually does.

How Minimax Runs Step by Step

Minimax is a depth-first traversal (see Depth-First Search) of the game tree that returns values up the recursion. There is no separate data structure to maintain — the implicit call stack is the frontier, giving O(d) auxiliary space for a tree of depth d.

• Descend from the root, generating children move-by-move until you hit a terminal position or a depth cutoff.
• Evaluate leaves. A terminal node returns the true result; a cutoff node returns eval(), a domain heuristic (in chess: material + mobility + king safety + pawn structure, tuned over decades).
• Fold values upward. A MAX node returns the max of its children's returned values; a MIN node returns the min. Track which child produced the extremum to recover the move.
• Return to the root, whose chosen child is the move to play.

A common simplification is negamax: since min(a, b) = −max(−a, −b) for zero-sum games, you can write a single routine that always maximizes and negates the value returned from the child. This halves the code and eliminates a whole class of sign bugs:

function negamax(node, depth, color):
  if depth == 0 or terminal(node):
    return color * eval(node)
  value = −∞
  for child in children(node):
    value = max(value, −negamax(child, depth−1, −color))
  return value

Alpha-Beta: Pruning Branches You Can Prove Are Irrelevant

Naive minimax visits every node. Alpha-beta pruning (co-discovered around 1958–1963; John McCarthy named it, and Knuth & Moore gave the definitive 1975 analysis) exploits a simple observation: once you know a move is worse than one you've already found, you don't need to know how much worse.

It carries two bounds down the recursion:

• α — the best (highest) value MAX can already guarantee somewhere along the current path.
• β — the best (lowest) value MIN can already guarantee.

The window [α, β] is the range of scores that can still influence the root. The invariant: within a call, the true node value only matters if it lies in (α, β). At a MAX node, whenever a child's value v ≥ β, MIN would never allow the game to reach this node (it already has a ≤β option elsewhere), so we cut off — a beta cutoff. Symmetrically at a MIN node, v ≤ α triggers an alpha cutoff.

function alphabeta(node, depth, α, β, maximizing):
  if depth == 0 or terminal(node):
    return eval(node)
  if maximizing:
    v = −∞
    for child in children(node):
      v = max(v, alphabeta(child, depth−1, α, β, false))
      α = max(α, v)
      if α ≥ β: break        // β cutoff — remaining siblings pruned
    return v
  else:
    v = +∞
    for child in children(node):
      v = min(v, alphabeta(child, depth−1, α, β, true))
      β = min(β, v)
      if β ≤ α: break        // α cutoff
    return v

The key correctness guarantee: alpha-beta returns exactly the same value as minimax for the root. Pruning only discards subtrees that provably cannot change the answer — it is an optimization, not an approximation.

Why the Complexity Drops from bᵈ to b^(d/2)

Naive minimax examines Θ(bᵈ) nodes for branching factor b and depth d — the game tree is b-ary and fully expanded. This is the same exponential wall as any brute-force Backtracking search.

Alpha-beta's savings depend entirely on move ordering. With optimal ordering — the best move examined first at every node — the analysis (Knuth & Moore, 1975) shows you must fully expand only one child at each node, and merely refute the rest with a single reply. The node count satisfies a recurrence whose solution is:

nodes ≈ b^⌈d/2⌉ + b^⌊d/2⌋ − 1  =  Θ(b^(d/2))

The effective branching factor collapses from b to √b. Concretely, chess averages b ≈ 35; √35 ≈ 5.9. In the same node budget that naive minimax spends reaching depth d, alpha-beta reaches depth 2d — a full doubling of search horizon, which is the difference between a club player and a grandmaster-strength engine.

• Best case (perfect ordering): Θ(b^(d/2)) — the target every real engine chases.
• Worst case (adversarial ordering): Θ(bᵈ) — no pruning at all; identical to naive minimax.
• Random ordering: roughly Θ(b^(3d/4)) — still a meaningful improvement.

Space is unchanged: O(bd) to hold the generated children along the active path, or O(d) if children are generated lazily. Pruning cuts time, not the stack depth.

Making It Fast in Practice: Ordering, Tables, and Deepening

Because alpha-beta's speed hinges on searching good moves first, real engines invest enormous effort in move ordering heuristics:

• Iterative deepening — search to depth 1, then 2, then 3… Each pass is cheap relative to the next (the geometric series sums to a small constant factor), and the best move from depth k becomes the first move tried at depth k+1. This alone gets ordering close to optimal. (See Iterative Deepening.)
• Transposition tables — a hash table (keyed by a Zobrist hash of the position) caches previously computed values and bounds. Since many move sequences reach the same position (a transposition), this is a form of memoization that overlaps with Dynamic Programming.
• Killer & history heuristics — moves that caused cutoffs elsewhere are tried early, since cutoff-causing moves tend to recur across sibling subtrees.
• Principal Variation Search (PVS / NegaScout) — after the first move, search remaining moves with a zero-width window (β = α+1) to cheaply prove they're worse; re-search fully only on the rare occasion the assumption fails.

Two more essentials: quiescence search extends the search past the depth limit through "noisy" moves (captures, checks) to avoid the horizon effect — stopping mid-exchange and misjudging the position. And aspiration windows start the root search with a narrow [α, β] around the previous score, re-searching wider only on a fail-high/fail-low.

Where It's Used — and Where It Breaks Down

Alpha-beta minimax powered essentially every strong classical engine: Deep Blue (chess, 1997), Chinook (checkers — solved to a draw in 2007 by Schaeffer using alpha-beta plus endgame databases), and open-source engines like Stockfish, which still uses alpha-beta as its search backbone (with an NNUE neural evaluation replacing the hand-tuned heuristic since 2020).

Its assumptions define its limits:

• Two players, zero-sum, perfect information. Minimax needs a single adversary and no hidden state or chance. Poker (hidden cards) and backgammon (dice) violate this; the latter needs expectiminimax, which adds averaging chance nodes and largely destroys pruning.
• Large branching factor. Go has b ≈ 250 and long games — even √b search is hopeless, and no simple evaluation exists. This is exactly why AlphaGo used Monte Carlo Tree Search guided by neural networks instead of alpha-beta.
• A trustworthy evaluation function. Below the cutoff depth the whole edifice rests on eval(). A bad heuristic makes deep search confidently wrong.

The rule of thumb: alpha-beta wins when the branching factor is modest and you have a decent evaluation function (chess, checkers, Othello, Connect Four). MCTS wins when b is huge and evaluation is hard.

Pitfalls, Edge Cases, and Variants

Even a textbook-correct alpha-beta implementation hides subtle traps:

• Initialize the window correctly. The root call must use α = −∞, β = +∞. Starting with a tight window prunes legitimate lines and returns a wrong value.
• Fail-soft vs. fail-hard. The classic ("fail-hard") version clamps returns into [α, β]. "Fail-soft" returns the actual best value found even outside the window, giving transposition tables tighter bounds — but you must store whether a stored score is an exact value, a lower bound (β cutoff), or an upper bound (α cutoff), or the table corrupts later searches.
• Sign errors in negamax. Forgetting to negate the child's return, or the α/β swap-and-negate when recursing, is the single most common bug — negamax exists precisely to minimize this surface.
• The horizon effect. Without quiescence search, the engine "pushes" bad news past its depth limit — e.g., delaying an unavoidable queen loss with checks until it falls off the horizon, then evaluating the position as fine.
• Non-determinism from equal scores. Ties among moves make the chosen move order-dependent; fix a tie-break for reproducibility.

Notable variants: SSS* and MTD(f) reformulate alpha-beta as a sequence of zero-window ("null-window") probes, often expanding fewer nodes than plain alpha-beta with good transposition support. Negascout/PVS is the practical standard. And for games decomposable into independent sub-games, the Sprague-Grundy theorem can replace search entirely with a nimber computation.

Naive minimax vs. alpha-beta vs. Monte Carlo Tree Search on a game tree with branching factor b, depth d.

Property	Naive Minimax	Alpha-Beta Pruning	MCTS
Nodes examined	Θ(bᵈ)	Θ(b^⌈d/2⌉) best order	sampled, anytime
Result exactness	Exact optimal value	Exact — identical to minimax	Statistical estimate
Depends on move order	No	Yes (huge constant factor)	Via selection policy
Space	O(bd)	O(bd)	O(nodes stored)
Needs eval function	Yes (at cutoff)	Yes (at cutoff)	No (uses rollouts)
Wins when	Tiny trees	Chess-like tactical trees	Huge b (Go), weak eval