The Minimax Algorithm and Alpha-Beta Pruning

Allen Newell and Herbert Simon at Carnegie Mellon University and Cliff Shaw at the Rand Corporation developed some of the fundamental programming ideas behind all computer chess programs.

The team studied computer chess as part of its larger research interest in Artificial Intelligence, and in 1958 developed the NSS chess program. This program combined "algorithms" (step by step procedures) that searched for good moves, with "heuristics" (rules of thumb) that captured well-known chess strategies to reduce the number of possible moves to explore.

The best chess programming approach combined the "minimax" algorithm with the "alpha-beta pruning" technique. Using minimax, the computer searched a game tree of possible moves and counter-moves, evaluating the best move on its turn and the worst move on its opponent’s turn. Adding the “alpha-beta pruning” technique allowed the computer to ignore or "prune" branches of the search tree that would yield less favorable results, thus saving time. Most two-person game-playing programs use the minimax algorithm with the alpha-beta pruning technique.