Learning Models of Opponent’s Strategy in Game Playing

Contents

Most of the activity in the area of game playing programs is concerned with efficient ways of searching game trees. There is substantial evidence that game playing involves additional types of intelligent processes. One such process performed by human experts is the acquisition and usage of a model of their opponent’s strategy. This work studies the problem of opponent modelling in game playing. A simplified version of a model is defined as a pair of search depth and evaluation function. M*, a generalization of the minimax algorithm that can handle an opponent model, is described. The benefit of using opponent models is demonstrated by comparing the performance of M* with that of the traditional minimax algorithm. An algorithm for learning the opponent’s strategy using its moves as examples was developed. Experiments demonstrated its ability to acquire very accurate models. Finally, a full model-learning game-playing system was developed and experimentally demonstrated to have advantage over non-learning player.