Prob-Max n : playing N-player games with opponent models

Nathan Sturtevant, Martin Zinkevich, Michael Bowling

Abstract

Much of the work on opponent modeling for game tree search has been unsuccessful. In two-player, zero-sum games, the gains from opponent modeling are often outweighed by the cost of modeling. Opponent modeling solutions simply can-not search as deep as the highly optimized minimax search with alpha-beta pruning. Recent work has begun to look at the need for opponent modeling in n-player or general-sum games. We introduce a probabilistic approach to oppo-nent modeling in n-player games called prob-maxn, which can robustly adapt to unknown opponents. We implement prob-maxn in the game of Spades, showing that prob-maxn is highly effective in practice, beating out the maxn and soft-maxn algorithms when faced with unknown opponents. Introduction and Background
BibTeX
@inproceedings{sturtevant2006prob,
  author = {Nathan Sturtevant and Martin Zinkevich and Michael Bowling},
  title = {{Prob-Max n : playing N-player games with opponent models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=H14_feZObS},
}

Loading related content...

Figure