Solving Imperfect Information Games Using Decomposition

By Neil Burch, Michael Bradley Johanson, Michael H. Bowling. 2013

121 citations recorded by the source corpus.

Decomposition, i.e. independently analyzing possible subgames, has proven to be an essential principle for effective decision-making in perfect information games. However, in imperfect information games, decomposition has proven to be problematic. To date, all proposed techniques for decomposition in imperfect information games have abandoned theoretical guarantees. This work presents the first technique for decomposing an imperfect information game into subgames that can be solved independently, while retaining optimality guarantees on the full-game solution. We can use this technique to construct theoretically justified algorithms that make better use of information available at run-time, overcome memory or disk limitations at run-time, or make a time/space trade-off to overcome memory or disk limitations while solving a game. In particular, we present an algorithm for subgame solving which guarantees performance in the whole game, in contrast to existing methods which may have unbounded error. In addition, we present an offline game solving algorithm, CFR-D, which can produce a Nash equilibrium for a game that is larger than available storage.

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

The Hanabi Challenge: A New Frontier for AI Research (2019, background): “As has been observed in domains like poker, imperfect information entangles how an agent should behave across multiple observed states [17,18].”
Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, background): “Furthermore, even game-theoretic methods do not generally achieve unexploitable behaviour when planning locally in imperfectinformation games (Burch et al., 2014; Ganzfried & Sandholm, 2015; Lisý et al., 2015).”
Safe and Nested Endgame Solving for Imperfect-Information Games (2017, methodology): “In Re-solve reﬁnement (Burch, Johanson, and Bowling 2014), a safe strategy is computed for P 2 in the endgame by constructing an auxiliary game , as shown in Figure 3, and computing an equilibrium strategy σ S for it.”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “My contributions are some fundamental tools for decomposition in imperfect information games, an algorithm CFR-D which uses decomposition to solve games, an algorithm for re-solving a portion of a game (all published in AAAI [15]), and some unpublished enhancements to the re-solving algorithm.”
Report on DeepStack Expert-Level Artificial Intelligence in Heads-Up No-Limit Poker (2019, methodology): “[2] Neil Burch, Michael Johanson, and Michael Bowling.”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, background): “This decomposition issue in IG have been addressed in many previous works (e.g., CFR-D [8, 7], DeepStack [29], Reach subgame solving [4]), mainly in the context of solving subgames in a principled way in two-player zero-sum games (like Poker).”
Endgame Solving in Large Imperfect-Information Games (2015, methodology): “One of these approaches has only been applied to the small domain of limit Leduc Hold’em, which has 936 information sets in its game tree, and is not practical for larger games such as NLTH due to its running time [3].”
Smooth UCT Search in Computer Poker (2015, methodology): “Furthermore, solving a subgame of an imperfect-information game, by using online search, can produce exploitable strategies [Burch et al., 2014; Ganzfried and Sandholm, 2015].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “sub-game decomposition technique (Burch et al., 2014; Moravcik et al., 2016; Brown and Sandholm, 2017) for imperfect-information games and by constructing fine-grained abstractions of the sub-games.”
Depth-Limited Solving for Imperfect-Information Games (2018, background): “Other safe subgame solving techniques have been developed in recent papers, but those techniques require solving to the end of the full game [7, 17, 27, 5, 6] (except one [26], which we will compare to in Section 7).”
Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games (2015, background): “Finally, one interesting question is whether the subgame decomposition ideas of [4, 19] could be adapted to the online search setting.”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, methodology): “However, the other interpretations suffer from similar issues. information sets when thinking about the properties of those defined by (Burch et al., 2014).12 Second, if used for online game playing where the time to make each decision is limited, these augmented information sets do not allow the…”