Alpha-Beta Pruning

Alpha-beta pruning is an optimization of minimax search that skips branches of a game tree once it is certain they cannot change the final decision, so that it returns exactly the move and value plain minimax would, while examining far fewer positions. It works by carrying two bounds down the search, alpha (the best score the maximizing player can already guarantee) and beta (the best score the minimizing player can already guarantee), and abandoning a position as soon as the two bounds cross.

The idea is usually traced to John McCarthy, who has said he conceived it around the time of the 1956 Dartmouth summer project, and its first appearance in a working chess program is credited to Allen Newell, Cliff Shaw and Herbert Simon. Their paper Chess-Playing Programs and the Problem of Complexity (IBM Journal of Research and Development, 1958) described a program that used a cutoff of this kind, and Arthur Samuel's checkers work of the same period used related pruning. The attribution is genuinely tangled: other researchers, among them Daniel Edwards and Timothy Hart at MIT, who described a tree-pruning procedure in 1961, and the Soviet researcher Alexander Brudno, who published a version in 1963, arrived at the same logic independently. The scheme was in use long before anyone gave it a rigorous analysis, which is a recurring pattern in early artificial intelligence.

The rigorous analysis came in 1975, when Donald Knuth and Ronald Moore published An Analysis of Alpha-Beta Pruning in the journal Artificial Intelligence, proving the algorithm correct and working out how much work it saves. The mechanism is simple to state. At a Min node, once some reply has produced a score no better for Max than a value Max could already secure elsewhere, there is no reason to look at the remaining replies, because Max would never steer play into this branch. The mirror-image cutoff happens at Max nodes. In the example below, after Max has found that move A is worth 3, the search of move B stops as soon as Min shows a reply worth 2, and the second reply to B is never evaluated at all.

The headline result is that with ideal move ordering, alpha-beta examines about the square root of the positions plain minimax would, so in the same time a program can search roughly twice as deep. Writing the leaf count of minimax as b to the power d for branching factor b and depth d, the best case is on the order of b to the power d/2, which is why the effective branching factor of a well-tuned search drops toward the square root of the raw one. In the worst case, where the best reply is always tried last, nothing is pruned and the cost matches minimax. Everything therefore depends on trying likely-best moves first, and chess engines invest heavily in move ordering: captures ordered by value, the killer heuristic (a quiet move that caused a cutoff in a sibling position), a history table, transposition-table moves, and iterative deepening, in which the best move from a shallow search seeds the ordering of a deeper one.

A frequent misconception is that alpha-beta is an approximation or a heuristic that sacrifices accuracy for speed; it is not, since it provably returns the same value and a best move as full minimax over the same tree to the same depth. The approximations in real engines come from different places: depth limits, evaluation functions, and unsound extras such as late-move reductions and null-move pruning that deliberately risk missing a rare tactic. A second pitfall is thinking pruning needs a probabilistic argument; its cutoffs are pure logic about bounds. Refinements such as aspiration windows, principal variation search (NegaScout) and MTD(f) narrow the bounds further, and the technique remains the core of top engines such as Stockfish, even as neural-network evaluations and Monte Carlo tree search have taken over in games with very wide trees like Go.

Read alpha-beta pruning as minimax with a conscience about wasted effort: a bookkeeping device that proves, branch by branch, that a line cannot matter, and so turns a hopeless exponential search into one that, given good move ordering, reaches about twice as far.