State Abstraction for Large Imperfect Information Games

This direction is merged into another direction: state space abstraction, potential-aware state abstraction. Its last version stays readable and citable here.

Version 1 of 125 papers28 conceptsfrozen 2026-10-04

In games like No-Limit Texas Hold'em, the number of possible decision points is astronomical—roughly $10^{165}$, a figure far exceeding the number of atoms in the observable universe. Traditional algorithms for finding a Nash equilibrium, which work by traversing the entire game tree, fail immediately at this scale. To make these problems tractable, researchers use state abstraction: the process of strategically shrinking the game by grouping similar situations together.

The Intuition of Bucketing

The core idea behind abstraction is that many distinct game states are strategically equivalent. In poker, a "King-high flush" on the flop might be technically different from a "Queen-high flush," but the optimal way to play them is often nearly identical.

As Jiefu Shi and Michael Littman demonstrated in Towards Approximately Optimal Poker, we can group these similar hands into discrete "bins" or "buckets." By solving the game at this lower resolution, we compute a strategy for the buckets rather than individual hands. This approach was foundational for the first "pseudo-optimal" bots developed by Darse Billings and Jonathan Schaeffer 0001, who compressed the state space of Texas Hold'em from $10^{18}$ down to $10^7$ to compete with professionals (Approximating Game-Theoretic Optimal Strategies for Full-scale Poker).

Measuring Similarity with Earth Mover’s Distance

The challenge of abstraction is deciding which states belong in the same bucket. If you group a very strong hand with a very weak one, the resulting strategy will be nonsensical. Early methods looked only at current hand strength, but this ignored "potential"—how a hand might improve on future cards.

To solve this, Sam Ganzfried and Tuomas Sandholm introduced potential-aware abstraction in Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games. They used the Earth Mover’s Distance (EMD) to cluster hands based on the similarity of their future win-rate distributions. If two hands have a similar "probability of becoming a winner" across all possible future cards, they are grouped together. This ensures the abstraction preserves the strategic nuances of the game's trajectory.

Strategic Forgetting and Imperfect Recall

While it seems intuitive that an AI should remember everything that happened in a game, Jiri Cermak and Viliam Lisý argue for the opposite: imperfect-recall abstractions. In Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games, they show that by teaching an AI to strategically "forget" irrelevant historical details, it can solve massive games using less than 1% of the memory required by traditional methods.

The intuition is that the exact sequence of bets in the early game often matters less than the current pot size and hand strength. By merging histories that lead to similar current situations, solvers can allocate more computational "resolution" to the decisions that matter most. However, this must be balanced carefully; as Yanchang Fu notes in KrwEmd, "forgetting everything" can lead to excessive abstraction, requiring a "k-recall" feature to retain just enough context to remain competitive.

Beyond Poker: Security and Biology

The power of abstraction extends beyond card games into high-stakes real-world scenarios:

  • Security: In patrolling games, Nicola Basilico and Nicola Gatti use abstraction to cluster movements into "macro-actions," allowing defenders to compute effective strategies in environments triple the size of what was previously solvable (Automated Abstractions for Patrolling Security Games).
  • Medicine: Tuomas Sandholm has proposed using these same game-theoretic abstractions to treat evolution as an opponent. By grouping billions of possible genetic states into manageable abstractions, researchers can design treatment plans that steer diseases like cancer into "evolutionary traps" (Steering Evolution Strategically).

Real-Time Refinement

Even the best abstraction is still an approximation. To bridge the gap, researchers use subgame refinement. As Matej Moravcik and Martin Schmid describe in Refining Subgames in Large Imperfect Information Games, an agent can use a coarse abstraction for the overall game but "re-solve" the specific subgame it is currently in with much higher precision. This allows the AI to play with the efficiency of a simplified model while maintaining the tactical sharpness of a full-scale solver when it matters most.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_state_abstraction_for_large_imperfect_in_629f5cd0,
  title = {State Abstraction for Large Imperfect Information Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-abstraction-for-large-imperfect-information-games/rdr_629f5cd0f746491dbcf2b3cc582a79d8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_state_abstraction_for_large_imperfect_in_629f5cd0_v1,
  title = {State Abstraction for Large Imperfect Information Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-abstraction-for-large-imperfect-information-games/rdr_629f5cd0f746491dbcf2b3cc582a79d8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}