Incorporating Opponent Models into Adversary Search

Abstract

This work presents a generalized theoretical framework 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 fffi algorithm which returns the M value of a tree while searching only necessary branches. Introduction The minimax algorithm (Shannon 1950) has served as the basic decision procedure for zero-sum games since the early days of computer science. The basic assumption behind minimax is that the player has no knowledge about the opponent's decision procedure. In the absence of such knowledge, minimax assumes that the opponen...