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

By Branislav Bosanský, Christopher Kiekintveld, Viliam Lisý, Michal Pechoucek. 2014

97 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Fictitious Self-Play in Extensive-Form Games (2015, methodology): “The most popular modern techniques are either optimizationbased (Koller et al., 1996; Gilpin et al., 2007; Miltersen & Sørensen, 2010; Bosansky et al., 2014) or perform regret minimization (Zinkevich et al., 2007).”
Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence (2019, background): “Competitive multi-agent intelligence originally comes from computational game theory [9, 11, 60, 79].”
Algorithms for computing strategies in two-player simultaneous move games (2016, unknown): “There are also state-of-the-art algorithms for solving generic extensive-form games with imperfect information, based on sequence-form optimization problems [42, 43, 44].”