Search

The multi-model search framework generalizes minimax to allow exploitation of recursive opponent models. In this work we consider adding pruning to the multi-model search. We prove a sufficient condition that enables pruning and describe two pruning algorithms, αβ ∗ and αβ 1p ∗ . We prove correctness and optimality of the algorithms and provide an experimental study of their pruning power. We show that for opponent models that are not radically different from the player's strategy, the pruning power of these algorithms is significant.

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 m ove 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. † Much of this article is a revision of material condensed from an entry entitled ‘‘Computer Chess Methods,’’ prepared for the Encyclopedia of Artificial Intelligence , S. Shapiro (editor), to be published by John Wiley & Sons in 1987. The transposition table pseudo code of Figure 7 is similar to that in another paper: ‘‘Parallel Search of Strongly Ordered Game Trees,’’ T.A. Marsland and M. Campbell, ACM Computing Surveys, Vol 14, No. 4, copyright 1982, Association for Computing Machinery Inc., and is reprinted by permission.