State Abstraction in Imperfect Information Games

56 concepts45 papers1 proposal

In strategic environments where players hold private information—such as poker, security patrolling, or economic auctions—finding an optimal strategy requires solving for a Nash equilibrium. For small games, standard linear programming or iterative algorithms can compute these strategies exactly. However, as games grow in complexity, their state spaces balloon exponentially.

For instance, Heads-Up Limit Texas Hold'em contains roughly $10^{18}$ distinct states, while the No-Limit variant exceeds $10^{165}$ states, as noted by Tuomas Sandholm in Abstraction for Solving Large Incomplete-Information Games. Iterative solvers like Counterfactual Regret Minimization (CFR), introduced by Martin Zinkevich et al. in Regret Minimization in Games with Incomplete Information, must traverse these states to compute equilibrium strategies. When the game tree is larger than the memory capacity of any modern supercomputer, direct computation becomes impossible.

To bypass this "curse of dimensionality," researchers use state abstraction. The core intuition is to compress the massive, original game tree into a smaller, strategically similar "abstract game." By solving this smaller game and mapping its strategies back to the real world, agents can play at a near-superhuman level using a fraction of the compute.

The Mechanics of Information Abstraction

The foundational approach to state abstraction involves grouping distinct game states into discrete clusters, often referred to as "buckets" or "bins." In a pioneering paper, Daphne Koller et al. (Generating and Solving Imperfect Information Games) demonstrated that grouping similar information sets simplifies the strategic space, making large-scale games computationally tractable.

Consider how this works in a card game. Instead of treating every unique combination of cards as a separate decision point, an abstraction algorithm treats strategically equivalent hands as identical. Jiefu Shi et al. (Towards Approximately Optimal Poker) showed that by categorizing future random outcomes into broad classes, solvers can approximate optimal strategies at a lower resolution.

Original Game Tree (Millions of States)
   [Hand A]      [Hand B]      [Hand C]
      |             |             |
   (Bet 10)      (Bet 10)      (Bet 10)

                 VS.

Abstracted Game Tree (Single Compressed State)
         [Bucket: Strong Hands]
                    |
                 (Bet 10)

By collapsing the game tree this way, Darse Billings et al. (Approximating Game-Theoretic Optimal Strategies for Full-scale Poker) successfully compressed a poker state space from $10^{18}$ down to $10^7$, allowing a solver to compute a highly competitive strategy.

However, this compression introduces a fundamental trade-off. As argued by Andrew Gilpin et al. in Potential-Aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold'em Poker, coarser abstractions require fewer computational resources but sacrifice critical strategic nuances, resulting in a lossy approximation of the underlying game.

Expectation vs. Potential-Aware Abstraction

The earliest automated abstraction techniques clustered states based on their immediate expected value (EV)—such as a hand's raw probability of winning at the current moment. While intuitive, this approach suffers from a major flaw: it ignores how a state's value might evolve over time.

Imagine two different scenarios in a game:

  1. Scenario A: You hold a mediocre hand that has a 50% chance of winning, and no future cards will change its strength.
  2. Scenario B: You hold a "draw" hand that also has a 50% current chance of winning, but future cards will either turn it into an unbeatable hand or make it completely worthless.

An expectation-based abstraction treats these two scenarios identically because their immediate EV is identical. However, their strategic properties are completely different. Scenario B has high potential, requiring a strategy that can adapt to drastic shifts in future rounds.

To resolve this, Andrew Gilpin et al. (Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker) introduced potential-aware abstraction. Instead of clustering states by a single expected value, potential-aware algorithms cluster states based on histograms of future equity distributions.

Expectation-Based: [Scenario A (50% EV)]  <-- Clustered Together -->  [Scenario B (50% EV)]

Potential-Aware:   [Scenario A (Flat 50%)] <-- Separated By -->       [Scenario B (0% or 100%)]

By looking ahead to how a state's strength might transition across multiple rounds, potential-aware abstractions preserve the game's underlying dynamics. Sam Ganzfried (Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games) advanced this concept by applying the Earth Mover's Distance (EMD) metric to compare these multi-round probability distributions, creating abstractions that significantly outperform expectation-based models.

Imperfect Recall: Strategically Forgetting the Past

In standard game theory, agents are assumed to have perfect recall, meaning they remember every single action taken by every player since the start of the game. While mathematically clean, perfect recall causes the game tree to expand dramatically because identical current situations are treated as entirely different states if they were reached via different historical paths.

Imperfect-recall abstraction solves this by forcing the agent to strategically "forget" irrelevant historical details. If an agent finds itself in a specific late-game situation, the exact sequence of early-game actions that led there might not alter the optimal strategic choice. By merging these historically distinct paths into a single abstract state, the memory footprint of the game tree plummets.

[Christian Kroer](/author/christian-kroer) et al. (Imperfect-Recall Abstractions with Bounds in Games) proved that computing these abstractions can be framed as a mathematical clustering problem with provable solution-quality guarantees. Building on this, Jiří Čermák et al. (Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games) developed automated algorithms that construct imperfect-recall abstractions using less than 1% of the memory required by traditional perfect-recall representations, making massive sequential games solvable on standard hardware.

Overcoming Abstraction Pathologies via Refinement

While state abstraction makes computation possible, it introduces a vulnerability known as an abstraction pathology. Because the abstract game is a simplified model, an optimal strategy calculated within the abstraction can perform poorly in the real, unabstracted game. A clever opponent can exploit the rigid boundaries of the "buckets" to trap the abstracted agent.

To fix this, modern architectures combine offline abstraction with real-time, unabstracted computation. [Michael Bradley Johanson](/author/michael-bradley-johanson) et al. (Finding Optimal Abstract Strategies in Extensive-Form Games) introduced the CFR-BR algorithm, which trains an abstracted agent directly against an unabstracted opponent playing a best response. This prevents the agent from overfitting to its own simplified representation of the game.

For late-game scenarios where coarse abstractions lose too much critical detail, agents employ subgame refinement (or endgame solving). As detailed by Matej Moravcik in Refining Subgames in Large Imperfect Information Games, when the game reaches its final stages, the agent abandons the precomputed, lossy offline abstraction. Instead, it dynamically constructs and solves a highly detailed, unabstracted model of the specific subgame in real-time.

By combining broad, potential-aware offline abstractions for the early game with precise, real-time subgame refinement for the late game, modern AI systems achieve equilibrium approximations that are both computationally practical and highly robust against exploitation.

Key Foundational Work

Generating and Solving Imperfect Information Games (1995) — contributed 2 concept elements to this direction.
Changes in Representation which Preserve Strategies in Games (1971) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_state_space_abstraction_aa0a470a,
  title = {state space abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-space-abstraction/rdr_aa0a470a098e4d8cbb324cb3c00472da},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_state_space_abstraction_aa0a470a_v1,
  title = {state space abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-space-abstraction/rdr_aa0a470a098e4d8cbb324cb3c00472da/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake