Prob-Max n : playing N-player games with opponent models
Nathan Sturtevant, Martin Zinkevich, Michael Bowling · 2006
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