Search in Imperfect Information Games
arXiv:2111.05884
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 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.
arXiv commentdoctoral thesis
References in corpus (30)
- Adam: A Method for Stochastic Optimization
- Deep Learning in Neural Networks: An Overview
- Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
- Dota 2 with Large Scale Deep Reinforcement Learning
- DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
- Bayes' Bluff: Opponent Modelling in Poker
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
- RUDDER: Return Decomposition for Delayed Rewards
- Safe and Nested Subgame Solving for Imperfect-Information Games
- A parameter-free hedging algorithm
- The Mirage of Action-Dependent Baselines in Reinforcement Learning
- Depth-Limited Solving for Imperfect-Information Games
- Solving Large Imperfect Information Games Using CFR+
- A Generalized Training Approach for Multiagent Learning
- Deep Counterfactual Regret Minimization
- Finding Friend and Foe in Multi-Agent Games
- Equilibrium Approximation Quality of Current No-Limit Poker Bots
- From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
- Double Neural Counterfactual Regret Minimization
- Single Deep Counterfactual Regret Minimization
- DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
- Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
- Unlocking the Potential of Deep Counterfactual Value Networks
- AIVAT: A New Variance Reduction Technique for Agent Evaluation in Imperfect Information Games
- The Advantage Regret-Matching Actor-Critic
- XDO: A Double Oracle Algorithm for Extensive-Form Games
- Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games
- Approximate exploitability: Learning a best response in large games
- Problems with the EFG formalism: a solution attempt using observations
- Small Nash Equilibrium Certificates in Very Large Games