Home | Publications | CS Home

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, pages 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

---

Secondary Keywords: M*, Mstar, OM Search, Adversary Search

---

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},
  Keywords =    {Opponent Modeling, Multi-Agent Systems},
  Secondary-keywords =  {M*, Mstar, OM Search, Adversary Search},
  Address =     {Portland, Oregon},
  Url =         {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-aaai1996.pdf},
  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.}
}