A Review of Game-Tree Pruning 1

Chess programs have three major components: move generation, search, and evaluation. All components are important, although evaluation with its quiescence analysis is the part which makes each program’s play unique. The speed of a chess program is a function of its move generation cost, the complexity of the position under study and the brevity of its evaluation. More important, however, is the quality of the mechanisms used to discontinue (prune) search of unprofitable continuations. The most reliable pruning method in popular use is the robust alpha-beta algorithm, and its many supporting aids. These essential parts of game-tree searching and pruning are reviewed’ here, and the performance of refinements, such as aspiration and principal variation search, and aids like transposition and history tables are compared.