Prob-Maxn : Playing N-Player Games with Opponent Models

Nathan R. Sturtevant, Martin Zinkevich, Michael Bowling

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 cannot 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 opponent modeling in n-player games called probmaxn, which can robustly adapt to unknown opponents. We implement probmaxn in the game of Spades, showing that probmaxn is highly effective in practice, beating out the maxn and softmaxn algorithms when faced with unknown opponents.

Subjects: 1.8 Game Playing; 15.7 Search

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.