Measuring the Size of Large No-Limit Poker Games

By Michael Bradley Johanson. 2013

84 citations recorded by the source corpus.

In the eld of computational game theory, games are often compared in terms of their size. This can be measured in several ways, including the number of unique game states, the number of decision points, and the total number of legal actions over all decision points. These numbers are either known or estimated for a wide range of classic games such as chess and checkers. In the stochastic and imperfect information game of poker, these sizes are easily computed in \limit" games which restrict the players’ available actions, but until now had only been estimated for the more complicated \no-limit" variants. In this paper, we describe a simple algorithm for quickly computing the size of two-player no-limit poker games, provide an implementation of this algorithm, and present for the rst time precise counts of the number of game states, information sets, actions and terminal nodes in the no-limit poker games played in the Annual Computer Poker Competition.

Subfields: Artificial Intelligence, Clinical Psychology, Economics and Econometrics, 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

In Clinical Psychology

In Economics and Econometrics

In Game & Decision Theory

Citations in the corpus

DeepStack: Expert-level artificial intelligence in heads-up no-limit poker (2017, methodology): “The imperfect-information game HUNL is comparable in size to go, with the number of decision points exceeding 10(160) (13).”
Superhuman AI for heads-up no-limit poker: Libratus beats top professionals (2018, background): “By contrast, HUNL (23) has 10(161) decision points (24), so traversing the entire game tree even once is impossible.”
Endgame Solving in Large Imperfect-Information Games (2015, background): “cantly larger; for example, two-player limit Texas Hold’em has about 10(17) nodes, and a popular variant of two-player no-limit Texas Hold’em has about 10(165) nodes [12].”
Safe and Nested Endgame Solving for Imperfect-Information Games (2017, background): “This is a problem for large games, such as No-Limit Texas Hold’em— a common benchmark problem in imperfect-information game solving—which has 10 165 nodes (Johanson 2013).”
DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker (2017, background): “In HUNL, the two players can bet any number of chips, resulting in over 10(160) decision points (13).”
Solving Games with Functional Regret Estimation (2014, background): “2 · 10 160 such sequences (Johanson 2013, p. 12)).”
Solving Imperfect Information Games Using Decomposition (2013, methodology): “r game is among the simplest played by humans. The 2-Player No-Limit game played in the Annual Computer Poker 2 Competition is far larger, with 6:311 10164 game states and 6:376 10161 decision points [6]. Computer agents for these domains must use some technique to manage the large game size which m”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “Reducing the chance branching factor using suit equivalence [4], there are c1 = 169, c2 = 1286 792, c3 = 55 190 538, and c4 = 2428 287 420 information sets for each betting sequence in rounds 1 to 4 respectively [44] due to different chance events.”
Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent (2015, methodology): “We experimented on the version of two-player no-limit Texas Hold’em (NLTH) used in the ACPC, which has 10(165) nodes [17] in its game tree.”