DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
arXiv:1701.01724 · 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 is the quintessential game of imperfect information, and a longstanding 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 more difficult to exploit strategies than prior approaches.
References in corpus (4)
Cited by in corpus (126)
- T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction
- Shortcut Learning in Deep Neural Networks
- Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model
- Dota 2 with Large Scale Deep Reinforcement Learning
- Unmasking Clever Hans Predictors and Assessing What Machines Really Learn
- DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
- Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
- A Survey and Critique of Multiagent Deep Reinforcement Learning
- Towards Explainable Artificial Intelligence
- Opportunities and Challenges for Machine Learning in Materials Science
- Deep Learning for Real-time Gravitational Wave Detection and Parameter Estimation: Results with Advanced LIGO Data
- Compute Trends Across Three Eras of Machine Learning
- The Hanabi Challenge: A New Frontier for AI Research
- Cooperating with Machines
- Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning
- Game-Theoretic Multiagent Reinforcement Learning
- OpenSpiel: A Framework for Reinforcement Learning in Games
- Bottom-up and top-down approaches for the design of neuromorphic processing systems: Tradeoffs and synergies between natural and artificial intelligence
- How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review
- Suphx: Mastering Mahjong with Deep Reinforcement Learning
- Finding Effective Security Strategies through Reinforcement Learning and Self-Play
- Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
- Single-step deep reinforcement learning for open-loop control of laminar and turbulent flows
- Learning with AMIGo: Adversarially Motivated Intrinsic Goals
- Reinforcement Learning Applications
- Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning
- Distributed Deep Reinforcement Learning: A Survey and A Multi-Player Multi-Agent Learning Toolbox
- AI in Human-computer Gaming: Techniques, Challenges and Opportunities
- Understanding and Comparing Deep Neural Networks for Age and Gender Classification
- At Human Speed: Deep Reinforcement Learning with Action Delay
- Backplay: "Man muss immer umkehren"
- Deep Counterfactual Regret Minimization
- Mimetic Models: Ethical Implications of AI that Acts Like You
- Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
- Learning to Play No-Press Diplomacy with Best Response Policy Iteration
- BeBold: Exploration Beyond the Boundary of Explored Regions
- Finding Friend and Foe in Multi-Agent Games
- Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
- A Maintenance Planning Framework using Online and Offline Deep Reinforcement Learning
- No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
- Learning to Combat Compounding-Error in Model-Based Reinforcement Learning
- Improving Search with Supervised Learning in Trick-Based Card Games
- Concurrent Meta Reinforcement Learning
- First-Order Methods for Large-Scale Market Equilibrium Computation
- Student of Games: A unified learning algorithm for both perfect and imperfect information games
- Online Fast Adaptation and Knowledge Accumulation: a New Approach to Continual Learning
- Single Deep Counterfactual Regret Minimization
- Algorithms in Multi-Agent Systems: A Holistic Perspective from Reinforcement Learning and Game Theory
- World Discovery Models
- Personal Universes: A Solution to the Multi-Agent Value Alignment Problem
- Neural Replicator Dynamics
- MADE: Exploration via Maximizing Deviation from Explored Regions
- Learning and Planning in Complex Action Spaces
- Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks
- DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
- Human-Level Performance in No-Press Diplomacy via Equilibrium Search
- Unlocking the Potential of Deep Counterfactual Value Networks
- Solving imperfect-information games via exponential counterfactual regret minimization
- AndroidEnv: A Reinforcement Learning Platform for Android
- The Advantage Regret-Matching Actor-Critic
- Robust Opponent Modeling via Adversarial Ensemble Reinforcement Learning in Asymmetric Imperfect-Information Games
- Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence
- Generosity, selfishness and exploitation as optimal greedy strategies for resource sharing
- Model-free Neural Counterfactual Regret Minimization with Bootstrap Learning
- Joint Policy Search for Multi-agent Collaboration with Imperfect Information
- Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field Control/Game in Continuous Time
- Enabling Multi-Agent Transfer Reinforcement Learning via Scenario Independent Representation
- TSS: Transformation-Specific Smoothing for Robustness Certification
- Scalable Online Planning via Reinforcement Learning Fine-Tuning
- Beyond Winning and Losing: Modeling Human Motivations and Behaviors Using Inverse Reinforcement Learning
- Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
- Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games
- Stochastic Regret Minimization in Extensive-Form Games
- Combinational Q-Learning for Dou Di Zhu
- Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games
- Selective Dyna-style Planning Under Limited Model Capacity
- Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond
- Monte Carlo Neural Fictitious Self-Play: Approach to Approximate Nash equilibrium of Imperfect-Information Games
- Last-iterate Convergence in Extensive-Form Games
- Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games
- Teaching Temporal Logics to Neural Networks
- Learning in Quantum Common-Interest Games and the Separability Problem
- Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning
- Deep Latent Competition: Learning to Race Using Visual Control Policies in Latent Space
- PokerKit: A Comprehensive Python Library for Fine-Grained Multi-Variant Poker Game Simulations
- Low-Variance and Zero-Variance Baselines for Extensive-Form Games
- Approximate exploitability: Learning a best response in large games
- Bounds for Approximate Regret-Matching Algorithms
- Generative Reversible Data Hiding by Image to Image Translation via GANs
- Problems with the EFG formalism: a solution attempt using observations
- Alternative Function Approximation Parameterizations for Solving Games: An Analysis of -Regression Counterfactual Regret Minimization
- Competitive Policy Optimization
- Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings
- CFR-MIX: Solving Imperfect Information Extensive-Form Games with Combinatorial Action Space
- Neural Network-based Information Set Weighting for Playing Reconnaissance Blind Chess
- Dual policy as self-model for planning
- Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
- Sound Algorithms in Imperfect Information Games
- Small Nash Equilibrium Certificates in Very Large Games
- Shallow Unorganized Neural Networks using Smart Neuron Model for Visual Perception
- Most Important Fundamental Rule of Poker Strategy
- Theoretical and Practical Advances on Smoothing for Extensive-Form Games
- Mixture of Public and Private Distributions in Imperfect Information Games
- Search in Imperfect Information Games
- Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies
- Learning to Play Imperfect-Information Games by Imitating an Oracle Planner
- Conscious Intelligence Requires Lifelong Autonomous Programming For General Purposes
- Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games
- Sim-to-Real Optimization of Complex Real World Mobile Network with Imperfect Information via Deep Reinforcement Learning from Self-play
- Improving Fictitious Play Reinforcement Learning with Expanding Models
- VRGym: A Virtual Testbed for Physical and Interactive AI
- Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
- BridgeHand2Vec Bridge Hand Representation
- Computing Human-Understandable Strategies
- Post-Selections in AI and How to Avoid Them
- Subgame solving without common knowledge
- Iconary: A Pictionary-Based Game for Testing Multimodal Communication with Drawings and Text
- Recording and Describing Poker Hands
- Perfect Information Monte Carlo with Postponing Reasoning
- Empirical Validation of the Independent Chip Model
- Strongly Solving 2048 4x3
- Efficient representations for team and imperfect-recall equilibrium computation
- Going Beyond Linear RL: Sample Efficient Neural Function Approximation
- Improving Social Welfare While Preserving Autonomy via a Pareto Mediator
- Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess
- Learning Representations by Stochastic Meta-Gradient Descent in Neural Networks