Alpha-Beta Algorithm

Alpha-beta pruning is a technique that optimizes the Minimax game-tree search algorithm: it reduces the number of positions that must be evaluated without changing the move Minimax would choose. It applies to two-player, zero-sum, perfect-information adversarial games, such as chess or checkers.

The idea took shape in the 1950s: John McCarthy recalled proposing the alpha-beta heuristic, but he also acknowledged that Arthur Samuel and the Newell-Simon team used independent versions and that no single authorship could be established. An early public discussion appeared in 1958 in Allen Newell, J. C. Shaw and Herbert Simon's work on chess-playing programs and complexity.

How it works

The algorithm keeps two values while traversing the tree: alpha, the best score already guaranteed for the maximizing player, and beta, the best for the minimizing one. When at a node it is discovered that it can no longer improve the already-secured decision—that is, when beta is less than or equal to alpha—that branch is “pruned” and no longer explored, because none of its descendants can alter the final choice. In a sentence: a move is abandoned as soon as it is proven worse than another already examined.

How much it saves

Pruning does not change the result, only the cost, and that cost depends on the order in which moves are examined. With optimal ordering, the effective branching factor is reduced to its square root, which allows searching about twice as deep with the same compute. With a random order the improvement is real but smaller, which is why engines invest in ordering moves well.