Search in Imperfect Information Games

2021/11/10 by Martin Schmid, Schmid, Martin · 1 citation
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #FOS: Computer and information sciences #Reinforcement Learning in Robotics #Sports Analytics and Performance #cs.AI

paper · pdf · doi:10.48550/arxiv.2111.05884

doctoral thesis

arxiv created 2021/11/10 · openalex publication_date 2021/11/10 · arxiv updated 2021/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Fast Convergence of Regularized Learning in Games
• Adam: A Method for Stochastic Optimization
• Solving Large Imperfect Information Games Using CFR+
• A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
• The Complexity of Computing a Nash Equilibrium
• Robust Estimation of a Location Parameter
• Zur Theorie der Gesellschaftsspiele
• Deep Learning in Neural Networks: An Overview
• A Markovian Decision Process
• The Complexity of Decentralized Control of Markov Decision Processes
• The Lack of A Priori Distinctions Between Learning Algorithms
• Bayes' Bluff: Opponent Modelling in Poker
• Planning and acting in partially observable stochastic domains
• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Double Neural Counterfactual Regret Minimization
• Deep Blue
• Single Deep Counterfactual Regret Minimization
• Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games
• Problems with the EFG formalism: a solution attempt using observations
• AIVAT: A New Variance Reduction Technique for Agent Evaluation in Imperfect Information Games
• A Generalized Training Approach for Multiagent Learning
• Dota 2 with Large Scale Deep Reinforcement Learning
• Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
• XDO: A Double Oracle Algorithm for Extensive-Form Games

Cited by

• AI Agents for the Dhumbal Card Game: A Comparative Study
• Human-Level Competitive Pokémon via Scalable Offline Reinforcement Learning with Transformers

Related

• General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess
• Study and improvement of search algorithms in two-players perfect information games
• Information and Search in Computer Chess
• Sound Algorithms in Imperfect Information Games
• Look-ahead Search on Top of Policy Networks in Imperfect Information Games