mlsanityData to 7 Oct 2026

Search in Imperfect Information Games

arXiv 2111.05884 ↗First posted 10 Nov 2021cs.AIcited by 8

Not on the map. Why?

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.

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

Builds on

31 of 163 references.

References · 31

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  3. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  4. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  5. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  6. 2018RUDDER: Return Decomposition for Delayed Rewardscited by 162
  7. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  8. 2018Deep Counterfactual Regret Minimizationcited by 102
  9. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  10. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  11. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  12. 2019A Generalized Training Approach for Multiagent Learningcited by 53
19 more
  1. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  2. 2018The Mirage of Action-Dependent Baselines in Reinforcement Learningcited by 46
  3. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  4. 2019Rethinking Formal Models of Partially Observable Multiagent Decision Makingcited by 35
  5. 2021XDO: A Double Oracle Algorithm for Extensive-Form Gamescited by 34
  6. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 25
  7. 2020Approximate exploitability: Learning a best response in large gamescited by 23
  8. 2018Online Convex Optimization for Sequential Decision Processes and Extensive-Form Gamescited by 21
  9. 2019Single Deep Counterfactual Regret Minimizationcited by 20
  10. 2020The Advantage Regret-Matching Actor-Criticcited by 17
  11. 2018Double Neural Counterfactual Regret Minimizationcited by 16
  12. 2013Measuring the Size of Large No-Limit Poker Gamescited by 14
  13. 2020Unlocking the Potential of Deep Counterfactual Value Networkscited by 8
  14. 2018Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Gamescited by 7
  15. 2019Problems with the EFG formalism: a solution attempt using observationscited by 3
  16. 2021Safe Search for Stackelberg Equilibria in Extensive-Form Gamescited by 3
  17. 2019Value Functions for Depth-Limited Solving in Zero-Sum Imperfect-Information Gamescited by 2
  18. 2020Sound Algorithms in Imperfect Information Gamescited by 2
  19. 2020Small Nash Equilibrium Certificates in Very Large Gamescited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 2; 2024: 1; 2025: 2.

8 papers.

  1. 2021Student of Games: A unified learning algorithm for both perfect and imperfect information gamescited by 22
  2. 2023Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Playcited by 10
  3. 2024Large Language Models as Agents in Two-Player Gamescited by 10
  4. 2022HSVI can solve zero-sum Partially Observable Stochastic Gamescited by 8
  5. 2025Human-Level Competitive Pok'emon via Scalable Offline Reinforcement Learning with Transformerscited by 4
  6. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  7. 2023Learning not to Regretcited by 2
  8. 2025AI Agents for the Dhumbal Card Game: A Comparative Studycited by 0