Textbook of AI

Also known as: α-β pruning

Alpha–beta search (also written α-β) is the standard pruning technique for minimax search in two-player zero-sum games. Plain minimax explores the entire game tree to a fixed depth and backs up values; alpha–beta keeps two bounds α (the best score the maximising player can already guarantee) and β (the best the minimiser can guarantee) and prunes any branch in which the current node's value is provably worse than the bound, since neither player would choose to enter it.

Alpha–beta pruning was discovered independently several times in the late 1950s and early 1960s by John McCarthy, Allen Newell, Herbert Simon, Cliff Shaw, Alexander Brudno (in the Soviet Union), Donald Knuth and others. It is provably as good as minimax, it returns the same value , and on average, with a good move ordering, reduces the effective branching factor from b to roughly √b, so a fixed time budget reaches roughly twice the depth of plain minimax.

For the next half-century, alpha–beta with progressively more sophisticated move-ordering heuristics, transposition tables, iterative deepening, quiescence search and pruning extensions (null-move pruning, late-move reductions) drove every strong chess program, culminating in Deep Blue's 1997 victory over Kasparov. Monte Carlo tree search (MCTS) and learned policy/value networks (AlphaGo, AlphaZero) have since displaced alpha–beta in games with very high branching factors like Go, but alpha–beta remains the technique of choice in chess and similar games.