Home | Publications | CS Home

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:

---

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

  }