PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker

Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, Michael Bowling

arXiv:1701.01724v3cs.AI

TL;DR

Poker is a longstanding imperfect-information challenge for artificial intelligence. DeepStack uses continual re-solving, depth-limited lookahead, and learned value functions, and it defeated professional heads-up no-limit Texas hold’em players with statistical significance.

  • Problem

    Poker poses a longstanding artificial-intelligence challenge because players act under imperfect information.

  • Method

    DeepStack combines sound local strategy computation, continual re-solving, depth-limited lookahead with a learned value function, and restricted lookahead actions.

  • Results

    44,852 games were played, and DeepStack won 492 mbb/g overall, more than four standard deviations from zero; it defeated professional poker players with statistical significance.

  • Takeaways & Limitations

    DeepStack focuses computation on situations that arise during decisions and uses automatically trained value functions, shifting beyond offline computation of complete strategies.

  • Takeaways & Limitations

    The reported analysis assumes the opponent uses a best response, while a comparable 100-big-blind strategy required almost 2TB of memory and approximately 14 CPU years to solve.

Abstract

from arXiv · show

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.

DeepStack

DeepStack computes local strategies during play for the public states that arise, combining continual re-solving, depth-limited learned values, and sparse action trees. This design addresses recursive reasoning in imperfect-information poker while retaining a theoretical approximation guarantee before action sparsification.

  • DeepStack: DeepStack computes an approximate low-exploitability strategy only for public-tree states that arise during play.It produces a stochastic action distribution through deterministic computation rather than storing a complete game strategy.
  • DeepStack: The algorithm combines sound local strategy computation, depth-limited learned lookahead, and restricted actions to apply heuristic-search ideas to imperfect-information games.Its local computation uses recursive reasoning while focusing computation on the current public state.
  • Continual re-solving: Continual re-solving reconstructs a subtree strategy whenever DeepStack must act, retaining its own range and opponent counterfactual values instead of a full-game strategy.The opponent values provide conditional what-if values for each opponent hand, enabling reconstruction for the remaining game.
  • Limited depth lookahead via intuition: DeepStack’s learned counterfactual value function replaces subtrees beyond the depth limit using both players’ ranges, pot size, and public cards as inputs.It outputs a vector of estimated values for holding each private hand in the resulting public state.
  • Sound reasoning: If value-function error is less than ϵ and T CFR iterations are used, Theorem 1 bounds exploitability by k1ϵ + k2/T.The constants k1 and k2 are game-specific.
  • Sparse lookahead trees: Sparse lookahead restricts actions to fold, call, 2- or 3-bet actions, and all-in, producing re-solved games with approximately 10^7 decision points solved in under five seconds.This action restriction makes play feasible at conventional human speeds but voids Theorem 1’s soundness property.

Deep Counterfactual Value Networks

DeepStack uses neural networks as learned counterfactual value functions for depth-limited lookahead. The networks process poker states and ranges through hand clustering and a zero-sum-constrained architecture, with training examples generated from randomly sampled games.

  • Network design: DeepStack trains separate neural networks for flop and turn states, plus an auxiliary network for situations before public cards appear.These networks estimate counterfactual values used when lookahead reaches its depth limit.
  • Architecture: The architecture uses seven fully connected hidden layers with 500 nodes each and an outer computation enforcing the counterfactual values’ zero-sum property.The outer computation combines estimated values with the input ranges to estimate game value for each player.
  • Training: The turn network was trained on 10 million randomly generated poker turn games, while the flop network used 1 million randomly generated flop games.Training games varied ranges, public cards, and pot size, with targets generated by solving restricted-action games without card abstraction.
  • Figure 3: Figure 3 maps pot size, public cards, and player ranges through hand clusters and seven hidden layers into zero-sum-constrained counterfactual-value vectors.The network output is post-processed before being mapped back to the hand-level value representation.

Evaluating DeepStack

DeepStack was evaluated against professional poker players using variance-reduced performance estimates and exploitability analysis. It won statistically significantly overall and against nearly all players who completed the requested match length, while local best response found no positive exploitability bound.

  • Performance measurement: 85% reduction in standard deviation from AIVAT enabled statistically significant performance estimates in matches with as few as 3,000 games.AIVAT uses DeepStack’s value-function estimates to compute a control variate.
  • Aggregate results: 492 mbb/g was DeepStack’s overall raw win rate across all games, more than four standard deviations above zero.Using AIVAT, the estimated performance was 486 mbb/g, more than 20 standard deviations from zero.
  • Individual results: 394 mbb/g was DeepStack’s estimated advantage among players completing 3,000 games, statistically significantly beating 10 of 11 players.The only exception was the best-performing player, against whom DeepStack was estimated to lose by 70 mbb/g without statistical significance.
  • Exploitability: LBR found no positive lower bound for DeepStack’s exploitability under a variety of settings, while losing over 350 mbb/g when attempting to exploit it.The cited analysis contrasts this with abstraction-based programs that were highly exploitable by LBR.

Discussion

DeepStack defeated professional poker players in heads-up no-limit Texas hold’em, a large imperfect-information game comparable in size to go. Its approach focuses computation on encountered situations and uses automatically trained value functions, with implications for broader asymmetric-information settings.

  • Discussion: DeepStack defeated professional poker players at HUNL with statistical significance in a game similarly sized to go but complicated by imperfect information.The paper describes this as closing much of the gap between the largest mastered perfect- and imperfect-information games.
  • Discussion: DeepStack focuses computation on specific situations arising during decisions instead of relying on offline computation of complete strategies.This differs from the abstraction paradigm that had dominated approaches to large sequential imperfect-information games for almost 20 years.
  • Discussion: Automatically trained value functions extend principles that have powered successes in perfect-information games to sequential imperfect-information settings.The paper presents this combination as part of a broader paradigm shift in approximating solutions to such games.
  • Implications: DeepStack’s continual re-solving paradigm is presented as a route toward applying powerful AI to real-world problems involving information asymmetry.The discussion names strategic-resource defense and robust medical decision making as examples where imperfect-information methods have shown promise.

Game of Heads-Up No-Limit Texas Hold’em

Heads-up no-limit Texas hold’em is a two-player, repeated poker game with private cards, public cards, and unrestricted betting subject to stack limits. Players act across four rounds by folding, calling, or raising, with unresolved games decided at showdown.

  • Game structure: HUNL is a two-player repeated game in which players alternate dealer position and seek to maximize chips won across individual hands.Each hand produces a chip transfer between the players.
  • Game structure: Players begin each hand with small and big blinds, while each player’s wagers and potential winnings are capped by a fixed stack.In the format used here, the big blind is 100 chips and the stack is 20,000 chips, or 200 big blinds.
  • Rounds and information: HUNL has four rounds—pre-flop, flop, turn, and river—with two private cards and five public cards revealed over the hand.The private cards are initially hidden from the opponent, whereas later cards are dealt face-up.
  • Actions: After cards are dealt in each round, players alternate among fold, call, and raise actions that determine whether play continues and how much enters the pot.Folding ends the hand, calling matches the current wager, and raising increases it.
  • Outcome: If no player folds by the river, a showdown reveals both private-card holdings and awards the pot to the player with the strongest five-card hand.The dealer acts first pre-flop, while the non-dealer acts first in later rounds.
  • Performance measure: Performance is measured in milli-big-blinds per game, or mbb/g, the average winning rate expressed in thousandths of a big blind.This stake-normalized measure allows results from matches played for different monetary stakes to be compared.

Poker Glossary

The glossary defines HUNL’s betting actions, rounds, cards, game objects, roles, and performance unit. Together, these terms describe how private and public information drives play from initial blinds through showdown.

  • Actions: A bet is the first wager in a round, while a raise increases the wager beyond the amount required to call.A call matches the current wager and ends the round; a check declines to wager when facing no bet.
  • Roles and blinds: The dealer posts the small blind, acts first in round one and second later, while the big blind is the non-dealer’s initial wager and twice the small blind.The small blind is half the size of the big blind.
  • Actions and outcomes: A fold gives up the current game and forfeits all wagers in the pot, ending the player’s participation.A showdown instead occurs after the river when players who have not folded reveal their private cards.
  • Cards and hands: A hand can mean a single poker game, a player’s private cards, or the best five-card combination formed from public and private cards.The glossary distinguishes these meanings for clarity.
  • Performance measure: Mbb/g is the average winning rate over games measured in thousandths of big blinds.It standardizes performance across matches played at different stakes.
  • Game objects: The pot is the collected chips from wagers, and the stack is the maximum amount a player can wager or win in one game.A chip is the whole-number marker representing wager value.
  • Rounds: The pre-flop, flop, turn, and river are the four successive rounds, associated respectively with initial private cards and later public-card reveals.The flop has three revealed public cards, while the turn and river each add one.
  • Cards and hands: Private cards are face-down cards visible only to one player, whereas public cards are face-up cards visible to everyone.Both are used together to form a poker hand.

Performance Against Professional Players

DeepStack was evaluated against professional poker players recruited through the International Federation of Poker, using a four-week, 3,000-game match format with monetary incentives.

  • Professional participants were recruited with assistance from the International Federation of Poker and identified themselves as professional poker players during registration.Players were selected from those recruited through member nation organizations.
  • Players had four weeks to complete a 3,000-game match against DeepStack.Matches ran from November 7 through December 12, 2016, through an online user interface.
  • The top three players who completed their matches received CAD $5,000, $2,500, and $1,250 prizes.Prizes were based on AIVAT performance.

Local Best Response of DeepStack

DeepStack’s exploitability was assessed with local best response rather than head-to-head performance, because head-to-head results poorly estimate equilibrium quality in imperfect-information games. Across tested LBR settings, LBR found no exploitable flaw in DeepStack, although the experiments do not prove it flawless.

  • Head-to-head performance is a poor estimator of equilibrium approximation quality in imperfect-information games, motivating LBR evaluation.DeepStack aims to produce a strategy with low exploitability, but exact exploitability is intractable for HUNL.
  • LBR provides a lower bound on exploitability by searching a fixed set of locally good actions against a strategy.Its available options can affect the lower bound because locally good actions may miss larger future exploitation opportunities.
  • Abstraction-based programs were found to be highly exploitable by LBR, with four programs beatable by over 3,000 mbb/g.These programs were reported as more exploitable than simply folding each game.
  • Under all tested LBR action settings, DeepStack yielded no exploitable flaw, while LBR lost 350 mbb/g or more to DeepStack.The authors state that this suggests exploiting DeepStack requires a more sophisticated search procedure than exploiting abstraction-based programs.
  • The experiments do not prove that DeepStack is flawless.The reported result is limited to the tested LBR settings and available actions.

DeepStack Implementation Details

DeepStack combines continual re-solving, sparse lookahead trees, learned counterfactual value networks, and a hybrid CFR solver to make fast decisions with commodity hardware. Its implementation tunes action sparsity and iterations by round while using caching and neural networks to control computation.

  • Continual Re-Solving: Lookahead re-solving specifics vary by round, including available actions, depth limits, and the neural network used beyond the depth limit.The networks include flop, turn, and auxiliary networks.
  • Continual Re-Solving: DeepStack solves an augmented game during play using a hybrid of vanilla CFR and CFR+ with uniform weighting and simultaneous updates.Early CFR iterations are omitted when computing the final average strategy and counterfactual values.
  • Implementation: The implementation tunes lookahead sparsity and re-solving iterations separately for each round to achieve consistent speed on commodity hardware and one GPU.The design goal was typically to play at least as fast as a human.
  • Implementation: DeepStack caches observed pre-flop re-solving results and uses an auxiliary network during initial CFR iterations to reduce repeated computation.The pre-flop round otherwise requires enumerating 22,100 possible flop public-card states.
  • Continual Re-Solving: DeepStack uses sparse lookahead trees whose first action layer determines its next-action options, while the remainder estimates counterfactual values.The F, C, P, A action set offers an excellent tradeoff between computational requirements and approximation quality.
  • Continual Re-Solving: Using more actions quickly enlarges the lookahead tree without substantially improving errors, whereas a single non-pot betting action substantially increases error.The action-set comparison evaluates sparse-tree counterfactual-value estimation.
  • Deep Counterfactual Value Networks: The turn network reached validation Huber loss 0.026 of pot size, the flop network 0.034, and the auxiliary network 0.000055.The passage notes that losses may overestimate true loss because multiple Nash equilibria can produce different counterfactual-value vectors.

Proof of Theorem 1

The proof establishes that depth-limited continual re-solving remains theoretically controlled: exploitability accumulates from approximate subgame solving and value-estimation error. After multiple re-solving steps, the resulting bound grows with the number of steps and estimator accuracy.

  • Error decomposition: The proof decomposes each re-solving step’s exploitability into errors from approximate subgame solving and the counterfactual-value estimator.The formal argument uses several lemmas to bound these two components separately before combining them.
  • Continual re-solving: Continual re-solving maintains the agent’s range and opponent counterfactual values rather than a full-game strategy.These quantities support reconstructing only the needed remainder of the game while preserving exploitability control.
  • Relation to prior work: The proof generalizes and improves the earlier re-solving exploitability bound and decomposition-regret bound of Burch et al.The result extends both components of the prior theoretical analysis.
  • Subgame replacement: The gadget-game analysis shows that replacing a subgame strategy adds at most the subgame’s exploitability to the original strategy’s exploitability.This provides the compositional step used to propagate local re-solving guarantees to the full game.
  • Final guarantee: Theorem 2 bounds exploitability after d re-solving steps by a term decreasing with T plus an estimator-error term proportional to (2d+1).Specifically, the bound is (d+1)k/T +(2d+1)jϵE, with game- and decomposition-specific constants.

Pseudocode

DeepStack repeatedly re-solves a depth-limited lookahead from the current public state, using ranges and opponent counterfactual values as its state representation. It evaluates the tree, updates regrets and strategies, samples an action, and updates the representation for the next decision.

  • RE-SOLVE: RE-SOLVE takes a public state, the agent’s range, opponent counterfactual values, and an information set, then returns an action and updated state representation.The updated representation contains the successor state, updated range, and updated opponent counterfactual values.
  • Iterative solving: At each iteration, VALUES computes subtree counterfactual values and UPDATESUBTREESTRATEGIES updates regrets and applies regret matching.The algorithm repeats these operations for T iterations before acting.
  • Action selection: After averaging the iterated strategies, DeepStack samples an action from the approximate equilibrium strategy at the current information set.The sampled action determines both the next public state and the updates to the agent’s range and opponent values.
  • Depth-limited evaluation: At the depth limit, VALUES calls the neural network evaluator instead of expanding the lookahead tree further.Terminal states are evaluated from the utility matrix, while depth-limited states use NEURALNETEVALUATE.
  • Range gadget: RANGEGADGET lets the opponent choose between entering the subtree and receiving an input value for each hand.This gadget is used alongside subtree solving to incorporate opponent counterfactual-value constraints.
Loading 1701.01724v3…