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.

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.

Where it is used

Alpha-beta pruning was for decades the basis of chess engines, combined with evaluation functions and depth cutoffs, since the full tree is unmanageable. In games with a huge branching factor, such as Go, it loses effectiveness, and there Monte Carlo tree search takes over, the approach popularized by AlphaGo.