# Number of game tree nodes in HU

Is there a formula to calculate every possible betting/checking outcome in Heads Up situations at a given depth (stack/BB)?

• It would help if you gave a lot more specifications about the game setting. What game are you even talking about? What is the betting structure (be detailed)? In any case, there are likely at least trillions of nodes, even if you are bucketing scenarios. Oct 29, 2014 at 3:05
– Jon
Oct 30, 2014 at 7:49

It sounds like we're looking for game states.

Assumptions:

• The game is Texas Hold 'Em
• We round bets to multiples of the big blind for calculating state
• We don't distinguish between raising and re-re-re-re-raising because we only care about "betting / checking outcomes."
• For the sake of example, we'll assume \$0.50 / \$1.00 blinds with a \$100 buy-in.

The formula starts to look something like this:

There are 6,497,400 card states pre-flop (52 * 51 * 50 * 49) For each one of these, there are an additional 103,776 card states on the flop. For each of those, there are 45 new card states on the turn, and then 44 for the river. Therefore, at showdown, there are 1,335,062,881,152,000 possible card states.

At each betting juncture, there are (stack-size / BB) possible bet sizes to be made, and (stack-size / BB) possible raises to answer with. Checking adds one more possibility. Folding ends the game and destroys the state. In our example, then, there are (100 bets + 1 check) * (100 bets) = 10,100 possible betting states pre-flop. Post-flop, every dollar that went into the pot (creating a new possible state) is a dollar that we can't bet (removing a possible state), so I think that if we don't care about the full history, every betting phase has 10,100 possible betting states.

So, while the final number of game states will vary with blinds and stack sizes, we can describe the current or final state of any game with (1335062881152000 card states * 10100 betting states) = 13,484,135,099,635,200,000 nodes.

On the one hand, I hope I've interpreted your question correctly so that I could provide you a good answer. On the other hand, if I'm correct in guessing that you're looking at using game-state nodes for some sort of analysis software, I'm betting you're gonna need a bigger hard drive. And I'll make that bet even if you're Google. :)

• I think your interpretation is correct, and a good start. +1. But there's plenty of room for improvement. First, betting history is critical, each giving rise to a different node. Also, raising is very important, so I don't think it's practical to eliminate it, but some simplifications are reasonable. Also, your card states could greatly be reduced, because many of those states are virtually indistinguishable from an optimization perspective. For example, compare these 2 states: 1) Ac Kd vs 9s 8h with a flop of Qh Jd Ts. 2) Ac Kd vs 9s 8h with a flop of Qs Jc Th. Nov 15, 2014 at 16:53
• Good points on all counts. Betting history is critical to putting your opponent on a hand, but might not matter as much to the specific analysis being performed (e.g., from state #5734221, what is the next most likely state). The math was already gnarly, so I picked the easy interpretation of "betting / checking outcomes." :) I thought about suit compacting, too - definitely room for an algorithmic improvement, but the node count is so large that even a truly implausible 90% reduction in card states leaves us with an unmanageable tree. Nov 15, 2014 at 19:20
• Your very first number is wrong. There are 6,497,400/4 = 1,624,350 card states pre-flop, because XY is the same hand as YX. Nov 15, 2014 at 22:40
• @TonyK Argh. You are totally right. One of these days, I'll remember that step. :) Nov 17, 2014 at 5:18