“An Analysis of Alpha-Beta Pruning” was written by Donald E. Knuth and Ronald W. Moore and published in the journal Artificial Intelligence, volume 6, in 1975 (pages 293 to 326). The paper opens by stating its aim plainly: the alpha-beta technique for searching game trees is analyzed in an attempt to provide some insight into its behavior. It is the definitive theoretical treatment of one of the most important algorithms in classical AI.
A game-playing program looks ahead by building a tree of possible moves and replies and evaluating the leaf positions. The basic procedure is minimax: assume each side plays its best move, propagating the best achievable value back up the tree. The trouble is that the tree grows explosively, so examining every branch is hopeless for games like chess. Alpha-beta pruning is the cure: by keeping two bounds, conventionally called alpha and beta, the search can prove that certain branches cannot affect the final decision and skip them entirely without changing the result. Knuth and Moore supply an expository derivation of the method, a correctness proof, its history, a proof that the procedure is optimal in a precise sense, and bounds on its running time under random data. A key result is that with good move ordering, alpha-beta can search roughly twice as deep as plain minimax in the same time.
The algorithm and the understanding this paper provided underpinned decades of game programs, most famously the chess machines that culminated in Deep Blue defeating Garry Kasparov in 1997.
Why a business reader should care: alpha-beta pruning is a canonical example of how a smart algorithm beats raw computing power, cutting away provably irrelevant options so that a search which is theoretically intractable becomes practical, a pattern that recurs throughout optimization and decision software.