In perfect-information games like Chess or Go, every player knows the exact state of the board at any given moment. This transparency allows AI agents to use localized look-ahead search algorithms (like minimax or Monte Carlo Tree Search) to evaluate independent subtrees of the game.
However, when critical information is hidden—such as the cards in an opponent's hand in poker, or private assets in a negotiation—traditional search algorithms break down completely. In these imperfect-information environments, players face hidden state uncertainty, meaning they do not know their exact location within the game tree. As a result, moves cannot be evaluated in isolation; a strategy at any single point depends on the strategies deployed across all other potential paths of play.
The Failure of Local Search and the Trap of Strategy Fusion
To understand why imperfect-information games are uniquely challenging, consider the foundational work by Daphne Koller et al. in Generating and Solving Imperfect Information Games. They noted that standard look-ahead techniques cannot isolate and solve specific subtrees in real time because the lack of a single known game state prevents agents from determining where their search should even begin.
A naive attempt to bypass this challenge is determinization: sampling a specific hidden state (e.g., guessing the opponent's exact cards) and running a standard perfect-information search on that concrete scenario. While intuitive, this approach suffers from a fatal flaw known as strategy fusion.
Strategy fusion occurs when an agent incorrectly assumes it can tailor its future moves to information it does not yet possess. By treating multiple distinct, unobservable states as if they were a single state with perfect information, the agent builds an unrealistic strategy. For instance, it might choose an action that is optimal only if it can perfectly guess the opponent's cards in the next round, failing to find a robust strategy that accounts for ongoing uncertainty.
Shifting from States to Information Sets
To overcome strategy fusion, algorithms must operate not on individual game states, but on information sets. An information set is a collection of all possible game states that are completely indistinguishable to a player based on their private knowledge and the public history of actions.
Instead of searching a tree of states, the agent searches a tree of information sets. This ensures that any decision made at a given point is identical for all underlying states within that set, naturally enforcing the physical constraints of the game. However, because information sets group states together, the choices made in one part of the game tree alter the probabilities of being in specific states in another part of the tree. This interdependence requires a global approach to optimization.
Counterfactual Regret Minimization
The breakthrough framework for optimizing over information sets is Counterfactual Regret Minimization (CFR), introduced by Martin Zinkevich et al. in Regret Minimization in Games with Incomplete Information.
The core intuition behind CFR is to evaluate decisions through a "counterfactual" lens: What would have happened if I had chosen a different action at an information set, assuming I played perfectly to reach that point?
The algorithm operates through iterative self-play:
- Compute Counterfactual Values: For a given information set, the agent calculates the expected payoff for taking a specific action, weighted by the probability that the opponent's strategy would allow this information set to be reached.
- Accumulate Regret: The agent subtracts the actual payoff received from the counterfactual payoff of the alternative action. If the alternative would have yielded a better outcome, the agent accumulates positive "regret" for not choosing it.
- Update Strategy via Regret Matching: In the next iteration, the agent selects actions with a probability proportional to their positive accumulated regret. Actions that caused high regret are prioritized, while actions with zero or negative regret are avoided.
By minimizing counterfactual regret at every information set across the entire game tree, the average strategy profile is mathematically guaranteed to converge toward a Nash Equilibrium—a state where no player can improve their outcome by unilaterally changing their strategy.
Taming Massive State Spaces
While tabular CFR works perfectly for small games, full-scale strategic environments are far too large to solve directly. For example, Heads-Up No-Limit Texas Hold'em contains roughly $10^{161}$ decision points. Researchers have developed two primary mechanisms to scale information-set reasoning to these massive spaces: abstraction and real-time subgame solving.
1. Abstraction and Bucketing
Early breakthroughs relied on compressing the game tree before running regret minimization. Jiefu Shi et al. demonstrated in Towards Approximately Optimal Poker that grouping similar hands into coarse "bins" or "buckets" allows solvers to compute near-optimal strategies using a fraction of the computational resources. This concept was expanded by Darse Billings et al. in Approximating Game-Theoretic Optimal Strategies for Full-scale Poker to compress state spaces by orders of magnitude, enabling the creation of competitive, pseudo-optimal agents. By solving the game at a lower resolution, the agent can still capture essential strategic concepts like bluffing and slow-playing.
2. Real-Time Subgame Solving
For complex, unconstrained games, abstraction alone is insufficient. To achieve superhuman performance, modern architectures combine a coarse, global "blueprint" strategy with real-time, localized refinement.
In Libratus: The Superhuman AI for No-Limit Poker, Noam Brown et al. introduced "nested" subgame solving. Instead of relying purely on a precomputed blueprint, the agent dynamically solves the specific subgame it is currently playing in real time.
Crucially, this real-time lookahead must be handled with care. Christian Kroer et al. proved in Limited Lookahead in Imperfect-Information Games that imperfect-information games exhibit a "lookahead pathology": looking further ahead using naive heuristic evaluations can actually lead to worse performance. Because an opponent's internal evaluation metrics are hidden, a rational player cannot easily model a truncated decision-making process. Christian Kroer demonstrated that to safely look ahead, subgame strategies must remain strictly coordinated with the global blueprint to ensure that real-time adjustments do not inadvertently leak private information through observable actions.
Through the combination of information-set tracking, counterfactual regret tracking, and safe subgame search, modern AI can navigate hidden state uncertainty, transforming seemingly unpredictable environments into mathematically solvable domains.
Key Foundational Work
Generating and Solving Imperfect Information Games (1995) — contributed 4 concept elements to this direction.