Incorporating Opponent Models into Adversary Search

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Negotiation & Coalition

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.