DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
By Matej Moravcík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Bradley Johanson, Michael H. Bowling. 2017
1,018 citations recorded by the source corpus.
Computer code based on continual problem re-solving beats human professional poker players at a two-player variant of poker. Artificial intelligence masters poker Computers can beat humans at games as complex as chess or go. In these and similar games, both players have access to the same information, as displayed on the board. Although computers have the ultimate poker face, it has been tricky to teach them to be good at poker, where players cannot see their opponents' cards. Moravčík et al. built a code dubbed DeepStack that managed to beat professional poker players at a two-player poker variant called heads-up no-limit Texas hold'em. Instead of devising its strategy beforehand, DeepStack recalculated it at each step, taking into account the current state of the game. The principles behind DeepStack may enable advances in solving real-world problems that involve information asymmetry. Science, this issue p. 508 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.
Subfields: Artificial Intelligence, Clinical Psychology, Economics and Econometrics, Reinforcement Learning, Game & Decision Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yoshua Bengio
- Mohit Bansal
- Pieter Abbeel
- Quoc V. Le
- Ruslan Salakhutdinov
- Jianfeng Gao
- Percy Liang
In Clinical Psychology
- Neil Burch
- Jakob N. Foerster
- Hengyuan Hu
- Zhuoran Yang
- Adam Lerer
- Michael H. Bowling
- Vojtěch Kovařík
- Viliam Lisý
In Economics and Econometrics
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Yuxi Li
- Shimon Whiteson
- Chelsea Finn
- Timothy P. Lillicrap
- Jakob N. Foerster
- David Silver
In Game & Decision Theory
- Karl Tuyls
- Noam Brown
- Tuomas Sandholm
- Marc Lanctot
- Julien Pérolat
- Neil Burch
- Zhuoran Yang
- Jakob N. Foerster
Citations in the corpus
- Privacy Risks of Securing Machine Learning Models against Adversarial Examples (2019, background): “Machine learning models, especially deep neural networks, have been deployed prominently in many real-world applications, such as image classification [28, 49], speech recognition [11, 21], natural language processing [2, 10], and game playing [35, 48].”
- Counterfactuals in Explainable Artificial Intelligence (XAI): Evidence from Human Reasoning (2019, background): “For example, “counterfactual regret minimization” ensures a deep learning algorithm adapts its strategy over successive iterations in self-play, by assigning values to reflect an opponent’s hand using “deep counterfactual value networks” [Moravčík et al., 2017].”
- Dota 2 with Large Scale Deep Reinforcement Learning (2019, background): “Where many reinforcement learning environment episodes last hundreds of steps ([4, 29–31]), games of Dota 2 can last for tens of thousands of time steps.”
- Relational inductive biases, deep learning, and graph networks (2018, background): “…domains, from image classification (Krizhevsky et al., 2012; Szegedy et al., 2017), to natural language processing (Sutskever et al., 2014; Bahdanau et al., 2015), to game play (Mnih et al., 2015; Silver et al., 2016; Moravˇc´ık et al., 2017), are a testament to this minimalist principle.”
- Striving for Simplicity in Off-policy Deep Reinforcement Learning (2019, background): “Recent progress in mastering the games of Go [50] and Poker [43, 10] and advances in robotic control [36, 44, 30] present additional supporting evidence for the enormous potential of deep RL.”
- Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, background): “…component for achieving superhu-man performance in a number of hard benchmark problems in AI, including Go (Silver et al., 2016; 2017; 2018), Chess (Campbell et al., 2002), Poker (Moravˇc´ık et al., 2017; Brown & Sandholm, 2017; 2019), and, more recently, self-play Hanabi (Lerer et al., 2020).”
- The Hanabi Challenge: A New Frontier for AI Research (2019, methodology): “Lastly, an approach in poker (DeepStack) introduced function approximators that represent belief-conditional values and explicitly representing and reasoning about manipulating agents’ beliefs [13], similar to the approach of BAD [38].”
- Online Fast Adaptation and Knowledge Accumulation: a New Approach to Continual Learning (2020, background): “For example, the context variable could be the strategy of an opponent in a game [69, 49, 77, 51], regimes in time-series forecasting [56, 19, 9] or the mood of a user when navigating a content platform in recommender systems [25, 72].”
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, methodology): “In our Leduc Poker experiments, we use an alternating implementation that switches periodically between computing the best response (oracle training phase) and meta-strategy learning phase where the empirical payoff tensor is updated and meta-strategy computed.”
- Human-level performance in 3D multiplayer games with population-based reinforcement learning (2018, background): “In contrast to previous work ( 18, 41, 42, 47, 48, 53, 58, 63, 64 ), agents do not have access to models of the environment, other agents, or human policy priors, nor can they communicate with each other outside of the game environment.”