How computer chess programs prune away useless branches to find the winning move faster
In short: Alpha–beta pruning is an adversarial search algorithm that slashes the number of game tree nodes evaluated by minimax. By ignoring branches that cannot influence the final outcome, it allows computers to search significantly deeper in the same amount of time, turning impossible calculations into manageable, winning strategies.
At its core, alpha–beta pruning is a clever optimization for the minimax algorithm, which is used to navigate the complex decision trees of two-player zero-sum games like chess or checkers. In a standard minimax search, the computer evaluates every possible move to determine the best outcome. Alpha–beta pruning introduces two values—alpha and beta—that represent the minimum score the maximizing player is guaranteed and the maximum score the minimizing player is guaranteed. If the algorithm discovers a move that is already worse than a previously examined option, it stops evaluating that branch entirely. This process, known as pruning, eliminates subtrees that cannot possibly affect the final decision.
The efficiency gains are dramatic. In an optimal scenario where the best moves are searched first, alpha–beta pruning can effectively double the search depth compared to a simple minimax approach. For a chess program searching four plies deep with an average of 36 branches per node, a standard search might evaluate over one million terminal nodes. With optimal pruning, this can be reduced to about 2,000 nodes—a 99.8% reduction in computation. Because the number of positions searched decreases exponentially as you move closer to the current state, sorting early moves to trigger these cutoffs is a critical, high-leverage strategy.
The algorithm’s history is one of independent discovery. Invented by John McCarthy, it was later refined by researchers like Donald Knuth and Ronald W. Moore in 1975, with Judea Pearl later proving its optimality for trees with randomly assigned leaf values. Today, it is often paired with techniques like iterative deepening and move-ordering heuristics, such as the killer heuristic, to further sharpen its performance. While other strategies like best-first search exist, alpha–beta remains a foundational tool for machine-played games, proving that knowing what to ignore is just as important as knowing what to calculate.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Alpha–beta pruning
To cite this card, link to https://intellectplus.co.uk/app/technology-alpha-beta-pruning.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Inventions · More in Technology · Latest · A–Z · All topics