Alpha–Beta Pruning in Depth
Move ordering and the √ speedup in the best case.
Alpha–beta's best case is a square root: a perfectly ordered search to depth costs about as much as minimax to depth . Its worst case saves nothing. Between them lies a precise theory, from Knuth and Moore's minimal tree to Pearl's golden-ratio branching factor, and the engineering that pushes real engines toward the best case.
What you’ll learn
- State the fail-soft invariant of alpha–beta in negamax form, and use null windows to test bounds on the value.
- Prove that certifying a minimax value requires at least leaves, and that perfectly ordered alpha–beta examines exactly that many.
- State Pearl's theorem for random trees, derive properties of its branching factor , and compare it with , and .
- Explain how iterative deepening, transposition tables, move-ordering heuristics, PVS and MTD(f) bring practical search close to the minimal tree.
Negamax, fail-soft and null windows
In the negamax form of minimax, every value is taken from the point of view of the player to move, so one rule serves both players, , and the window flips sign as it passes down. The fail-soft version of alpha–beta returns the best value it found even when that value falls outside the window.
function NEGAMAX-AB(s, depth, α, β): # value for the player to move; fail-soft
if depth = 0 or TERMINAL(s): return EVAL(s)
v ← −∞
for each child c of s, most promising first:
v ← max(v, −NEGAMAX-AB(c, depth − 1, −β, −α))
if v ≥ β: return v # cutoff: the opponent avoids s
α ← max(α, v)
return vA null window , for integer values, leaves no room for an exact answer: the search must fail low () or fail high (). It answers the Boolean question "is ?", and because every cutoff test is as tight as possible, it examines far fewer leaves than a full-window search. Scout (Pearl, 1980), principal variation search (PVS, also called NegaScout; Reinefeld, 1983) and MTD(f) (Plaat et al., 1996) assemble exact searches out of such tests.
A fail-soft null-window search with (window , integer values) returns 7. What do you now know about the true value ?
- , and nothing more
Show the answer
D.
The search failed low, so the fail-soft invariant gives . A fail-hard implementation, which clamps results to the window, would report only ; the sharper bound is one reason MTD(f) and aspiration searches use fail-soft.
The minimal tree
Certificates are necessary. Suppose the examined leaves determine the value . If every MAX strategy had a leaf outside or a leaf below , an adversary could set the unexamined leaves to and push the value below . So contains a whole MAX strategy with all leaves and, symmetrically, a whole MIN strategy with all leaves :
Counting. A MAX strategy branches fully at the MIN levels, a MIN strategy at the MAX levels, and the two share exactly one leaf, at the end of the unique path that follows at MAX nodes and at MIN nodes:
Alpha–beta attains it. Under perfect ordering the searched nodes fall into Knuth and Moore's three types. Type 1 nodes (the principal variation) search all children: the first is type 1, the rest type 2. A type 2 node is refuted by its first child, which is type 3. A type 3 node searches all children, each of type 2:
Following the types down, the searched nodes form one MAX strategy and one MIN strategy that share only the principal variation: type 2 nodes are where the player to move shows a single refutation, and type 3 nodes are where every reply of the other player is answered. Their union has exactly the bound's number of leaves:
A uniform tree has and , so 81 leaves. How many of them does perfectly ordered alpha–beta examine?
Show the answer
17
. A MAX strategy (one move at MAX nodes, all moves at MIN nodes) has leaves, a MIN strategy also 9, and they share one.
Random trees: Pearl's branching factor
From we get , which gives the branching factor a compact form:
For , , and is the golden ratio, between (perfect ordering) and (no pruning):
For large , put . Then gives , so , and random ordering prunes only a logarithmic factor per level. Knuth and Moore had already found this order of growth for a simplified alpha–beta without deep cutoffs:
| perfect order: | random order: | no pruning: | ||
|---|---|---|---|---|
| 2 | 1.41 | 1.62 | 1.68 | 2 |
| 3 | 1.73 | 2.15 | 2.28 | 3 |
| 10 | 3.16 | 5.06 | 5.62 | 10 |
| 35 | 5.92 | 12.8 | 14.4 | 35 |
| 1000 | 31.6 | 190 | 178 | 1000 |
Engineering toward the minimal tree
Real engines approach the best case by making the first move tried at each node very likely to be the best one:
- Iterative deepening with a transposition table. Each iteration stores the best move of every position in a hash table, and the next, deeper iteration tries that hash move first. The table also merges transpositions, positions reached by different move orders.
- Move-ordering heuristics. Captures are ordered by most valuable victim and least valuable attacker; killer moves that caused cutoffs at the same depth in sibling positions come next; the history heuristic (Schaeffer, 1989) credits moves that caused cutoffs anywhere in the tree.
- Narrow windows. Aspiration windows center the root search on the previous iteration's value. PVS searches the first move with the full window and the rest with null windows, re-searching only after a fail high. MTD(f) uses null-window searches alone, with a transposition table; Plaat et al. (1996) showed that it reformulates Stockman's best-first SSS* (1979), long thought impractical because of its memory.
- Unsafe forward pruning. Null-move pruning and late-move reductions search apparently poor moves to reduced depth. They give up the guarantee of the exact depth- value, but buy much deeper search in practice.
Key takeaways
- Fail-soft alpha–beta returns exact values inside the window and bounds outside it; a null window turns it into a cheap test of .
- Certifying a minimax value takes a MAX strategy and a MIN strategy, hence at least leaves, and perfectly ordered alpha–beta examines exactly these (Knuth & Moore, 1975).
- On random trees alpha–beta's branching factor is : the golden ratio for , close to for moderate , like for large , and optimal among directional algorithms (Pearl, 1982).
- Engines approach the minimal tree with iterative deepening, transposition tables, killer and history heuristics and PVS or MTD(f), and buy further depth with unsafe forward pruning.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why does the minimal tree have leaves?
- It is the union of one MAX strategy and one MIN strategy, which share exactly one leaf
- Alpha–beta must examine every leaf once and half of them twice
- Every node of the tree has children searched
- It counts the leaves of the principal variation at every depth
Show the answer
A. It is the union of one MAX strategy and one MIN strategy, which share exactly one leaf
Proving needs a MAX strategy ( leaves) and proving a MIN strategy ( leaves). Their intersection is the single leaf where the two strategies' paths meet.
What is alpha–beta's asymptotic branching factor on random binary trees () with i.i.d. continuous leaf values?
Show the answer
D.
solves , so and . The rule of thumb is close, but not exact.
In principal variation search, a null-window search of a later move fails high. What does PVS do?
- It discards the move, since null-window results are unreliable
- It re-searches the move with a wider window, because it may beat the current best
- It stops the whole search and plays that move
- It lowers and continues with the next move
Show the answer
B. It re-searches the move with a wider window, because it may beat the current best
The null window established only that the move scores at least the current best value. To learn its exact value, and whether it becomes the new principal variation, PVS searches it again with a wider window. With good ordering this is rare, so the many cheap null-window searches dominate the cost.
How does MTD(f) compute an exact minimax value?
- With one full-window alpha–beta search
- By Monte Carlo sampling of the leaves
- With a sequence of null-window searches and a transposition table, moving bounds until they meet
- By searching the tree breadth-first
Show the answer
C. With a sequence of null-window searches and a transposition table, moving bounds until they meet
Each null-window search moves an upper or a lower bound; the transposition table keeps the work of earlier passes, so later passes are cheap. Plaat et al. (1996) showed that this reformulates SSS*, a best-first algorithm.
Further reading
- D. E. Knuth & R. W. Moore, "An analysis of alpha-beta pruning," Artificial Intelligence 6(4) (1975), 293–326.
- J. Pearl, "The solution for the branching factor of the alpha-beta pruning algorithm and its optimality," Communications of the ACM 25(8) (1982), 559–564.
- A. Plaat, J. Schaeffer, W. Pijls & A. de Bruin, "Best-first fixed-depth minimax algorithms," Artificial Intelligence 87 (1996), 255–293.
- J. Schaeffer, "The history heuristic and alpha-beta search enhancements in practice," IEEE Transactions on Pattern Analysis and Machine Intelligence 11(11) (1989), 1203–1212.
- M. Campbell, A. J. Hoane Jr. & F.-h. Hsu, "Deep Blue," Artificial Intelligence 134 (2002), 57–83.