Safe and Nested Subgame Solving for Imperfect-Information Games

2017/05/08 by Noam Brown, Tuomas Sandholm, Tüomas Sandholm +2 · 1 voice · 16 citations
Computer Science · Social Sciences · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #Digital Games and Media #FOS: Computer and information sciences #Reinforcement Learning in Robotics #cs.AI #cs.GT

paper · pdf · doi:10.48550/arxiv.1705.02955

openalex publication_date 2017/05/08 · arxiv published 2017/05/08 · arxiv created 2017/11/16 · arxiv updated 2017/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

• Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search
• Outbidding and Outbluffing Elite Humans: Mastering Liar's Poker via Self-Play and Reinforcement Learning
• Beyond Outcome-Based Imperfect-Recall: Higher-Resolution Abstractions for Imperfect-Information Games
• Safety Game: Balancing Safe and Informative Conversations with Blackbox Agentic AI using LP Solvers
• Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation
• Efficient representations for team and imperfect-recall equilibrium computation
• Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information
• Solving imperfect-information games via exponential counterfactual regret minimization
• A Theory of Inference Compute Scaling: Reasoning through Directed Stochastic Skill Search
• Deep Reinforcement Learning for Green Security Games with Real-Time Information
• Confucius3-Math: A Lightweight High-Performance Reasoning LLM for Chinese K-12 Mathematics Learning
• Smoothing Method for Approximate Extensive-Form Perfect Equilibrium
• Learning to run a power network challenge for training topology controllers
• General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess
• Practical Scalability for Stackelberg Security Games
• GTO Wizard Benchmark

Discussions

• Safe and Nested Subgame Solving for Imperfect-Information Games [pdf] [hn, 2 points, 1 comments]

Related

• Subgame solving without common knowledge
• Depth-Limited Solving for Imperfect-Information Games
• Student of Games: A unified learning algorithm for both perfect and imperfect information games
• No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding
• DecisionHoldem: Safe Depth-Limited Solving With Diverse Opponents for Imperfect-Information Games