# Solving Imperfect Information Games Using Decomposition

arXiv: https://arxiv.org/abs/1303.4441 · HTML: https://mlsanity.com/paper/1303.4441/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2013.

## Built on by (most cited first, 29 of 29)

- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning](https://mlsanity.com/paper/2403.04344/) (2024)
- [HSVI can solve zero-sum Partially Observable Stochastic Games](https://mlsanity.com/paper/2210.14640/) (2022)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)
- [General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess](https://mlsanity.com/paper/2506.01242/) (2025)
- [Real-Time Parallel Counterfactual Regret Minimization](https://mlsanity.com/paper/2605.19928/) (2026)
- [Safe Search for Stackelberg Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2102.01775/) (2021)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learning](https://mlsanity.com/paper/2310.04796/) (2023)
- [Adapting Beyond the Depth Limit: Counter Strategies in Large Imperfect Information Games](https://mlsanity.com/paper/2501.10464/) (2025)
- [Look-ahead Reasoning with a Learned Model in Imperfect Information Games](https://mlsanity.com/paper/2510.05048/) (2025)
- [AI in Human-computer Gaming: Techniques, Challenges and Opportunities](https://mlsanity.com/paper/2111.07631/) (2021)
- [CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjong](https://mlsanity.com/paper/2307.12087/) (2023)
- [Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games](https://mlsanity.com/paper/2507.19263/) (2025)
- [Game of Thought: Robust Information Seeking with Large Language Models Using Game Theory](https://mlsanity.com/paper/2602.01708/) (2026)
- [Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms](https://mlsanity.com/paper/2112.10890/) (2021)
- [Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations](https://mlsanity.com/paper/2307.12062/) (2023)
- [HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2404.10679/) (2024)
- [Perfect Information Monte Carlo with Postponing Reasoning](https://mlsanity.com/paper/2408.02380/) (2024)
- [GPU-Accelerated Counterfactual Regret Minimization](https://mlsanity.com/paper/2408.14778/) (2024)
- [Approximate State Abstraction for Markov Games](https://mlsanity.com/paper/2412.15877/) (2024)
- [OpenGuanDan: A Large-Scale Imperfect Information Game Benchmark](https://mlsanity.com/paper/2602.00676/) (2026)
- [Test-time Reinforcement Learning in Imperfect Information Games](https://mlsanity.com/paper/2608.30635/) (2026)
- [GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay](https://mlsanity.com/paper/2609.11923/) (2026)
- [SafeAdapt-Poker: Counterfactual Risk Calibration for Budgeted Adaptation under Opponent Shift](https://mlsanity.com/paper/2610.20473/) (2026)

## Abstract (arXiv)

Decomposition, i.e. independently analyzing possible subgames, has proven to be an essential principle for effective decision-making in perfect information games. However, in imperfect information games, decomposition has proven to be problematic. To date, all proposed techniques for decomposition in imperfect information games have abandoned theoretical guarantees. This work presents the first technique for decomposing an imperfect information game into subgames that can be solved independently, while retaining optimality guarantees on the full-game solution. We can use this technique to construct theoretically justified algorithms that make better use of information available at run-time, overcome memory or disk limitations at run-time, or make a time/space trade-off to overcome memory or disk limitations while solving a game. In particular, we present an algorithm for subgame solving which guarantees performance in the whole game, in contrast to existing methods which may have unbounded error. In addition, we present an offline game solving algorithm, CFR-D, which can produce a Nash equilibrium for a game that is larger than available storage.