Alpha-Beta Pruning Algorithm

Alpha-beta pruning is an algorithm that speeds up the minimax search used to choose a move in a two-player game such as chess by cutting off, or pruning, branches of the game tree that cannot change the final decision, letting the same computational budget search substantially deeper than plain minimax could. It tracks two bounds while it searches, alpha, the best score the maximizing player can already guarantee, and beta, the best score the minimizing player can already guarantee, and stops exploring any branch as soon as it proves that branch cannot produce a result the opposing player would ever allow to happen. The gain can be dramatic: a search examining four levels of a chess game tree with an average of thirty six legal moves per position would otherwise evaluate more than a million end positions, where a well-ordered alpha-beta search can cut that to roughly two thousand, a reduction of more than ninety nine percent. The technique's origin is genuinely disputed: John McCarthy proposed the underlying idea at the 1956 Dartmouth Workshop, Arthur Samuel built an early version into his checkers program, Alexander Brudno published results on it in 1963, and Donald Knuth and Ronald Moore gave it a rigorous treatment in 1975, after which Judea Pearl proved the technique's optimality among comparable pruning methods.