Opponent-Model Search in Games with Incomplete Information

Junkang Li, Bruno Zanuttini, Véronique VentosAAAI 2024 · DOI

TL;DR

This paper introduces novel algorithms for computing optimal and robust strategies in games with incomplete information, specifically by incorporating "opponent models" that predict how an adversary might reason. They extend existing methods to handle uncertainty about these opponent models and propose a general framework for recursive opponent modeling, inspired by cognitive hierarchy theories.

What Problem Does This Paper Address?

In many real-world scenarios, like card games (poker, bridge), players don't have perfect information about their opponents' hands or strategies. This uncertainty makes decision-making challenging. Traditional game theory often assumes players are perfectly rational and have complete information, which doesn't reflect reality. While "opponent models" have been used in perfect information games to find robust strategies (guaranteeing a certain payoff), extending these to games with incomplete information is complex. This paper tackles the problem of how to compute optimal strategies when players have incomplete information about the game state and potentially incomplete or uncertain knowledge about their opponent's reasoning process.

Methods

The core of the paper lies in extending existing game-theoretic algorithms to handle opponent models within the context of incomplete information games, specifically "Vector Games" (VGs). VGs model scenarios where one player (MAX) has incomplete information about the other player's (MIN) type, while MIN has perfect information.

The authors propose several key algorithmic contributions:

  • Opponent-Model Search: They adapt minimax-style algorithms to compute maxmin values (the best guaranteed payoff) against a given set of opponent models. This involves defining "belief states" for MAX to track probabilities of MIN's types based on observed actions and the opponent models.
  • Probabilistic Opponent Models: They handle situations where MAX has a probability distribution over several possible opponent models. This is elegantly handled by merging these models into a single, weighted opponent model.
  • Lexicographic Opponent Models: They address scenarios where MAX has a ranked preference for opponent models (e.g., "MIN is most likely to follow model 1, then model 2, etc."). This is solved by extending the situational values to vectors and using lexicographic maximization.
  • Nondeterministic Opponent Models: They consider the case where MAX knows MIN's strategy is one of a set of models, but without a probability distribution. This leads to a more complex maxmin calculation where situational values become sets of vectors.
  • Opponent Models with Uncertainty: A crucial contribution is handling uncertainty about the opponent model itself. They introduce a parameter $p_\infty$ representing the probability that MIN doesn't follow the known opponent model and acts arbitrarily. This leads to a trade-off between robustness (against arbitrary play) and performance (exploiting the known model).
  • Recursive Opponent Models: They propose a general framework for recursive opponent modeling, inspired by cognitive hierarchy theory. Here, a player's strategy at level $k$ is defined as the best response against an opponent playing at level $k-1$, down to level 0. This framework is flexible and can incorporate various assumptions about opponent reasoning and aggregation.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and uses illustrative examples from existing game theory literature (e.g., Figure 1, Figure 2).

Key Insights and Ideas

  • Opponent Models as a Bridge: Opponent models are not just for predicting behavior but can be integrated into search algorithms to find robust strategies, even in incomplete information settings.
  • Belief States for Incomplete Information: Bayesian belief updating is essential for MAX to infer MIN's type and strategy based on observed actions, given a set of opponent models.
  • The Robustness-Performance Trade-off: When there's uncertainty about the opponent model ($p_\infty > 0$), MAX must balance playing optimally against the known model versus playing robustly against arbitrary behavior. This leads to strategies that might not be optimal against the single best-guess opponent model but are safer overall.
  • Recursive Reasoning as a General Framework: The proposed recursive opponent model framework is powerful because it can generalize existing approaches like best-defense models, cognitive hierarchy, and even some forms of fictitious play, providing a unified way to model bounded rationality.
  • Non-locality in Pure Maxmin: The paper highlights that the NP-hardness of pure maxmin in VGs stems from "non-locality," where local optimal choices don't necessarily lead to global optimality, making pruning strategies tricky without careful consideration.

Key Results

The paper presents several propositions that provide algorithms for computing maxmin values under different assumptions about opponent models:

  • Single OM: Algorithms run in $O(t|T|)$ time, where $t$ is the number of MIN's types and $|T|$ is the size of the game tree.
  • Probabilistic OMs: Algorithms run in $O(mt|T|)$ time, where $m$ is the number of opponent models.
  • Lexicographic OMs: Algorithms run in $O(mt|T|)$ time.
  • Nondeterministic OMs (Pure Maxmin): This case is shown to be NP-complete, even for simpler settings.
  • Opponent Models with Uncertainty: The paper shows how to modify existing algorithms to incorporate the uncertainty parameter $p_\infty$, demonstrating the trade-off between robustness and performance. For mixed maxmin, this is achieved via a modified separation oracle in an LP algorithm. For pure maxmin, a new situational value representation (annotated vectors) is introduced.

Limitations and Future Work

  • Computational Complexity: While some algorithms are polynomial, the pure maxmin case with nondeterministic opponent models is NP-complete. The paper notes that the algorithm for nondeterministic OMs is exponential in the worst case.
  • Generalization of Games: The current framework is primarily for two-player, zero-sum games. Extending it to more players and general-sum games is a stated future direction.
  • Opponent Model Representations: The paper focuses on opponent models described by behavior strategies. Future work could explore other representations (e.g., evaluation functions, learned models).
  • Uncertainty Quantification: The paper considers uncertainty $p_\infty$ as a single parameter. Exploring scenarios where $p_\infty$ is only known within a precision $\epsilon$ is suggested, with a conjecture that algorithms might benefit from the maxmin value being piecewise linear in $p_\infty$.
  • Compact Game Representations: The algorithms are presented for explicit extensive-form games. Future work could explore using compact game representations.
  • Epistemic Logic: The authors suggest an epistemic logic account of their recursive framework, linking it to notions of rationalizability.
  • Real-world Data: While the recursive framework is motivated by human behavior, the paper doesn't present empirical validation on real-world datasets.

Summary updated

BibTeX
@inproceedings{li2024opponent,
  author = {Junkang Li and Bruno Zanuttini and Véronique Ventos},
  title = {{Opponent-Model Search in Games with Incomplete Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28844},
}
Figure