Pruning Algorithms for Multi-Model Adversary Search

David Carmel and Shaul Markovitch. Pruning Algorithms for Multi-Model Adversary Search. Artificial Intelligence, 99:325-355, 1998.

Abstract

The Multi-model search framework generalizes minimax to allow exploitation of recursive opponent models. In this work we consider adding pruning to the multi-model search. We prove a sufficient condition that enables pruning and describe two pruning algorithms, alpha-beta-star and alpha-beta-star-one-pass. We prove correctness and optimality of the algorithms and provide an experimental study of their pruning power. We show that for opponent models that are not radically different from the player's strategy, the pruning power of these algorithms is significant.

Keywords: Opponent Modeling, Multi-Agent Systems

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

Online version:

Bibtex entry:

 

@article{Carmel:1998:PAM,
  Author =      {David Carmel and Shaul Markovitch},
  Title =       {Pruning Algorithms for Multi-Model Adversary Search},
  Year =        {1998},
  Journal =     {Artificial Intelligence},
  Volume =      {99},
  Number =      {2},
  Pages =       {325--355},
  Keywords =    {Opponent Modeling, Multi-Agent Systems},
  Secondary-keywords =  {M*, Mstar, OM Search, Pruning, Adversary Search},
  Url =         {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-aij1998.pdf},
  Abstract =    {The Multi-model search framework generalizes minimax to allow exploitation of
             recursive opponent models. In this work we consider adding pruning to the
             multi-model search. We prove a sufficient condition that enables pruning and
             describe two pruning algorithms, alpha-beta-star and alpha-beta-star-one-pass.
             We prove correctness and optimality of the algorithms and provide an
             experimental study of their pruning power. We show that for opponent models
             that are not radically different from the player's strategy, the pruning power
             of these algorithms is significant.}
}