DeepStack: Expert-level artificial intelligence in heads-up no-limit poker

2017/01/06 by Matej Moravčík, Martin Schmid, Neil Burch +7 · 3 voices · 77 citations
Computer Science · Economics, Econometrics and Finance · Psychology · #Artificial Intelligence in Games #Sports Analytics and Performance #Gambling Behavior and Treatments

paper · pdf · doi:10.1126/science.aam6960

Abstract

Artificial intelligence has seen several breakthroughs in recent years, with games often serving as milestones. A common feature of these games is that players have perfect information. Poker, the quintessential game of imperfect information, is a long-standing challenge problem in artificial intelligence. We introduce DeepStack, an algorithm for imperfect-information settings. It combines recursive reasoning to handle information asymmetry, decomposition to focus computation on the relevant decision, and a form of intuition that is automatically learned from self-play using deep learning. In a study involving 44,000 hands of poker, DeepStack defeated, with statistical significance, professional poker players in heads-up no-limit Texas hold'em. The approach is theoretically sound and is shown to produce strategies that are more difficult to exploit than prior approaches.

Citations

• Robust Estimation of a Location Parameter

Cited by

• Student of Games: A unified learning algorithm for both perfect and imperfect information games
• Mastering Atari, Go, chess and shogi by planning with a learned model
• The Hanabi challenge: A new frontier for AI research
• Mastering the game of Stratego with model-free multiagent reinforcement learning
• LeAct: Learning to Reason from Expert Actions
• GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning
• Finding Friend and Foe in Multi-Agent Games
• TSS: Transformation-Specific Smoothing for Robustness Certification
• Selective Dyna-style Planning Under Limited Model Capacity
• Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field\n Control/Game in Continuous Time
• Correlation in Extensive-Form Games: Saddle-Point Formulation and\n Benchmarks
• Hybrid-AIRL: Enhancing Inverse Reinforcement Learning with Supervised Expert Guidance
• DiffFP: Learning Behaviors from Scratch via Diffusion-based Fictitious Play
• α-Rank: Multi-Agent Evaluation by Evolution
• Human-Level Performance in No-Press Diplomacy via Equilibrium Search
• KrwEmd: Revising the Imperfect-Recall Abstraction from Forgetting Everything
• No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding
• Deep (Predictive) Discounted Counterfactual Regret Minimization
• 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
• Quantifying Skill and Chance: A Unified Framework for the Geometry of Games
• Improving Fictitious Play Reinforcement Learning with Expanding Models
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Metaethical perspectives on ‘benchmarking’ AI ethics
• Suphx: Mastering Mahjong with Deep Reinforcement Learning
• Backplay: "Man muss immer umkehren"
• Reinforcement Learning Applications
• BeBold: Exploration Beyond the Boundary of Explored Regions
• First-Order Methods for Large-Scale Market Equilibrium Computation
• VRGym: A Virtual Testbed for Physical and Interactive AI
• OpenSpiel: A Framework for Reinforcement Learning in Games
• Monopoly Deal: A Benchmark Environment for Bounded One-Sided Response Games
• Competitive Policy Optimization
• Confounding Robust Deep Reinforcement Learning: A Causal Approach
• Learning to Play No-Press Diplomacy with Best Response Policy Iteration
• Learning and Planning in Complex Action Spaces
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Shallow Unorganized Neural Networks using Smart Neuron Model for Visual Perception
• On the Universal Near Optimality of Hedge in Combinatorial Settings
• Convergence of Regret Matching in Potential Games and Constrained Optimization
• Beyond Outcome-Based Imperfect-Recall: Higher-Resolution Abstractions for Imperfect-Information Games
• Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Depth-Limited Solving for Imperfect-Information Games
• Algorithms in Multi-Agent Systems: A Holistic Perspective from Reinforcement Learning and Game Theory
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
• Look-ahead Reasoning with a Learned Model in Imperfect Information Games
• Strongly Solving 2048 4x3
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
• On the O(1/T) Convergence of Alternating Gradient Descent-Ascent in Bilinear Games
• Neural Bayesian Filtering
• Sound Algorithms in Imperfect Information Games
• SpinGPT: A Large-Language-Model Approach to Playing Poker Correctly
• Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation
• HSVI for zs-POSGs using Concavity, Convexity and Lipschitz Properties
• SpinGPT: A Large-Language-Model Approach to Playing Poker Correctly
• Efficient representations for team and imperfect-recall equilibrium computation
• Game-Theoretic Multiagent Reinforcement Learning
• Problems with the EFG formalism: a solution attempt using observations
• Understanding and Comparing Deep Neural Networks for Age and Gender\n Classification
• Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning
• Shortcut learning in deep neural networks
• Personal Universes: A Solution to the Multi-Agent Value Alignment Problem
• Dota 2 with Large Scale Deep Reinforcement Learning
• Analysis of Bluffing by DQN and CFR in Leduc Hold'em Poker
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
• AI Testing Should Account for Sophisticated Strategic Behaviour
• Theoretical and Practical Advances on Smoothing for Extensive-Form Games
• Regret Circuits: Composability of Regret Minimizers
• Solving imperfect-information games via exponential counterfactual regret minimization
• Beyond Winning and Losing: Modeling Human Motivations and Behaviors\n Using Inverse Reinforcement Learning
• Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games
• Teaching Temporal Logics to Neural Networks
• Joint Policy Search for Multi-agent Collaboration with Imperfect Information
• Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning
• Monte Carlo Neural Fictitious Self-Play: Approach to Approximate Nash equilibrium of Imperfect-Information Games
• Artificial Generals Intelligence: Mastering Generals.io with Reinforcement Learning
• Generative Reversible Data Hiding by Image to Image Translation via GANs

Discussions

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker [hn, 102 points, 47 comments]
• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker [lobsters, 7 points, 16 comments]
• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker | https://arxiv.org/pdf/1701.01724.pdf [bsky, 0 points, 0 comments]

Related

• DecisionHoldem: Safe Depth-Limited Solving With Diverse Opponents for Imperfect-Information Games
• Most Important Fundamental Rule of Poker Strategy
• Depth-Limited Solving for Imperfect-Information Games
• PokerGPT: An End-to-End Lightweight Solver for Multi-Player Texas Hold'em via Large Language Model
• Student of Games: A unified learning algorithm for both perfect and imperfect information games