Source-linked AI summary
Solving Imperfect Information Games Using Decomposition
Neil Burch, Michael Johanson, Michael Bowling
TL;DR
Imperfect-information games lack decomposition methods that preserve theoretical guarantees, limiting their use despite the storage demands of solving large games. This paper defines subgames and develops guaranteed re-solving and CFR-D methods. The methods provide whole-game exploitability guarantees and enable CFR-D to solve Limit Hold’em using less than 16GB rather than over 200TB for a complete strategy.
Problem
Imperfect-information games lack decomposition techniques with theoretical guarantees, while state-of-the-art solving can require hundreds of terabytes for 2-Player Limit Texas Hold’em.
Source: Introduction · p. 1Method
The paper defines imperfect-information subgames and presents guaranteed subgame re-solving plus CFR-D, which decomposes a game and solves subgames independently.
Source: Introduction · p. 1, Subgame Strategy Re-Solving · p. 3, Generating a Trunk Strategy using CFR-D · p. 4Results
CFR-D solves 2-Player Limit Texas Hold’em in less than 16GB, although storing a complete strategy would require over 200TB.
Source: Conclusions · p. 6Takeaways & Limitations
CFR-D overcomes a key storage barrier to making a computation such as solving Limit Hold’em feasible, though its time cost is currently too large.
Source: Conclusions · p. 6CFR-D’s reduced space costs increased computation time; using CFR for subgames results in O(1/ϵ^4) work.
Source: Generating a Trunk Strategy using CFR-D · p. 5
Abstract
from arXiv · showhide
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.
Introduction
Decomposition lets perfect-information games be solved through independently analyzed subgames, reducing storage and allowing strategies to be recomputed as needed. The paper addresses the lack of guaranteed decomposition methods for imperfect-information games with two methods that preserve whole-game guarantees.
Introduction
- In perfect-information games, independently solving subgames produces strategy fragments that can be combined into an optimal full-game strategy.The paper contrasts this tractable decomposition with imperfect-information games, where hidden state information complicates the approach.Source: Introduction · p. 1
- Decomposition can reduce storage because a game with S states can be split into O(S) subgames of size O(S), allowing one subgame to be analyzed at a time.Perfect-information algorithms can also recompute subgame strategies as needed rather than store the complete strategy.Source: Introduction · p. 1
- Imperfect-information games lack methods for solving or re-solving subgames with guarantees that their strategies combine into a whole-game equilibrium.Existing algorithms are limited to problems whose complete strategy fits in available space; solving 2-Player Limit Texas Hold’em would require hundreds of terabytes using a state-of-the-art algorithm.Source: Introduction · p. 1
- The paper presents two methods for safely decomposing imperfect-information games: guaranteed subgame re-solving and CFR-D, which computes error-bounded Nash-equilibrium approximations.The authors also report experiments showing that prior methods’ lack of theoretical bounds can lead to significant error in practice.Source: Introduction · p. 1
Notation and Background
The paper models games as sequential interactions with histories, legal actions, player and chance moves, and payoff-bearing terminal states. It focuses on two-player, zero-sum, perfect-recall games, and defines strategies, values, and equilibrium concepts for this setting.
Notation and Background
- An extensive-form game represents sequential interaction through histories of actions, with terminal states marking the ends of play.Non-terminal states have legal actions and a player or chance actor; terminal states carry player payoffs.Source: Notation and Background · pp. 1–2
- Information sets group states a player cannot distinguish, and a behavior strategy assigns action probabilities at each information set.The strategy cannot vary across states within an information set because the player does not observe which state occurred.Source: Notation and Background · p. 2
- The paper focuses exclusively on two-player, zero-sum games with perfect recall, where players do not forget their own actions or previously observed information.Perfect recall also gives each terminal state reachable from an information set a unique preceding state in that set.Source: Notation and Background · p. 2
- A Nash equilibrium is a profile in which each player’s strategy is a best response to the others, and exploitability is average loss to best responses in two-player, zero-sum games.A Nash equilibrium has zero exploitability.Source: Notation and Background · p. 2
- A counterfactual best response maximizes counterfactual value at every information set and is necessarily a best response, though a best response need not be counterfactual.The distinction matters at information sets the player reaches with zero probability under their own strategy.Source: Notation and Background · p. 2
Decomposition into Subgames
The paper refines the notion of a subgame for imperfect-information settings, where a state-rooted tree can cut across information-set boundaries. Its definition uses augmented information sets so the root preserves players’ information partitioning.
Decomposition into Subgames
- A state-rooted subgame can cut across information-set boundaries, including states indistinguishable to a player, making the usual perfect-information definition unsuitable.The paper introduces a refined notion of subgame for imperfect-information games.Source: Decomposition into Subgames · p. 2
- Augmented information sets group states according to the sequence of another player’s information sets and actions along the path to each state.This extends ordinary information sets to partition states where that other player does not act.Source: Decomposition into Subgames · p. 2
- An imperfect-information subgame is a forest of trees closed under descendants and membership in any player’s augmented information sets.The roots are a set of augmented information sets rather than generally a single information set.Source: Decomposition into Subgames · p. 2
- The definition preserves information partitioning at the subgame root, ruling out a subgame that contains one state but omits a state grouped with it by an augmented information set.In perfect-information games, where information sets contain single states, this definition is equivalent to the usual subgame definition.Source: Decomposition into Subgames · pp. 2–3
- Figure 1 illustrates rock-paper-scissors split into a trunk containing the initial state and a subgame containing the three states after player one’s hidden move.The subgame retains player two’s information set spanning those states and player one’s augmented information sets.Source: Decomposition into Subgames · p. 3, Figure 1 · p. 3
Subgame Strategy Re-Solving
The method re-solves a subgame using compact summary information retained from its previous strategy, while bounding the effect on whole-game exploitability. Its construction gives the opponent a choice between ending with the original counterfactual value and continuing into the subgame.
Subgame Strategy Re-Solving
- The method retains compact summary information so subgame strategies can be discarded and re-solved as needed, including on machines with limited memory.The paper also identifies improving a suboptimal strategy while guaranteeing that the replacement does at least as well in the worst case as an application.Source: Subgame Strategy Re-Solving · p. 3
- A subgame equilibrium against a fixed trunk can fail when the opponent changes trunk policy; in rock-paper-scissors, rock yields −1 against a switch to paper.The rock policy has expected utility 0 against the combined strategy, but the trunk switch changes the outcome.Source: Subgame Strategy Re-Solving · p. 3
- At each subgame root, the opponent can end with the original counterfactual value or continue into the copied subgame.The method uses the opponent’s choice between T and F to construct the re-solving game.Source: Subgame Strategy Re-Solving · pp. 3–4
- Re-solving both players increases the combined strategy’s exploitability by at most (|IRS| −1)ϵS + ϵR.ϵR is the re-solving subgame strategy’s exploitability; ϵS is the original subgame strategy’s full-game exploitability; |IRS| counts root information sets for both players.Source: Subgame Strategy Re-Solving · p. 4
Generating a Trunk Strategy using CFR-D
CFR-D solves subgames independently while updating a trunk strategy and retaining average counterfactual values at subgame roots. It reduces memory requirements, at the cost of re-solving at run-time and increased computation.
Generating a Trunk Strategy using CFR-D
- CFR updates independent regret-minimization problems at each information set, and its average policy approaches a Nash equilibrium over iterations.CFR-D belongs to this family of algorithms for approximating equilibria in very large games.Source: Generating a Trunk Strategy using CFR-D · p. 4
- CFR-D solves one subgame at a time, updates the trunk and average counterfactual values at its root, then discards the subgame solution.The average strategy approximates a Nash equilibrium even though subgame action probabilities are not retained; root average counterfactual values are kept for later re-solving.Source: Generating a Trunk Strategy using CFR-D · p. 4
- CFR-D stores values only for trunk information sets and subgame roots, giving memory requirements sub-linear in the number of information sets.Decomposing the game can reduce storage from O(S) to O(√S).Source: Generating a Trunk Strategy using CFR-D · p. 5
- The memory reduction requires run-time subgame re-solving and can raise work to O(1/ϵ^4) when CFR solves each subgame.CFR requires O(1/ϵ^2) iterations for error below ϵ; solving subgames at each trunk iteration adds another such factor.Source: Generating a Trunk Strategy using CFR-D · p. 5
- CFR-D requires mutual counterfactual best responses in subgames; ordinary mutual best responses may choose arbitrary policies at zero-reach information sets.A post-processing step can produce counterfactual best responses when another solver, such as a sequence-form linear program, is used.Source: Generating a Trunk Strategy using CFR-D · p. 5
Experimental Results
The experiments test safe subgame re-solving, CFR-D, and re-solving abstract strategies in Leduc Hold’em. They show that safe re-solving’s error tracks its iteration bound, CFR-D’s exploitability plateaus when other error sources remain, and safe re-solving reduces exploitability in the abstract-strategy test.
Re-Solving Strategies in Subgames
- The O(1/T) error bound for CFR in re-solving games translates into expected O(1/T) error in the reconstructed strategy’s overall exploitability.Unsafe re-solving instead approaches about 0.080 chips/hand without a theoretical bound; safe re-solving was around one tenth of a percent slower.Source: Re-Solving Strategies in Subgames · p. 5
Solving Games with Decomposition
- CFR-D exploitability plateaus as subgame iterations increase because trunk and re-solving errors remain constant while subgame error decreases.The experiments used CFR for the trunk, subgames, and re-solving games, so exploitability sums errors from all three.Source: Solving Games with Decomposition · pp. 5–6
Re-Solving to Improve Subgame Strategies
- In the Leduc Hold’em test, the starting abstract strategy is exploitable for 0.382 chips/hand in the full game because its abstraction loses strategically important texture information.The experiment re-solved unabstracted subgames and evaluated the resulting strategy against the original abstract strategy and by exploitability.Source: Re-Solving to Improve Subgame Strategies · p. 6
- After 200 iterations, safe re-solving lowers exploitability to 0.33 chips/hand; after 2,000 iterations it ranges from 0.23 to 0.29 chips/hand.Unsafe re-solving remains at 0.39 chips/hand after 6,250 iterations; its apparent convergence to the original exploitability is a coincidence, as outcomes can vary in other situations.Source: Re-Solving to Improve Subgame Strategies · p. 6
Conclusions
The paper presents safe subgame re-solving with a whole-game exploitability guarantee and CFR-D for decomposition-based game solving. CFR-D reduces space use at the cost of increased computation time.
Conclusions
- The subgame re-solving method uses summary information to generate a strategy no more exploitable than the original, unlike previous methods, which can produce significantly exploitable strategies.Source: Conclusions · p. 6
- CFR-D achieves sub-linear space costs through decomposition, solving 2-Player Limit Texas Hold’em in less than 16GB versus over 200TB to store a complete strategy.The space reduction comes at increased computation time, which is currently too large for solving Limit Hold’em.Source: Conclusions · p. 6
Appendix: Proofs
The proofs establish conditions under which re-solving a subgame preserves a whole-game exploitability guarantee. They bound the increase for a recovered strategy and show how counterfactual best responses can be constructed recursively.
Appendix: Proofs
- Re-solving for player one does not increase whole-game exploitability when it does not increase player two’s best-response counterfactual values.The proof constructs a counterfactual best response recursively, using unchanged strategies outside the subgame and induction over information-set depth.Source: Appendix: Proofs · p. 7
- For any player two strategy in the original game and player one strategy in the recovery game, the combined strategy’s counterfactual value at recovery information sets equals player two’s reach probability times recovery-game utility.This relation is used in bounding exploitability of the recovered strategy.Source: Appendix: Proofs · p. 7
- The recovered strategy increases exploitability by no more than (|Ĩ_R^2| −1)ϵS + ϵR, where ϵS bounds player two’s counterfactual regret and ϵR bounds recovery-game exploitability.The proof relates recovery-game utilities to original-game counterfactual values, then bounds the accumulated error across player two’s recovery information sets.Source: Appendix: Proofs · pp. 7–8