In massive games of imperfect information, such as No-Limit Texas Hold'em, the number of possible decision points can exceed $10^{160}$. Traditional game theory approaches attempt to solve these games by creating a "blueprint" strategy—a simplified version of the game created through abstraction, where similar states are grouped together to make the computation tractable.
However, these static abstractions are brittle. When an opponent makes an unexpected move that wasn't included in the abstraction—an "off-tree" action—the agent must "map" that action to the nearest known state. As Brown and Sandholm argue, this translation often introduces rounding errors that human experts can systematically exploit. The research direction of real-time subgame refinement addresses this by shifting the computation from a pre-computed global strategy to a dynamic, local search performed during live play.
The Problem with Static Blueprints
A static blueprint is essentially a pre-computed map of the entire game. Because the map is simplified, it lacks the resolution to handle the exact nuances of every possible bet or move. Sandholm notes that while abstraction allows agents to compete in environments with vast state spaces, it inevitably loses information.
When an agent encounters a state it didn't plan for, it traditionally uses "action translation" to find the closest approximation in its blueprint. This is like trying to navigate a city using a map that only shows every fifth street; eventually, you will be forced to make a turn that the map doesn't accurately represent, leading to compounding errors.
Solving the Game You Are Actually In
Instead of relying solely on a global map, real-time subgame refinement allows an agent to stop and "re-solve" the specific portion of the game it is currently inhabiting. As Moravčík et al. demonstrated with DeepStack, an agent can calculate an expert-level strategy on the fly by treating the current state as the root of a new, smaller game—a subgame.
This process involves two key components:
- The Subgame: A localized tree that starts from the current state and extends to a certain depth or the end of the game.
- Boundary Values: Estimates of what the game is worth at the "leaves" of this subgame, often provided by a neural network or the original blueprint strategy.
By solving this subgame in real-time, the agent can account for the exact parameters of the opponent's move. Brown and Sandholm introduced "Nested Subgame Solving," where this refinement happens at every single decision point. This ensures that the agent's strategy is always tailored to the actual state of play, effectively eliminating the exploitability caused by action translation.
Maintaining Global Safety
A major challenge in subgame solving is ensuring that local improvements don't make the agent vulnerable globally. In imperfect-information games, a move that looks good in a vacuum might reveal too much about your private information, allowing an opponent to exploit you later.
To prevent this, the authors of Safe and Nested Subgame Solving for Imperfect-Information Games developed techniques that constrain the subgame solver. The solver must ensure that the new strategy is consistent with the "reach probabilities" (the likelihood of being in certain states) and the "counterfactual values" (the expected utility) established by the broader strategy. Moravcik et al. further refined this with "max-margin" refinement, which optimizes the strategy to be as robust as possible against any potential opponent deviation.
Beyond Equilibrium: Adaptation and Scaling
While early work focused on reaching a Nash Equilibrium (a strategy that cannot be beaten), recent developments have expanded subgame refinement to handle more complex scenarios:
- Opponent Exploitation: Liu et al. proposed Safe Opponent-Exploitation (SES), which allows the subgame search to deviate from a conservative equilibrium to exploit observed opponent weaknesses, while still maintaining a theoretical safety net.
- Massive State Spaces: For games even larger than Poker, such as GuanDan, Ge et al. introduced Generative Subgame Solving (GS2). This method uses strategic sampling to solve a representative subset of the subgame, drastically reducing the time required for real-time computation.
- Dynamic Abstraction: Rather than a fixed simplification, Waugh et al. and Brown and Sandholm explored ways to grow the game's abstraction dynamically, adding detail only where the solver identifies high potential for regret.
By moving the heavy lifting of strategy computation from the "factory" (offline) to the "field" (online), real-time subgame refinement allows AI to navigate the uncertainty of imperfect information with a level of precision that static models cannot match.
Key Foundational Work
Case-based strategies in computer poker (2012) — contributed 1 concept elements to this direction.
Non-Linear Monte-Carlo Search in Civilization II (2011) — contributed 1 concept elements to this direction.