Alpha–beta pruning is a tree search algorithm that seeks to decrease the number of nodes evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games such as Tic-tac-toe, Chess, and Connect 4. The algorithm stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move, so such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
The algorithm is a classic example of a branch-and-bound approach in Artificial intelligence, and it underpins many game-playing programs, including early chess computers and modern engines. Its efficiency gains allow deeper searches within the same computational budget, making it a foundational technique in adversarial search.
History
John McCarthy, during the Dartmouth Workshop in 1956, met Alex Bernstein of IBM, who was writing a chess program. McCarthy invented alpha–beta search and recommended it to Bernstein, but Bernstein was "unconvinced." Allen Newell and Herbert A. Simon, who used what McCarthy called an "approximation" in 1958, wrote that alpha–beta "appears to have been reinvented a number of times." Arthur Samuel had an early version for a checkers simulation. Richards, Timothy Hart, Michael Levin, and/or Daniel Edwards also invented alpha–beta independently in the United States. McCarthy proposed similar ideas during the Dartmouth workshop and suggested them to a group of his students, including Alan Kotok at MIT in 1961. Alexander Brudno independently conceived the alpha–beta algorithm, publishing his results in 1963. Donald Knuth and Ronald W. Moore refined the algorithm in 1975. Judea Pearl proved its optimality in terms of the expected running time for trees with randomly assigned leaf values in two papers. The optimality of the randomized version of alpha–beta was shown by Michael Saks and Avi Wigderson in 1986.
Core Idea
A game tree can represent many two-player zero-sum games, such as chess, checkers, and reversi. Each node in the tree represents a possible situation in the game. Each terminal node (outcome) of a branch is assigned a numeric score that determines the value of the outcome to the player with the next move.
The algorithm maintains two values, alpha and beta, which respectively represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of. Initially, alpha is negative infinity and beta is positive infinity, meaning both players start with their worst possible score. Whenever the maximum score that the minimizing player (the "beta" player) is assured of becomes less than the minimum score that the maximizing player (the "alpha" player) is assured of (i.e., beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in actual play.
To illustrate with a real-life example, suppose someone is playing chess, and it is their turn. Move "A" will improve the player's position. The player continues to look for moves to make sure a better one hasn't been missed. Move "B" is also a good move, but the player then realizes that it will allow the opponent to force checkmate in two moves. Thus, other outcomes from playing move B no longer need to be considered since the opponent can force a win. The maximum score that the opponent could force after move B is negative infinity: a loss for the player. This is less than the minimum position that was previously found; move A does not result in a forced loss in two moves.
Improvements Over Naive Minimax
The benefit of alpha–beta pruning lies in the fact that branches of the search tree can be eliminated. This way, the search time can be limited to the 'more promising' subtree, and a deeper search can be performed in the same time. Like its predecessor, it belongs to the branch and bound class of algorithms. The optimization reduces the effective depth to slightly more than half that of simple minimax if the nodes are evaluated in an optimal or near-optimal order (best choice for side on move ordered first at each node).
With an (average or constant) branching factor of b, and a search depth of d plies, the maximum number of leaf node positions evaluated (when the move ordering is pessimal) is O(b^d) - the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves are always searched first), the number of leaf node positions evaluated is about O(b 1 b 1 ... b) for odd depth and O(b 1 b 1 ... 1) for even depth, or O(b^(d/2)) = O(sqrt(b^d)). In the latter case, where the ply of a search is even, the effective branching factor is reduced to its square root, or equivalently, the search can go twice as deep with the same amount of computation. The explanation of b1b1... is that all the first player's moves must be studied to find the best one, but for each, only the second player's best move is needed to refute all but the first (and best) first player move - alpha–beta ensures no other second player moves need be considered.
When nodes are considered in a random order (i.e., the algorithm randomizes), asymptotically, the expected number of nodes evaluated in uniform trees with binary leaf-values is Theta(((b-1+sqrt(b^2+14b+1))/4)^d). For the same trees, when the values are assigned to the leaf values independently of each other and say zero and one are both equally probable, the expected number of nodes evaluated is Theta((b/2)^d).
Implementation Considerations
In practice, alpha–beta pruning is often implemented with iterative deepening, where the search depth is increased incrementally. Move ordering is critical to achieving near-optimal performance; common heuristics include examining captures first, using killer moves, and employing transposition tables. The algorithm can be extended with techniques like quiescence search to avoid horizon effects, and it forms the basis for more advanced algorithms such as principal variation search and negascout. Alpha–beta pruning is widely used in chess programs, including those that run on platforms like Chess computer systems, and it has been integrated into various game-playing AI frameworks.
Legacy and Impact
Alpha–beta pruning has had a lasting impact on Artificial intelligence and game theory. It was a key component in early chess programs and remains relevant in modern game engines, especially for games with large branching factors. The algorithm's efficiency improvements have been studied extensively, and its principles have influenced other areas of search and optimization. Although newer techniques like Machine learning and Deep learning have transformed game AI, alpha–beta pruning still serves as a fundamental tool in adversarial search, and its historical development highlights the collaborative and iterative nature of AI research.