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. G ames have long served as benchmarks of progress in artificial intelligence (AI). In the past two decades, computer programs have reached a performance that exceeds that of expert human players in games such as backgammon (1), checkers (2), chess (3), Jeopardy! (4), Atari video games (5), and go (6). These successes all involve games with information symmetry, where all players have identical information about the current state of the game. This property of perfect information is also at the heart of the algorithms that enabled these successes, such as local search during play (7, 8) . John von Neumann, the founder of modern game theory and computing pioneer, envisioned reasoning in games without perfect information: "Real life is not like that. Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do. And that is what games are about in my theory" (9). One game that fascinated von Neumann was poker, where players are dealt private cards and take turns making bets or bluffing on holding the strongest hand, calling opponents' bets, or folding and giving up on the hand and the bets already added to the pot. Poker is a game of imperfect information, where players' private cards give them asymmetric information about the state of the game. Heads-up no-limit Texas hold'em (HUNL) is a two-player version of poker in which two cards are initially dealt face down to each player, and additional cards are dealt face up in three subsequent rounds. No limit is placed on the size of the bets, although there is an overall limit to the total amount wagered in each game (10). AI techniques have previously shown success in the simpler game of heads-up limit Texas hold'em, where all bets are of a fixed size, resulting in just under 10 14 decision points (11). By comparison, computers have exceeded expert human performance in go (6), a perfect-information game with approximately 10 170 decision points (12). The imperfect-information game HUNL is comparable in size to go, with the number of decision points exceeding 10 160 (13). Imperfect-information games require more complex reasoning than similarly sized perfectinformation games. The correct decision at a particular moment depends on the probability distribution over private information that an opponent holds, which is revealed through the opponent's past actions. However, the way in which that information is revealed depends on the opponent's knowledge of our own private information and how our actions reveal it. This kind of recursive reasoning is why one cannot easily reason about game situations in isolation, as in heuristic search methods used in perfect-information games. Competitive AI approaches in imperfectinformation games typically reason about the entire game and produce a complete strategy before play begins (14-16). Counterfactual regret minimization (CFR) (14, 17, 18 ) is one such technique in which a program uses self-play to do recursive reasoning through adapting its strategy against itself over successive iterations. If the game is too large to be solved directly, the common response is to solve a smaller, abstract game. To play the original game, one translates situations and actions from the original game to the abstract game. Although this approach makes it feasible for programs to reason in a game such as HUNL, it does so by squeezing HUNL's 10 160 situations down to the order of 10 14 abstract situations. Likely as a result of this loss of information, such programs are behind expert human play. In 2015, the computer program Claudico lost to a team of professional poker players by a margin of 91 milli-big blinds per game (mbb/g) (19), which is a "huge margin of victory" (20). Furthermore, it was recently shown that abstractionbased programs from the Annual Computer Poker Competition have massive flaws (21). Four such programs (including top programs from the 2016 competition) were evaluated using a local best response technique that produces an approximate lower bound on how much a strategy can lose. All four abstraction-based programs are beatable by more than 3000 mbb/g, whereas simply folding each game results in 750 mbb/g. DeepStack takes a fundamentally different approach. It continues to use the recursive reasoning of CFR to handle information asymmetry. However, it does not compute and store a complete strategy prior to play and so has no need for explicit abstraction. Instead, it considers each particular situation as it arises during play, but not in isolation. It avoids reasoning about the entire remainder of the game by substituting the computation beyond a certain depth with a fast approximate estimate. This estimate can be thought of as DeepStack's intuition: a gut feeling of the value of holding any possible private cards in any possible poker situation. Finally, DeepStack's intuition, much like human intuition, needs to be trained. We train it with deep learning (22), using examples generated from random poker situations. We show that DeepStack is theoretically sound, produces strategies substantially more difficult to exploit than abstraction-based techniques, and defeats professional poker players at HUNL with statistical significance. DeepStack is a general-purpose algorithm for a large class of sequential imperfect-information games. For clarity, we describe its operation in the game of HUNL. The state of a poker game can be split into the players' private information-hands of two cards dealt face down-and the public state, which consists of the cards lying face up on the table and the sequence of betting actions made by the players. Possible sequences of public states in the game form a public tree, with every public state having an associated public subtree (Fig. 1) . A player's strategy defines a probability distribution over valid actions for each decision point, where a decision point is the combination of the public state and the hand for the acting player. Given a player's strategy, for any public state one can compute the player's range, which is the probability distribution over the player's possible hands given that the public state is reached. Given strategies for both players, the utility for one of the players at a terminal public state, where the game has ended, is a bilinear function of both players' ranges using a payoff matrix determined by the rules of the game. The expected utility for a player at any other public state, including the initial state, is the expected utility over reachable
Past work has investigated using deep learning to estimate values at the depth limit of a subgame in imperfect-information games REF .
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
Science
Computer Science Medicine