Safe and Nested Subgame Solving for Imperfect-Information Games

Abstract

In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it by solving individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.

Cited by in corpus (27)

• An Introduction to Image Synthesis with Generative Adversarial Nets
• Learning to run a power network challenge for training topology controllers
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
• RLCard: A Toolkit for Reinforcement Learning in Card Games
• Backplay: "Man muss immer umkehren"
• Learning to run a Power Network Challenge: a Retrospective Analysis
• Single Deep Counterfactual Regret Minimization
• Deep Reinforcement Learning for Green Security Games with Real-Time Information
• Unlocking the Potential of Deep Counterfactual Value Networks
• On the Complexity of Reconnaissance Blind Chess
• Joint Policy Search for Multi-agent Collaboration with Imperfect Information
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond
• Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games
• Building a Computer Mahjong Player via Deep Convolutional Neural Networks
• Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information
• Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning
• Low-Variance and Zero-Variance Baselines for Extensive-Form Games
• Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces
• A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand
• A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
• Sound Algorithms in Imperfect Information Games
• Search in Imperfect Information Games
• Successful Nash Equilibrium Agent for a 3-Player Imperfect-Information Game
• Computing Optimal Coarse Correlated Equilibria in Sequential Games
• Subgame solving without common knowledge
• Towards a Sample Efficient Reinforcement Learning Pipeline for Vision Based Robotics
• Recursive Regret Matching: A General Method for Solving Time-invariant Nonlinear Zero-sum Differential Games