Source-linked AI summary
Safe and Nested Subgame Solving for Imperfect-Information Games
Noam Brown, Tuomas Sandholm
TL;DR
In imperfect-information games, a subgame’s optimal strategy can depend on strategies and outcomes elsewhere, making isolated solving inadequate and whole-game solving difficult for large games. The paper introduces theoretically stronger and practically better subgame-solving techniques, including methods for off-tree actions and repeated solving, and demonstrates them in heads-up no-limit Texas hold’em, where its AI defeated top humans.
Problem
In imperfect-information games, a subgame’s optimal strategy may depend on strategies and outcomes in other unreached subgames, while solving the whole game upfront does not extend to large games.
Method
The paper develops subgame-solving techniques that first use a blueprint strategy and then improve individual subgames, including nested solving for off-tree actions and repeated solving as play progresses.
Results
The techniques outperform prior subgame-solving methods in theory and practice, substantially outperform action translation for off-tree actions, and enabled an AI to defeat top humans in heads-up no-limit Texas hold’em.
Takeaways & Limitations
Subgame solving can be applied repeatedly during play and was a key component of the first AI to defeat top humans in heads-up no-limit Texas hold’em.
Takeaways & Limitations
When value estimates are used, exploitability might exceed the blueprint and solution quality depends on estimate accuracy; guarantees also use lower bounds on gifts after other subgames are solved.
Abstract
from arXiv · showhide
In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it by solving individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.
1 Introduction
Imperfect-information subgames cannot generally be solved independently because hidden state and other unreached subgames affect optimal play. The paper uses blueprint strategies and real-time subgame solving to address larger games.
- The challenge: Hidden information can make a subgame’s optimal strategy depend on values in other, unreached subgames.The current game-tree node is typically unknown, unlike in perfect-information games.
- Scaling challenge: 10161 decision points make heads-up no-limit Texas hold’em too large for solving the whole game upfront.Heads-up limit Texas hold’em, with 10^13 decision points, was essentially solved without decomposition.
- Blueprint strategies: An abstraction compresses the original game while retaining strategic characteristics, and its solution becomes the blueprint strategy for the full game.Continuous action spaces can be discretized before solving the abstract game.
- Subgame solving: Subgame solving improves a blueprint by solving a more fine-grained abstraction in real time while fitting the result within the overarching blueprint.This approach targets heavily abstracted games in which the blueprint may be far from the true solution.
2 Coin Toss
Coin Toss demonstrates why Player 2 cannot optimize the Play subgame without considering outcomes and values outside it. Changing the Sell payoff reverses the optimal guessing strategy.
- Game structure: Coin Toss hides the coin outcome from P2, who must choose one strategy across indistinguishable Heads and Tails nodes.P1 observes the coin and chooses Sell or Play; P2 acts in the Play subgame.
- Original payoffs: P2’s optimal Play strategy is 25% Heads and 75% Tails when Sell yields 0.50 on Heads and −0.50 on Tails.This keeps P1’s best achievable average reward at $0, matching always choosing Sell.
- Changed payoffs: Reversing the Sell values makes P2’s optimal Play strategy 75% Heads and 25% Tails.The change shows that subgame strategy depends on strategies and outcomes elsewhere in the game.
- Lesson: The Coin Toss example establishes that imperfect-information subgames cannot be solved using information from the subgame alone.The dependence arises because P2 cannot identify the exact underlying game-tree node.
3 Notation and Background
This section formalizes two-player zero-sum extensive-form games, including histories, actions, chance, infosets, strategies, values, best responses, Nash equilibrium, exploitability, and subgames.
- Game representation: A two-player zero-sum extensive-form game represents nodes as action sequences, with players or chance selecting available actions.Chance selects actions with fixed probabilities, and h·a denotes a successor node.
- Information sets: Infosets group nodes indistinguishable to a player, requiring the same player and available actions at every grouped node.A player therefore uses one action distribution across all nodes in an infoset.
- Strategies: A strategy assigns action probabilities at each infoset, while a strategy profile combines one full-game strategy for each player.Expected payoff is defined under the resulting profile.
- Solution quality: Exploitability measures how much worse a strategy performs against an opponent best response than a Nash equilibrium strategy would perform.A Nash equilibrium is a profile from which no player can improve by changing strategy.
- Best responses: A counterfactual best response is a best response that also maximizes value in unreached infosets.Its associated counterfactual best response value measures the expected payoff after an infoset has been reached.
- Subgames: An imperfect-information subgame contains nodes sharing prior public actions and preserves relevant infosets within the set.In poker, a subgame is defined by a sequence of bets and public board cards.
4 Prior Approaches to Subgame Solving
Prior methods improve or preserve a blueprint by solving augmented subgames, but they trade theoretical safety, practical improvement, and dependence on payoff estimates differently.
- Blueprints: A blueprint is an approximate full-game strategy, and subgame solving changes it only within an encountered subgame.The blueprint may be arbitrary and may come from an abstraction.
- Unsafe subgame solving: Unsafe subgame solving assumes blueprint play before the subgame, then solves using the resulting distribution over its root nodes.It solves an augmented subgame containing an initial chance node and the target subgame.
- Unsafe subgame solving: Unsafe subgame solving has no theoretical solution-quality guarantee and can perform extremely poorly, although it sometimes produces low-exploitability strategies.In Coin Toss, it would always choose Heads, allowing P1 to exploit it by choosing Play on Tails.
- Safe subgame solving: Safe subgame-solving methods ensure exploitability is no higher than the blueprint’s exploitability.Subgame Resolving gives P1 an opt-out action whose payoff equals the value of playing optimally against the blueprint.
- Subgame Resolving: Resolving can preserve dominated blueprint actions, such as Forfeit 25% of the time in Coin Toss, and therefore miss improvement opportunities.Its original purpose was compact storage and real-time reconstruction rather than improving a blueprint strategy.
- Maxmargin: Maxmargin can improve performance, but it does worse in practice when equilibrium values are estimated.Resolving only requires all margins to be nonnegative.
5 Reach Subgame Solving
Reach subgame solving accounts for how independently solved subgames can jointly increase an opponent’s attainable value. It distributes available gifts across subgames while producing stronger margins than prior safe techniques.
- Motivation: Independent subgame solving can make previously assumed gifts overlap, so potential value increases must remain bounded when summed across subgames.A lower bound on gifts after solving other subgames supports the strongest exploitability guarantee.
- Method: Reach subgame solving increases an augmented subgame’s alternative payoff using the probability of reaching it through a gift.The reach margin is based on a lower-bound gift value and the probability that P1 reaches the subgame.
- Method: Reach-Resolve and Reach-Maxmargin use margins at least as large as those of their corresponding prior techniques.The larger margin follows because the lower-bound gift is nonnegative.
- Guarantee: Reach-Maxmargin has exploitability no higher than past safe techniques when disjoint subgames use lower bounds on gifts.The guarantee applies when the subgames are solved independently under the stated gift-bound condition.
- Practical variant: Using estimated equilibrium values instead of blueprint values leads to far lower exploitability in practice, but can relax the guarantee relative to the blueprint.The estimate-based approach is presented as a practical trade-off between empirical performance and safety guarantees.
6 Estimates for Alternative Payoffs
The paper replaces exact equilibrium alternative payoffs with estimates that can be obtained within the blueprint abstraction. This can improve practical performance, while the resulting guarantee depends on estimation accuracy.
- Scope: The minimally exploitable strategy differing from the blueprint only in solved subgames need not be a Nash equilibrium because outside strategies remain fixed.It is instead the closest strategy achievable by changing only those subgames.
- Estimation: Alternative payoffs can be estimated using a counterfactual best response constrained to the abstraction that generated the blueprint.The paper denotes this constrained value as an approximation to the full-game counterfactual best-response value.
- Estimation: For a blueprint generated by T CFR iterations, the final iteration’s strategy can provide the constrained counterfactual best response used in experiments.This exploits convergence toward a counterfactual best response within the abstract game.
- Guarantees: Estimated equilibrium values can yield exploitability bounds based on their distance from the true values.This differs from earlier algorithms that guarantee exploitability no worse than the blueprint.
- Results: Reach-Resolve outperforms Resolve regardless of whether equilibrium estimates are used, while estimates generally improve practical performance.The theorem also extends to Reach-Maxmargin, although Resolve performs better with estimates in practice.
- Extension: Distributional alternative payoffs improve robustness to errors in blueprint estimates.This improvement is described as producing even better performance than the basic estimate-based approach.
7 Nested Subgame Solving
Nested subgame solving responds to off-tree opponent actions by solving an expanded subgame rather than translating the action into the abstraction. The process can repeat as play descends the game tree.
- Problem: Action translation maps an opponent’s off-tree action to an included abstract action, whereas nested solving computes a unique real-time response.The paper uses a $101 bid mapped to $100 as an example of action translation.
- Results: The methods dramatically outperform action translation and can solve finer-grained models as play progresses down the game tree.The paper presents these methods as alternatives to translating off-tree actions.
- Method: The inexpensive method generates a subgame after an off-tree action, solves it, and incorporates the solution into an expanded blueprint.The process repeats whenever another off-tree action is chosen.
- Method: Near-optimal actions in the blueprint abstraction can support approximate responses to arbitrary opponent actions, especially in very large or continuous action spaces.Only a small number of near-optimal actions may need to be included for the estimate used by the method.
- Limitation: The inexpensive approach cannot be combined with Unsafe subgame solving because off-tree-action reach probabilities are undefined.A more expensive alternative recomputes strategies from the preceding node and adds the off-tree action to the abstraction.
8 Experiments
The experiments evaluate safe and unsafe subgame-solving methods across poker abstractions and nested play, measuring exploitability in milli big blinds per hand. The techniques generally outperform action translation, with Reach-based methods and estimated or distributional alternative payoffs often performing best, while Libratus decisively defeated top human players.
- Experimental setup: Experiments cover NLFH, NLTH, and heads-up no-limit Texas hold’em, using CFR+ for equilibrium finding and mbb/h to measure exploitability.NLFH and NLTH vary information-abstraction granularity at the flop or turn before applying subgame solving.
- Safe methods: Reach subgame solving lowered exploitability even with theoretically safe gift splitting, while aggressive scaling often helped but could increase exploitability when excessive.The safe guarantee is weakened by aggressive scaling, and at least one case showed higher exploitability.
- Safe methods: Reach-Estimate + Distributional generally achieved the lowest exploitability among the tested choices and usually outperformed Unsafe subgame solving.Estimated values improved over Maxmargin and Resolve in all but one case, and distributional alternative payoffs improved exploitability in all but one case.
- Nested subgame solving: All tested subgame-solving techniques substantially outperformed action translation, with Reach-Maxmargin performing best among the compared methods.Nested subgame solving is preferable when sufficient time is available to solve the subgame.
- Libratus: Libratus applied nested subgame solving from the third betting round and decisively defeated four top specialists by 147 mbb / hand with 99.98 statistical significance.The competition lasted 20 days and included 120,000 hands of poker.
9 Conclusion
The paper presents subgame-solving techniques with stronger theoretical guarantees and better practical performance than prior methods, including nested solving for off-tree actions. In practice, these techniques were demonstrated in heads-up no-limit Texas hold’em, where Libratus became the first AI to defeat top humans.
- The proposed subgame-solving technique improves both theoretical guarantees and practical performance relative to prior methods.
- Nested subgame solving addresses opponent off-tree actions and performs dramatically better than the usual action-translation approach.
- The paper reports the first measurement of subgame-solving exploitability in large games.
- The techniques were effective in heads-up no-limit Texas hold’em, producing the first AI to defeat top humans in that game.
A Maxmargin Solving
Maxmargin solving modifies Resolving to maximize the minimum subgame margin, thereby seeking both deterrence and punishment of subgame entry. It is safe and can strictly reduce exploitability under a stated positive-margin condition, though it may overfit assumptions in practice.
- Maxmargin seeks to deter Player 1 from entering a subgame and punish her if she enters despite the deterrence.
- Maxmargin augments Resolving by maximizing the minimum margin across Player 1’s earliest-reachable infosets.The augmented subgames used by Resolving and Maxmargin are otherwise identical.
- Implementation: The augmented subgame can be solved with a standard LP solver, while the experiments used CFR with the corresponding gadget game.
- Maxmargin is safe and strictly lowers exploitability when every Player 1 best response reaches the subgame through an infoset with positive margin.Its stronger guarantees can nevertheless yield worse practical performance than Resolving when combined with later techniques because of greater overfitting to assumptions.
- Gadget game: The gadget game shifts Player 1 payoffs by alternative payoffs and lets Player 1 choose the starting infoset, encoding the margin objective for iterative solvers.These changes force focus on improvement over baseline payoffs and on maximizing the minimum margin.
B.1 Distributional Alternative Payoffs
Distributional alternative payoffs model uncertainty in estimated subgame values by randomizing alternative payoffs visible to P1 but hidden from P2. This yields a simpler gadget-game solution with a Nash-equilibrium guarantee for the resulting infinite augmented subgame.
- Motivation: The distributional construction addresses overfitting to estimated alternative payoffs, favoring robustness when payoff estimates are uncertain.The motivating example prefers sacrificing a high estimated value when its true value may vary substantially.
- Distributional alternative payoffs: Model uncertainty is incorporated by making alternative payoffs random variables whose realized values P1 observes while P2 does not.The modified augmented subgame otherwise matches the Resolve construction.
- Gadget-game reduction: The modified augmented subgame becomes infinite because real-valued payoff outcomes can induce distinct P1 strategies.Its special structure nevertheless permits solving a simpler gadget game to obtain the relevant P2 strategy.
- Guarantee: Theorem 3 proves that solving the simplified gadget game produces a P2 Nash-equilibrium strategy in the corresponding infinite distributional augmented subgame.The theorem applies when CFR is used under the specified construction.
- Experimental method: Softmax, also called Hedge, provides an alternative gadget-game formulation with better empirical performance and is used in the experiments.The paper describes this gadget game in Appendix C.
D Scaling of Gifts
Gift scaling can improve Reach-Maxmargin empirically but must respect the aggregate-gift condition for theoretical guarantees. Excessive scaling can instead make performance worse than Maxmargin.
- Theoretical condition: Reach subgame solving retains its theoretical guarantees only when gifts assigned to reachable subgames do not collectively exceed the original gift.The paper enforces this by increasing a related infoset’s margin by at most g(I1).
- Empirical behavior: Gift scaling often reduced exploitability in the experiments, but the effect was not uniformly beneficial.The paper reports an exception in which exploitability increased when gifts were scaled too far.
- Empirical behavior: Optimal performance in one Flop Texas Hold’em case occurred when gifts were scaled by about 1,000.At scaling factor 0 the algorithm matches Maxmargin, while factor 1 is the theoretically correct Reach-Maxmargin form.
- Empirical behavior: Scaling gifts by 100,000 produced performance worse than Maxmargin subgame solving in the reported case.This demonstrates that aggressive scaling can be harmful even when moderate scaling helps.
G Proof of Theorem 3
Theorem 3 is proved by relating the distributional augmented subgame to a simpler gadget game and showing that corresponding CFR updates match. Consequently, the resulting P2 strategy converges to a Nash equilibrium.
- Conclusion: The gadget-game play matches CFR in the distributional subgame and CFR-BR at the initial infosets, so convergence yields a Nash equilibrium.The equivalence follows because corresponding P1 and P2 play remains identical throughout the construction.
- Proof construction: Corresponding P1 infosets in the two games differ only by random-variable outcomes, while corresponding P2 infosets are reached through the same actions.This correspondence supports comparing their instantaneous regrets.
- Inductive argument: Inductively, corresponding infosets have identical regrets and therefore identical strategies on every CFR iteration.The proof begins with zero regrets and propagates equality through subsequent iterations.