Incorporating Opponent Models into Adversary Search

David Carmel and Shaul Markovitch. Incorporating Opponent Models into Adversary Search. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, 120-125 Portland, Oregon, 1996.

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 alpha-beta-star algorithm which returns the M* value of a tree while searching only necessary branches.

Keywords: Opponent Modeling, Multi-Agent Systems, Games, Heuristic Search

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Carmel:1996:IOMa,
  Author = {David Carmel and Shaul Markovitch},
  Title = {Incorporating Opponent Models into Adversary Search},
  Year = {1996},
  Booktitle = {Proceedings of the Thirteenth National Conference on Artificial Intelligence},
  Pages = {120--125},
  Address = {Portland, Oregon},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-aaai1996.pdf},
  Keywords = {Opponent Modeling, Multi-Agent Systems, Games, Heuristic Search},
  Secondary-keywords = {M*, Mstar, OM Search, 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 alpha-
    beta-star algorithm which returns the M* value of a tree while
    searching only necessary branches.
  }

  }