# Subgame solving without common knowledge

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2021.

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

- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Policy Space Diversity for Non-Transitive Games](https://mlsanity.com/paper/2306.16884/) (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)
- [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)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Look-ahead Reasoning with a Learned Model in Imperfect Information Games](https://mlsanity.com/paper/2510.05048/) (2025)
- [Safe Subgame Resolving for Extensive Form Correlated Equilibrium](https://mlsanity.com/paper/2212.14317/) (2022)
- [Perfect Information Monte Carlo with Postponing Reasoning](https://mlsanity.com/paper/2408.02380/) (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)

## Abstract (arXiv)

In imperfect-information games, subgame solving is significantly more challenging than in perfect-information games, but in the last few years, such techniques have been developed. They were the key ingredient to the milestone of superhuman play in no-limit Texas hold'em poker. Current subgame-solving techniques analyze the entire common-knowledge closure of the player's current information set, that is, the smallest set of nodes within which it is common knowledge that the current node lies. While this is acceptable in games like poker where the common-knowledge closure is relatively small, many practical games have more complex information structure, which renders the common-knowledge closure impractically large to enumerate or even reasonably approximate. We introduce an approach that overcomes this obstacle, by instead working with only low-order knowledge. Our approach allows an agent, upon arriving at an infoset, to basically prune any node that is no longer reachable, thereby massively reducing the game tree size relative to the common-knowledge subgame. We prove that, as is, our approach can increase exploitability compared to the blueprint strategy. However, we develop three avenues by which safety can be guaranteed. Even without the safety-guaranteeing additions, experiments on medium-sized games show that our approach always reduced exploitability in practical games even when applied at every infoset, and a depth-limited version of it led to -- to our knowledge -- the first strong AI for the challenge problem dark chess.