An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

Branislav Bosanský, Christopher Kiekintveld, Viliam Lisý, Michal PechoucekJAIR 2014 · OpenReview

TL;DR

This paper introduces a novel algorithm for finding exact Nash equilibria in complex, imperfect-information games. By combining a compact game representation with an iterative "double-oracle" approach, it significantly reduces memory requirements and speeds up computation, enabling the solution of much larger game instances than previously possible.

What Problem Does This Paper Address?

Computational game theory grapples with finding solutions (like Nash equilibria) for games with many players, complex decision trees, and hidden information. Existing methods, particularly those using linear programming on the "sequence form" of games, struggle with the exponential growth of game states and strategies, leading to prohibitive memory and computation costs. This is a critical bottleneck for applying game theory to real-world problems in areas like security, AI, and economics. The paper aims to overcome these scalability limitations for a significant class of games: two-player, zero-sum, extensive-form games with imperfect information.

Methods

The core of the paper's contribution is a sequence-form double-oracle algorithm. Here's a breakdown:

  • Sequence-Form Representation: Instead of dealing with full, explicit strategies (which can be astronomically large), the algorithm leverages the "sequence form." This representation compactly describes strategies as sequences of actions taken by a player.
  • Double-Oracle Framework: This is an iterative approach where the game is progressively "restricted." In each iteration:
  • A restricted game is created, allowing players to use only a subset of their possible action sequences.
  • A Nash equilibrium is computed for this smaller, restricted game.
  • Best-response sequences are found for each player against the opponent's current strategy in the original, unrestricted game. These best responses are sequences that, if added to the restricted game, would improve the current solution.
  • The restricted game is expanded by adding these new best-response sequences.
  • Key Innovations:
    • Sequence-based Expansion: Unlike previous double-oracle methods that added full strategies, this algorithm adds sequences, which are more compact and efficient building blocks.
  • Default Pure Strategy: To handle information sets not covered by the restricted sequences, a "default pure strategy" is implicitly used. This ensures that any strategy in the restricted game can be mapped to a valid strategy in the full game.
  • Temporary Utility Values: For "temporary leaves" (nodes that are leaves in the restricted game but inner nodes in the original game), special utility values are assigned to guide the algorithm correctly.
  • Best-Response Sequence (BRS) Algorithm: A specialized search algorithm with pruning techniques is developed to efficiently find these best-response sequences.

Datasets

The paper evaluates its algorithm on several types of games:

  • Search Games: Inspired by patrolling and pursuit-evasion scenarios, played on directed graphs. These games feature imperfect information and can have complex information sets.
  • Phantom Tic-Tac-Toe: A blind variant of Tic-Tac-Toe, where players cannot observe opponent moves, leading to complex information sets.
  • Simplified Poker: A two-player version of poker, inspired by Leduc Hold'em, featuring imperfect information due to dealt cards.

The authors note that there isn't a standardized collection of such games, so they selected these to represent different challenges like varying utility scales, causes of imperfect information, and information set structures.

Key Insights and Ideas

  • Sequences as Building Blocks are Powerful: The core insight is that by focusing on adding sequences of actions rather than entire complex strategies, the algorithm can manage the game's complexity much more effectively. This is the key to overcoming memory limitations.
  • Implicit Strategies (Default Pure Strategy) are Sufficient: The need to explicitly represent every possible strategy is avoided by using a simple, implicit "default" strategy. This is a clever way to ensure completeness without massive memory overhead.
  • Best Responses are Cheaper than Full Solutions: The double-oracle framework's effectiveness hinges on the fact that finding a best response to a known strategy is computationally much less demanding than finding an equilibrium from scratch. This iterative refinement is highly efficient.
  • Small Support Equilibria are a Sweet Spot: The algorithm shows significant speedups when the game's Nash equilibrium involves only a small fraction of possible sequences. This suggests the algorithm is particularly well-suited for games where optimal play is relatively focused.

Key Results

  • Significant Speedups: For search games and Phantom Tic-Tac-Toe, the double-oracle algorithm was orders of magnitude faster than the standard full sequence-form linear programming (FULLLP) method.
  • Memory Efficiency: The algorithm solved much larger game instances than FULLLP, which often ran out of memory. For example, in search games, FULLLP failed at depth 7, while the double-oracle algorithm (DO-SWP) solved it quickly.
  • Competitive with Approximations (in some cases): While primarily an exact algorithm, its speed and memory efficiency allow it to solve problems that approximate algorithms like Counterfactual Regret Minimization (CFR) struggle with due to scale.
  • DO-SWP Variant is Often Fastest: The "worse-player-selection" policy for choosing which player to update in each iteration (DO-SWP) generally yielded the best performance.
  • Convergence: Theoretical guarantees are provided for convergence to a Nash equilibrium. Experimental results show rapid convergence in many cases, especially compared to CFR's long tail.

Limitations and Future Work

  • Performance on Large Support Equilibria: The authors acknowledge that the algorithm's performance degrades when Nash equilibria require a large fraction of all possible sequences. In such cases, the number of iterations and the size of the restricted game can become substantial.
  • Identifying Game Properties: It's still an open question to precisely characterize which game properties make the double-oracle algorithm particularly advantageous. Games with longer sequences seem to benefit more, but a deeper analysis is needed.
  • Domain-Specific Heuristics: While the current implementation is domain-independent, the authors suggest that incorporating domain-specific knowledge (e.g., for move ordering or best-response calculations) could lead to even greater performance improvements.
  • Approximation Techniques: Exploring the use of sampling-based (e.g., Monte Carlo) best-response algorithms for an approximate version of the double-oracle algorithm is suggested.
  • Theoretical Questions: Further investigation into the expected number of iterations and the theoretical properties of games where this method excels is needed.

Summary updated

Abstract

Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods. Our main contributions include (1) a generic sequence-form double-oracle algorithm for solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing best-response sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm.
BibTeX
@article{bosansky2014exact,
  author = {Branislav Bosanský and Christopher Kiekintveld and Viliam Lisý and Michal Pechoucek},
  title = {{An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=uRPyC8ehjLI},
}
Figure