Alpha–Beta Pruning

The problem: why you can't just check every move

Minimax is a recursive algorithm for choosing the next move in a two-player game such as chess or checkers. Each player assumes the opponent will play the move that is worst for the player, and chooses the move that maximizes the minimum value the opponent can leave them. The practical problem is that the number of nodes to check in the game tree grows exponentially with the number of moves you look ahead ("plies"). So in practice, games like chess cannot be fully analyzed with pure minimax. A chess program evaluates intermediate positions with a heuristic evaluation function, at a limited search depth, rather than by scanning the whole game tree down to the final positions of win and loss.

The solution: exactly the same result, far fewer checks

Alpha–beta pruning is a tree search algorithm that aims to reduce the number of nodes the minimax algorithm has to evaluate in its search tree. Applied to a standard minimax tree, it returns the same move minimax would return, but prunes away branches that cannot possibly affect the final decision. The principle: while scanning the tree, the algorithm keeps track of two bounds. "Alpha" is the minimum score the maximizing player is already assured of elsewhere in the tree, and "beta" is the maximum score the minimizing player is already assured of. As soon as beta drops below alpha (and in many implementations, already when they are equal), it is clear that one of the players will not choose to reach this branch, because they have a better alternative. The rest of the branch is cut off without being checked, including all the sub-branches below it.

How much it saves: a million nodes versus about 2,000

A common numerical example from chess: a chess program searching four plies deep (half-moves, meaning two moves for each side), with an average of 36 branches per node, evaluates more than a million leaf nodes when it checks every option without pruning. In the optimal case, when the good moves are always checked first, alpha–beta pruning would eliminate all but about 2,000 of the leaf nodes: a 99.8% reduction, without changing the move the algorithm finally chooses at all. In practice the move order is not perfect and the savings are smaller, but still huge. Thanks to these savings, chess programs could search much deeper in the same computing time: the time saved can be spent looking one or two more moves ahead, not just finishing the same search faster.

The discovery: from John McCarthy to several independent discoveries

According to the historical record, John McCarthy invented the principle of alpha–beta search during the Dartmouth Workshop. There he met Alex Bernstein of IBM, who was then writing a chess program, and recommended the method to him, but Bernstein was not impressed and did not adopt it. Allen Newell and Herbert Simon wrote in 1958 that the idea had probably been invented several times, independently. Arthur Samuel had an early version in his checkers simulator; another group of researchers in the United States (including Timothy Hart, Michael Levin and Daniel Edwards) arrived at the idea separately; Alexander Brudno in the Soviet Union arrived at it entirely independently and published it in 1963; and later, in 1975, Donald Knuth and Ronald Moore refined the method and analyzed it mathematically. Judea Pearl proved that the algorithm is optimal (in terms of expected running time) for trees with random leaf values, and Michael Saks and Avi Wigderson showed in 1986 that its randomized version is optimal too.

In practice: from Deep Blue to modern chess engines

Deep Blue, the IBM chess computer that beat world champion Garry Kasparov in 1997, used custom VLSI chips to run the alpha–beta search algorithm in parallel. In other words, alpha–beta pruning was part of the dedicated hardware its power relied on, not just an idea implemented in software. According to the documentation, each dedicated chess chip in the machine contained four parts: a move generator, a smart move stack, an evaluation function, and a search controller. They worked together to run the search with pruning in the hardware itself. Alpha–beta pruning is still a cornerstone of chess engines today, and it is taught in introductory AI courses as a key example of combining systematic search with large savings in computing time.

The modern shift: classic minimax versus neural-network-guided search

According to results DeepMind published in 2018, AlphaZero, a system that learned to play chess from the rules alone, without any human chess knowledge fed to it in advance, played a series of 1,000 games against Stockfish, a chess engine based on alpha–beta pruning, and finished with 155 wins, 6 losses and 839 draws. The key difference is in the search method: AlphaZero searches only about 60,000 positions per second in chess, compared with about 60 million for Stockfish (the 2017 preprint reported about 80,000 against 70 million). It makes up for this huge gap with its deep neural network, which focuses much more selectively on the most promising lines. This is a version of Monte Carlo Tree Search (MCTS) guided by the network, instead of a systematic scan of the branches. Larry Kaufman, one of the developers of the Komodo chess engine, said, according to Wikipedia, that the strongest engine was likely to be a hybrid of neural networks and standard alpha–beta search. The prediction shows that alpha–beta pruning is seen as the "standard search", the baseline against which learning-based approaches are measured, and not as a method that has disappeared from the field. Indeed, since 2020 Stockfish itself has used a light neural network (NNUE) to evaluate positions, and since 2023 it relies on it alone, but its search is still based on alpha–beta.