Incorporating Opponent Models into Adversary Search

David Carmel, Shaul Markovitch

This work presents a generalized theoretical frame-work that allows incorporation of opponent models into adversary search. We present the M* algorithm, a generalization of minimax that uses an arbitrary opponent model to simulate the opponent’s search. The opponent model is a recursive structure consisting of the opponent’s evaluation function and its model of the player. We demonstrate experimentally the potential benefit of using an opponent model. Pruning in M* is impossible in the general case. We prove a sufficient condition for pruning and present the ab* algorithm which returns the M* value of a tree while searching only necessary branches.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.