Measuring the Size of Large No-Limit Poker Games
Michael Johanson. Measuring the Size of Large No-Limit Poker Games. Technical Report TR13-01, Department of Computing Science, University of Alberta, 2013.Download
Abstract
In the field 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 first 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.
Notes
Since 2007, the Annual Computer Poker Competition (ACPC) has played three different no-limit poker games:
- 2007-2008: $1-$2 with $1000 (500-blind) stacks
- 2009: $1-$2 with $400 (200-blind) stacks
- 2010-Present: $50-$100 with $20000 (200-blind) stacks.
The first game was previously estimated by Andrew Gilpin to have 10^71 game states. But this wasn't a precise count, and for the more recent two games, the computer poker community didn't have either an estimate or a precise count. This has been a little annoying, since the size of a game is the most common way of comparing complexity and the challenge of finding optimal strategies across games as diverse as chess, checkers, limit Texas hold'em poker, and so on.
In this technical report, we present a simple dynamic programming algorithm that can quickly and exactly count up the size of these large two-player no-limit poker games, in terms of the number of game states, information sets, terminal nodes, infoset-actions, and so on. We then present the sizes of the three no-limit competition games, which I have also reproduced below, and propose a new testbed game that is small enough to solve precisely in about 6 gigs of RAM (so it's tractable for all ACPC competitors), yet (we hope) complex enough that it will allow us to run meaningful experiments to investigate action abstraction and translation techniques. We have put our implementation of the algorithm online under an open-source (BSD) license (linked above), so that you can experiment with other no-limit games.
In the following three tables, I'll break down the size of the competition's no-limit Texas hold'em games in several different ways. The columns represent different counts of elements of the game:
- Sequences or Infosets: the number of sequences of actions in the game that reach a decision for either player 1 or player 2.
- Actions:the total number of legal actions for the player to act, summed across all sequences or infosets.
- Continuing:the number of sequences of actions that continue on to the next round.
- Terminal:the number of sequences of actions that end the game in the current round.
The rows are broken up into four sections. Within each section, we break down the counts by round, and also give a total across the entire game. The four sections are:
- Betting Sequences: Just the action sequences in the game, without considering cards for either player.
- One-Sided Canonical: The number of canonical information sets from one player's point of view, without considering the unseen cards dealt to the other player. This count only considers one "canonical" case from each set of "isomorphic" card deals that differ only by a suit rotation (ie, if every heart becomes a spade, every spade becomes a diamond, and so on).
- One-Sided: The number of information sets from one player's point of view, without considering the unseen cards dealt to the opponent. Every possible deal of cards is counted.
- Two-Sided: The number of game states from the perspective of an outside observer that sees both players' private cards.
2007-2008: $1-$2 $1000 (500-blind) stack no-limit Texas hold'em
| Betting Sequences |
Round | Sequences | Actions | Continuing | Terminal |
|---|---|---|---|---|---|
| Preflop | 8.54e31 | 2.56e32 | 8.55e31 | 8.55e31 | |
| Flop | 4.66e44 | 1.40e45 | 4.66e44 | 4.66e44 | |
| Turn | 1.61e54 | 4.84e54 | 1.61e54 | 1.61e54 | |
| River | 1.29e62 | 3.86e62 | 0 | 2.57e62 | |
| Total | 1.29e62 | 3.86e62 | 2.57e62 | ||
| One-Sided Canonical | Round | Infosets | Actions | Continuing | Terminal |
| Preflop | 1.44e34 | 4.33e34 | 1.44e34 | 1.44e34 | |
| Flop | 6.00e50 | 1.80e51 | 6.00e50 | 6.00e50 | |
| Turn | 8.91e61 | 2.67e62 | 8.91e61 | 8.91e61 | |
| River | 3.13e71 | 9.38e71 | 0 | 6.25e71 | |
| Total | 3.13e71 | 9.38e71 | 6.25e71 | ||
| One-Sided | Round | Infosets | Actions | Continuing | Terminal |
| Preflop | 1.13e35 | 3.40e35 | 1.13e35 | 1.13e35 | |
| Flop | 1.21e52 | 3.63e52 | 1.21e52 | 1.21e52 | |
| Turn | 1.97e63 | 5.92e63 | 1.97e63 | 1.97e63 | |
| River | 7.23e72 | 2.17e73 | 0 | 1.45e73 | |
| Total | 7.23e72 | 2.17e73 | 1.44e73 | ||
| Two-Sided | Round | States | Actions | Continuing | Terminal |
| Preflop | 1.39e38 | 4.16e38 | 1.39e38 | 1.39e38 | |
| Flop | 1.31e55 | 3.93e55 | 1.31e55 | 1.31e55 | |
| Turn | 2.04e66 | 6.12e66 | 2.04e66 | 2.04e66 | |
| River | 7.16e75 | 2.15e76 | 0 | 1.43e76 | |
| Total | 7.16e75 | 2.15e76 | 1.43e76 |
2009: $1-$2 $400 (200-blind) stack no-limit Texas hold'em
| Betting Sequences |
Round | Sequences | Actions | Continuing | Terminal |
|---|---|---|---|---|---|
| Preflop | 2.24e19 | 6.71e19 | 2.24e19 | 2.24e19 | |
| Flop | 9.91e26 | 2.97e27 | 9.91e26 | 9.91e26 | |
| Turn | 4.92e32 | 1.48e33 | 4.92e32 | 4.92e32 | |
| River | 2.47e37 | 7.42e37 | 0 | 4.94e37 | |
| Total | 2.47e37 | 7.42e37 | 4.94e37 | ||
| One-Sided Canonical |
Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 3.78e21 | 1.13e22 | 3.78e21 | 3.78e21 | |
| Flop | 1.28e33 | 3.83e33 | 1.28e33 | 1.28e33 | |
| Turn | 2.71e40 | 8.14e40 | 2.71e40 | 2.71e40 | |
| River | 6.00e46 | 1.80e47 | 0 | 1.20e47 | |
| Total | 6.00e46 | 1.80e47 | 1.20e47 | ||
| One-Sided | Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 2.96e22 | 8.89e22 | 2.96e22 | 2.96e22 | |
| Flop | 2.58e34 | 7.23e34 | 2.58e34 | 2.58e34 | |
| Turn | 6.01e41 | 1.80e42 | 6.01e41 | 6.01e41 | |
| River | 1.39e48 | 4.17e48 | 0 | 2.78e48 | |
| Total | 1.39e48 | 4.17e48 | 2.78e48 | ||
| Two-Sided | Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 3.63e25 | 1.09e26 | 3.63e25 | 3.63e25 | |
| Flop | 2.78e37 | 8.35e37 | 2.78e37 | 2.78e37 | |
| Turn | 6.22e44 | 1.87e45 | 6.22e44 | 6.22e44 | |
| River | 1.38e51 | 4.13e51 | 0 | 2.75e51 | |
| Total | 1.38e51 | 4.13e51 | 2.75e51 |
2010-Present: $50-$100 $20000 (200-blind) stack no-limit Texas hold'em
| Betting Sequences |
Round | Sequences | Actions | Continuing | Terminal |
|---|---|---|---|---|---|
| Preflop | 2.05e95 | 6.16d95 | 2.05e95 | 2.05e95 | |
| Flop | 1.02e121 | 3.05e121 | 1.02e121 | 1.02e121 | |
| Turn | 1.12e138 | 3.36e138 | 1.12e138 | 1.12e138 | |
| River | 1.13e151 | 3.40e151 | 0 | 2.27e151 | |
| Total | 1.13e151 | 3.40e151 | 2.27e151 | ||
| One-Sided Canonical |
Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 3.47e97 | 1.04e98 | 3.47e97 | 3.47e97 | |
| Flop | 1.31e127 | 3.93e127 | 1.31e127 | 1.31e127 | |
| Turn | 6.18e145 | 1.85e146 | 6.18e145 | 6.18e145 | |
| River | 2.76e160 | 8.27e160 | 0 | 5.51e160 | |
| Total | 2.76e160 | 8.27e160 | 5.51e160 | ||
| One-Sided | Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 2.72e98 | 8.17e98 | 2.72e98 | 2.82e98 | |
| Flop | 2.64e128 | 7.93e128 | 2.64e128 | 2.64e128 | |
| Turn | 1.37e147 | 4.11e147 | 1.37e147 | 1.37e147 | |
| River | 6.38e161 | 1.91e162 | 0 | 1.28e162 | |
| Total | 6.38e161 | 1.91e162 | 1.28e162 | ||
| Two-Sided | Round | Sequences | Actions | Continuing | Terminal |
| Preflop | 3.33e101 | 1.00e102 | 3.33e101 | 3.33e101 | |
| Flop | 2.86e131 | 8.57e131 | 2.86e131 | 2.86e131 | |
| Turn | 1.42e150 | 4.25e150 | 1.42e150 | 1.42e150 | |
| River | 6.31e164 | 1.89e165 | 0 | 1.26e165 | |
| Total | 6.31e164 | 1.89e165 | 1.26e165 |
Errata
In the "Two-Player" sections in the "Game States" columns, we're only counting the game states where it's one player's turn to act. Terminal nodes aren't counted.
Links
BibTeX
@techreport{ 2013-techreport-nl-size,
Title = "Measuring the Size of Large No-Limit Poker Games",
Author = "Michael Johanson",
type = "Technical Report",
year = "2013",
Institution = "Department of Computing Science, University of Alberta",
Number="TR13-01"
}