# Search in Imperfect Information Games

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 163 references that are in the map.
- First posted on arXiv 10 Nov 2021.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [The Mirage of Action-Dependent Baselines in Reinforcement Learning](https://mlsanity.com/paper/1802.10031/) (2018)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [DREAM: Deep Regret minimization with Advantage baselines and Model-free learning](https://mlsanity.com/paper/2006.10410/) (2020)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Approximate exploitability: Learning a best response in large games](https://mlsanity.com/paper/2004.09677/) (2020)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Single Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1901.07621/) (2019)
- [The Advantage Regret-Matching Actor-Critic](https://mlsanity.com/paper/2008.12234/) (2020)
- [Double Neural Counterfactual Regret Minimization](https://mlsanity.com/paper/1812.10607/) (2018)
- [Measuring the Size of Large No-Limit Poker Games](https://mlsanity.com/paper/1302.7008/) (2013)
- [Unlocking the Potential of Deep Counterfactual Value Networks](https://mlsanity.com/paper/2007.10442/) (2020)
- [Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games](https://mlsanity.com/paper/1812.07351/) (2018)
- [Problems with the EFG formalism: a solution attempt using observations](https://mlsanity.com/paper/1906.06291/) (2019)
- [Safe Search for Stackelberg Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2102.01775/) (2021)
- [Value Functions for Depth-Limited Solving in Zero-Sum Imperfect-Information Games](https://mlsanity.com/paper/1906.06412/) (2019)
- [Sound Algorithms in Imperfect Information Games](https://mlsanity.com/paper/2006.08740/) (2020)

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

- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Play](https://mlsanity.com/paper/2303.04096/) (2023)
- [Large Language Models as Agents in Two-Player Games](https://mlsanity.com/paper/2402.08078/) (2024)
- [HSVI can solve zero-sum Partially Observable Stochastic Games](https://mlsanity.com/paper/2210.14640/) (2022)
- [Human-Level Competitive Pok'emon via Scalable Offline Reinforcement Learning with Transformers](https://mlsanity.com/paper/2504.04395/) (2025)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Learning not to Regret](https://mlsanity.com/paper/2303.01074/) (2023)
- [AI Agents for the Dhumbal Card Game: A Comparative Study](https://mlsanity.com/paper/2510.11736/) (2025)

## Abstract (arXiv)

From the very dawn of the field, search with value functions was a fundamental concept of computer games research. Turing's chess algorithm from 1950 was able to think two moves ahead, and Shannon's work on chess from 1950 includes an extensive section on evaluation functions to be used within a search. Samuel's checkers program from 1959 already combines search and value functions that are learned through self-play and bootstrapping. TD-Gammon improves upon those ideas and uses neural networks to learn those complex value functions -- only to be again used within search. The combination of decision-time search and value functions has been present in the remarkable milestones where computers bested their human counterparts in long standing challenging games -- DeepBlue for Chess and AlphaGo for Go. Until recently, this powerful framework of search aided with (learned) value functions has been limited to perfect information games. As many interesting problems do not provide the agent perfect information of the environment, this was an unfortunate limitation. This thesis introduces the reader to sound search for imperfect information games.