PRUNING ALGORITHMS FOR MULTIMODEL ADVERSARY SEARCH

The multi-model search framework generalizes minimax to allow exploita tion of recursive opponent models. In this work we consider adding pru ning to the multi-model search. We prove a sufficient condition that e nables pruning and describe two pruning algorithms, alpha beta and al pha beta(1p) We prove correctness and optimality of the algorithms an d provide an experimental study of their pruning power. We show that f or opponent models that are not radically different from the player's strategy, the pruning power of these algorithms is significant. (C) 19 98 Elsevier Science B.V.