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

Nathan R. Sturtevant, Martin Zinkevich, Michael H. 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 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 Prob-Max$^n$, which can robustly adapt to unknown opponents. We implement Prob-Max$^n$ in the game of Spades, showing that it is highly effective in practice, beating out the Max$^n$ and Soft-Max$^n$ algorithms when faced with unknown opponents.

Introduction

In the domain of two-player, zero-sum games like Chess or Checkers, the minimax algorithm is the gold standard. It operates on the assumption that the opponent will always take the action that minimizes your utility. However, this assumption is often invalid in $n$-player, general-sum games. In these settings, players may have diverse and even conflicting utility functions.

In a game like Spades, one player might prioritize maximizing their total tricks, while another might focus on avoiding "overtricks" to evade penalties. If an agent searches a game tree assuming all opponents share its specific goal, its predictions will be flawed. This can lead to "pathological" outcomes where increasing search depth actually degrades performance because the agent becomes more confident in a fundamentally incorrect model of the world. The challenge is to develop a search algorithm that remains robust even when opponent strategies and motivations are unknown.

The Prob-Max$^n$ Algorithm

Prob-Max$^n$ addresses these challenges by moving away from deterministic assumptions. It builds upon the Max$^n$ algorithm (a multi-player extension of minimax) and Soft-Max$^n$ (which handles ties by considering sets of possible outcomes). The core innovations of Prob-Max$^n$ include:

  1. Probabilistic Modeling: Instead of predicting a single "best" move for an opponent, the algorithm assigns probabilities to all possible moves. It assumes opponents are $\epsilon$-greedy: they typically choose the optimal move according to their model but occasionally deviate.
  2. Model Weighting: The agent maintains a "global belief"—a probability distribution—over a set of possible opponent models (e.g., "trick-maximizer" vs. "overtrick-avoider").
  3. Expected Utility Calculation: At each node, the algorithm computes an expected utility matrix by weighting the outcomes of various models by their current likelihood.
Example game tree with three choices (a, b, c) and their associated payoffs.

As illustrated in Figure 3, a player may face multiple choices with varying payoffs for all participants. A deterministic search might fixate on a single "best" outcome, whereas Prob-Max$^n$ evaluates the risk and reward across different potential opponent behaviors.

Utility and weight calculations for the choices in Figure 3, demonstrating how Prob-Maxn handles model uncertainty.

Figure 6 demonstrates how the algorithm calculates utilities and weights for these choices. By considering both the Maximize Tricks (MT) and minimize OverTricks (mOT) models, the agent can identify moves that are robust across different opponent types. For instance, if Choice (b) provides a stable utility across models while Choice (a) is highly sensitive to the opponent's goal, Prob-Max$^n$ will favor the more robust option.

  1. Bayesian Learning: During gameplay, the algorithm uses Bayesian inference—specifically Markov chain Monte Carlo (MCMC) methods—to update its beliefs about opponent models based on observed moves.

Experimental Evaluation

The researchers evaluated Prob-Max$^n$ in a three-player, no-partnership version of Spades. The evaluation used 100 unique deal sequences, permuted across different seating arrangements to produce 600 games per experiment. Two primary utility functions were defined: MT (Maximize Tricks) and mOT (minimize OverTricks). This setup allowed the team to test how well the algorithm could adapt to opponents with fundamentally different objectives.

Key Insights and Results

The Importance of Robustness

A key finding is that in $n$-player games, search depth is secondary to model accuracy. An agent that assumes everyone plays like itself can see its win rate plummet from 75% to 44% when facing opponents with different goals. Prob-Max$^n$ succeeds by spreading probability across multiple likely actions, avoiding the "all-or-nothing" errors of deterministic search.

Performance Gains

Prob-Max$^n$ demonstrated statistically significant improvements over Soft-Max$^n$ in nearly every test case. In matches against opponents focused on minimizing overtricks ($mOT_{mOT}$), Prob-Max$^n$ achieved a 53% win rate, a 7% improvement over the previous state-of-the-art. Interestingly, while Bayesian learning was highly accurate (identifying opponent types with up to 98.8% accuracy), the inherent robustness of the Prob-Max$^n$ structure was the primary driver of its success.

Computational Efficiency

Despite the complexity of maintaining utility matrices for multiple models, Prob-Max$^n$ remains efficient. It produces moves in less than one second for a standard Spades hand, making it suitable for real-time play.

Limitations and Future Work

While effective, Prob-Max$^n$ currently relies on a predefined set of opponent models. If an opponent uses a strategy entirely outside this set, performance may degrade. Additionally, in games with extremely large outcome sets, the "Soft-Max" component could theoretically slow down search. Future research could focus on expanding the model set dynamically or applying the algorithm to even more complex domains where the benefits of learning might be more pronounced.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sturtevant2006prob,
  author = {Nathan R. Sturtevant and Martin Zinkevich and Michael H. Bowling},
  title = {{Prob-Maxn: Playing N-Player Games with Opponent Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=H14_feZObS},
}
Figure