Introduction
If you've turned on a TV in the past five years you've seen those nifty win percentages they throw up on the screen in televised poker:
In this multi-part series we're going to build a poker calculator (with complete source code) capable of computing these sorts of win percentages or equities for any poker situation whatsoever...
- Any poker variant (Hold'em, Omaha, etc.)
- Any number of players (22 players preflop vs. your pocket Aces? Fine.)
- With any type of hand (specific hand, hand range, random hand)
- On any street of betting
- In the language (C#, C++, Java, VB.NET, etc.) of your choice
...in a couple lines of code:
We'll also discuss the theory that goes into such a calculator:
- Monte Carlo
- Exhaustive Enumeration
- Hand Distributions
- Lookup Tables
- Recursion
- Combinatorics
- How To Speak To a Girl
- Hand Range Notation
Now: the above televised poker win percentages shown above were inserted by the producers, after the fact, with perfect knowledge of each player's cards. In the heat of battle, we don't have perfect knowledge of anything except our own cards. And the way we typically get around this is by assigning our opponents not a specific hand, but a range or distribution of potential hands.
When confronted with a situation like this, the typical poker calculator curls up into the fetal position and begs for mercy. We want a poker calculator capable of handling these sorts of calculations—multiway ranged equity calculations—without skipping a beat. For example, let's say there are nine players, two of whom have known hands, two of whom have hand ranges, and five of whom have random hands...
- Player 1: [Jc Jh]
- Player 2: [8s 7s]
- Player 3: [99+,AJs+]
- Player 4: [QQ+,AQs+,AQo+]
- Player 5: [random]
- Player 6: [random]
- Player 7: [random]
- Player 8: [random]
- Player 9: [random]
- Board: [4d Ac 5d]
Normally we'd have to break open a copy of Andrew Prock's excellent PokerStove in order to perform this sort of analysis.
The purpose of today's post is to explain how to perform these calculations in a couple lines of code, with a view towards incorporating robust ranged equity calculation into our pet poker software projects: poker bots, real-time strategy assists, PokerStove clones, etc. We talked about ranged equity calculation briefly in The Great Poker Hand Evaluator Roundup and again in How I Built a Working Online Poker Bot, Part 8. Today's discussion will pick up where those posts left off.
This article is rather long-winded, so here's an overview of what we'll be covering:
- Introduction
- How a Poker Calculator Works
- Hand Distributions and Hand Ranges
- Monte Carlo vs. Exhaustive Enumeration
- Equity vs. Win Percentages
- Recursive Enumeration
- Generating Hand Distributions
- Amortizing Collisions with Round-Robin Access
- The XPokerEquity Calculator Source Code
- Testing the Evaluator
- Conclusion
Fair warning! If you're a grizzled veteran of poker-related code, you probably won't learn much by reading this. Save yourself! If you're a non-programmer, this material will probably be excruciatingly boring. Save yourself! If, on the other hand, you've got the poker/programming bug, if you've struggled to write robust equity calculation code before, or if you plan on one day writing such code, well, this article may come in handy.
Who knows. Anything's possible.
How a Poker Calculator Works
There are (at least) four ways to calculate equity in the game of poker. Whatever the game and whatever the specific scenario:
- Monte Carlo simulation
- Exhaustive Enumeration
- Lookup Tables
- Combinatorics
These methods are all subtly related to one another. Exhaustive enumeration is really a case of applied combinatorics. Lookup tables are a way of pre-computing equities and storing them in a file so we don't have to recalculate them. Monte Carlo is a statistical method which allows us to approximate the value we would've gotten had we taken the time to exhaustive enumerate every possible outcome. And so forth.
The point I want to make is that a poker equity calculator is a hand evaluator sitting inside a loop.
Now, the "loop" in question might be a series of nested loops. It might be a recursive loop. But every calculator will impose a circular, repetitive motion across the following actions:
- Generate the cards. This can be done either randomly (Monte Carlo) or by choosing each possible combination in turn (Exhaustive Enumeration).
- Evaluate the winner. You've assembled a single "hand" or trial of poker. Figure out who wins/ties/loses.
- Tally the results. Keep a running tally of wins and losses for each player involved in the hand.
- Repeat steps 1-3 a million (or however many) times.
So no matter how convoluted the code or how advanced the algorithm, you'll generally be able to pick out the above stages. Let's take a look at some representative code.
We have a basic loop, set to run (in this case) a certain number of trials. For each trial, we'll generate a) any missing player cards and b) any missing board cards. Once we've done that, we'll pass those into the hand evaluator, which will compute the winner and tally the results.
Now, when I say a hand evaluator, I mean a component whose only job is to take the cards for a specific trial and determine the winner. Sometimes the term is used loosely, but for me it has a precise meaning. In The Great Poker Hand Evaluator Roundup, we discussed a dozen or so different evaluators. In particular:
We'll discuss how to use each of these evaluators to perform true multiway equity calculation. In this installment, we'll focus on the Pokersource evaluator. If you're not familiar with this evaluator, you might want to read A Pokersource Poker-Eval Primer before continuing.
Hand Distributions and Hand Ranges
Hand distributions and ranges are so important to poker strategy, a sort of mini-language has sprung up to describe them. This language is still evolving, but it started as a way of describing hands while stripping out unnecessary suit information. Poker players will be familiar with the following descriptions of agnostic hands.
| Hand | Number of Combinations | Meaning |
| AJs | 4 | Any Ace with a Jack of the same suit. |
| 77 | 6 | Any pair of Sevens. |
| T9o | 12 | Any Ten and Nine of different suits. |
| 54 | 16 | Any Five and Four, suited or unsuited. |
It wasn't long before players started adding a few symbols to make these notations more expressive:
| Hand | Number of Combinations | Meaning |
| AJs+ | 12 | Any Ace with a (Jack through King) of the same suit. |
| 77+ | 48 | Any pair greater than or equal to Sevens. |
| T9o-65o | 12 | Any unsuited connector between 65o and T9o. |
| 54 | 16 | Any Five and Four, suited or unsuited. |
And of course, these notations can be glommed together with the "comma operator":
| Hand | Number of Combinations | Meaning |
| QQ+,AQs+,AK | 38 | Any pair of Queen or better, any AQs, and any AK whether suited or not. |
| AhKh,7h7d | 2 | Ace-King of Hearts or a pair of red Sevens. |
Needless to say, if we're building an evaluator that can work with hand distributions, it should be able to understand the notation used to describe them. In particular, when we say "I believe my opponent has a range of 99+,AJs+", it should understand that what we're really saying is I believe my opponent has one of 48 specific hands.
Of course, if you happen to be holding the Ace of Spades, then some of those possibilities are now blocked for your opponent, and we'll need to take this into account when performing any equity calculations:
But regardless of what distribution we assign an opponent, or how many of the specific hands contained in that distribution are available, we can always, always, always represent an opponent's distribution as a simple collection of specific hands. Even if we know the opponent's specific cards, he still has a distribution...of one hand.
In fact, the core abstraction used in our evaluator is exactly that: a class representing a single player's distribution of possible hands:
{
public:
/* blah blah blah */
private:
vector<StdDeck_CardMask> m_hands;
};
This is the acid test of a true isometric calculator. Isometric (we could also use the word congruent) calculators treat everything as a distribution. The isometric calculator could care less whether a player has:
- A unary distribution containing a single specific hand
- A random distribution containing all of the 1,326 possible starting hands
- Any other distribution
This normalizes the underlying logic, allowing us to disregard arbitrary differences between specific hands, hand ranges, and random hands. They're all the same. And they're all treated the same.
Monte Carlo vs. Exhaustive Enumeration
Monte Carlo simulation and Exhaustive Enumeration are the two horns of the poker equity calculation beast.
On the one hand, we have the exhaustive enumeration approach, which consists of generating each and every possible outcome. No matter if you have 22 players with random and ranged hands before the flop, exhaustive enumeration will generate every possible combination of cards for each player along with every possible combination of board cards, tally them all, and yield the precise theoretical equity for the situation with zero error.
On the other hand, we have the Monte Carlo method, darling of physicists and statisticians, which consists of generating random inputs (cards, in our case) across many trials, thereby converging a result which closely approximates the theoretical "correct" result. Monte Carlo simulation produces results which have a small margin of error, although in practice this error is low enough that we can effectively ignore it.
Now: in a perfect world, we'd always use exhaustive enumeration. Given infinite computing power, we'd analyze every possible outcome in a nanosecond and be done with it. But in the real world, exhaustive enumeration can be prohibitively expensive. The outcomes start to explode as you add more and more choices to a given scenario:
| Scenario | Street | Number of Outcomes |
| AhAd vs. KcKs | Turn | 44 |
| QsJc vs. Ad2c | Flop | 990 |
| 44 vs. Ts7c | Flop | 2,970 |
| AKs vs. TT | Flop | 23,760 |
| AKs vs. TT vs. J9o | Flop | 260,064 |
| 3c2s vs. 5d4c | Preflop | 1,712,304 |
| AA vs. KK | Preflop | 61,642,944 |
| AA vs. KK vs. QQ | Preflop | 296,082,864 |
| AA vs. KK vs. QQ vs. JJ | Preflop | 1,407,466,368 |
| AA vs. XX | Preflop | 12,585,434,400 |
You're already looking at on the order of 12 billion outcomes just to exhaustively enumerate an agnostic pair of Aces versus a random hand before the flop. And we'll frequently be calculating situations involving 4 or 5 players (if not more), each of whom has a distribution of N possible hands, times the 5 board cards, and so forth.
Now here's the key point: even though it would take us (say) 12 billion evaluations to exhaustively enumerate the AA-vs.-random preflop scenario, we can Monte Carlo the same scenario and get some very precise results in a fraction of that time. A million-trial Monte Carlo simulation will produce equities that are precise down to fractions of a percent; in fact, we can typically get that type of precision with far fewer than a million trials (possibly as few as 10,000 or 100,000).
This leads us to a few rules of thumb:
- A robust calculator MUST support both Monte Carlo and Exhaustive Enumeration
- A robust calculator SHOULD have the ability to switch between MC and EE based on the specific scenario
PokerStove actually lets the user choose how to perform the analysis:
And sure enough, in the source code accompanying this article, you'll find a couple telltale methods:
{
public:
/* blah, blah, blah */
int Calculate(const char* hands, const char* board, const char* dead, int numberOfTrials, double* results);
private:
int CalculateExhaustive();
int CalculateMonteCarlo();
/* blah, blah, blah */
}
The decision as to when to use Monte Carlo vs. Exhaustive Enumeration really boils down to you and the purpose of your tool. If you need to compute equities involving many players with fat distributions in fractions of a second, you'll gravitate towards Monte Carlo. If on the other hand you have a lot of processing time or if you're not dealing with ranged/random hands so much, exhaustive enumeration might be the order of the day. In general, you'll find that there exists a Monte Carlo threshhold which is ideal for your application. When the number of potential outcomes exceeds this threshhold, you'll Monte Carlo; when the number of outcomes falls short, you'll exhaustively enumerate.
But the calculator itself should support both.
Equity vs. Win Percentages
The terms equity and win percentage are often used interchangeably, in casual conversation, but these are actually two different things. As Andrew Prock explains it:
[Equity] is not the chance that a hand will win the pot. Rather it is the fraction of the pot that a hand will win on average over many repeated trials, including split pots. The equity for a hand is calculated by dividing the number of "pots" that the hand won by the number outcomes considered. Because two players can split a pot, a player can win fractional pots. Thus, it is possible for a hand to have non-zero equity despite the fact that it cannot win.
The metaphor I like to use is that of a pizza.
In a single battle of poker, there's exactly 1.0 unit of "winningness" to go around. One pizza. The player who wins the hand gets the pizza, and everybody else goes hungry. But if two or more players tie for the win, well, they each get an equal share of the pizza. If exactly two players tie, they each get half of the pizza: 0.5 units of winningness each. If three players tie, they each get a third (0.333) of the pizza. And so forth.
In general, when N players tie in a particular game of poker, they're each awarded a fractional win equal to 1 / N.
This is not just some number we use by way of explanation. This fraction of the pizza, be it 1.0 or 0.5 or 0.333 or 0.25, is the actual amount you'll add to each player's "win tally" in the poker calculator implementation, after you determine the winner(s) of each specific trial:
if (!isTie)
{
m_wins[bestIndex]++;
}
// If there IS a tie, then the players with the tied winning hand get a +X for
// the win, based on by how many players it was split.
else
{
double partialWin = 1.0 / ((double)numTies + 1.0);
for (int i = 0; i <= numTies; i++)
m_wins[ m_tiedPlayerIndexes[i] ] += partialWin;
}
That code is a little messy (see my code disclaimer, below), but it gets the point across. Equity is similar to win percentage except it normalizes the value of ties. This is hugely important in a game like Hold'em or Omaha, where ties are so frequent.
Recursive Enumeration
One of the benefits of treating each player's hand as a distribution containing one or more hands is that it gives us a precise count of each player's possible holdings and allows us to express each player's hand as a number between 0 and N. For example, in a given three-player matchup we might find that:
- Player 1 has exactly 1 possible holding (a specific hand)
- Player 2 has exactly 36 possible holdings
- Player 3 has exactly 154 possible holdings
So we can exhaustively enumerate all possible combinations of player holdings using a typical nested loop structure.
HoldemHandDistribution dist2 = new HoldemHandDistribution("QQ+,AJ+");
HoldemHandDistribution dist3 = new HoldemHandDistribution("22+,A2s+,ATo+,KTs+,QJ+");
for (int player1 = 0; player1 < dist1.GetCount(); player1++)
{
for (int player2 = 0; player2 < dist2.GetCount(); player2++)
{
for (int player3 = 0; player3 < dist3.GetCount(); player3++)
{
// Pick a hand from each player's distribution
StdDeck_CardMask hand1 = dist1.Get(player1);
StdDeck_CardMask hand2 = dist2.Get(player2);
StdDeck_CardMask hand3 = dist3.Get(player3);
// Randomly choose or exhaustively enumerate whatever board cards.
}
}
}
The problem is that the number of loops has to be hard-coded per the number of players. If we had seven players, we'd need seven loops. That's a little messy, it violates DRY, and we'd prefer a normalized solution that will handle any arbitrary N number of players. In order to do that, we'll take our nested-loop structure and invert it, creating a recursive function with a depth equal to the number of players in the hand.
void ExhaustiveRecurse(int N)
{
HoldemHandDistribution thisHand = /* Get the Nth player's distribution */;
for (int index = 0; index < thisHand.GetCount(); index++)
{
m_playerHands[N] = thisHand.Get(index);
if (N < (numberOfPlayers - 1))
{
ExhaustiveRecurse(N + 1);
}
else
{
/* Each player has been assigned a single hand from his distribution.
Now, exhaustively enumerate all board cards and for each situation,
run the evaluator to determine the winner, and tally the results */
}
}
}
The above code omits some important details—such as how to handle dead cards and collisions between player distributions—but the general idea, and you'll see this in the full source code accompyaning this article, is that we can exhaustively enumerate any arbitrary situation involving N players with arbitrary distributions along with all possible board combinations using a single recursive function.
Generating Hand Distributions
So now that we know our core abstraction will be the hand distribution, and now that we're agreed on the language we use to describe hand distributions, let's talk a little bit about how to generate them programatically. In other words, how do we go from this...
22+,A2s+,ATo+,KT+,QT+,JT+,65s+
...to this?
In general, to parse a given textual hand distribution, we'll follow these steps:
- Tokenize the range on the comma delimiter. So we'll break "22+,A2s+,ATo+,KT+,QT+,JT+,65s+" into seven separate tokens.
- For each token, loop across the different suit-combinations.
- If the token includes a "+", add a loop to increment the ranks in conjunction.
- If the token includes a "-" (as in TT-88) add a ceiling to the the rank loop.
For example, to boil a given agnostic pair (such as 77) down into its six unique combinations, we might hack out this straightforward solution:
int rank = StdDeck_Rank_7;
for(int suit1 = StdDeck_Suit_FIRST; suit1 <= StdDeck_Suit_LAST; suit1++)
{
for (int suit2 = suit1 + 1; suit2 <= StdDeck_Suit_LAST; suit2++)
{
// Assemble the first and second card
card1 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit1) );
card2 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit2) );
// Combine them
StdDeck_CardMask_OR(hand, card1, card2);
// TODO: Add the hand to the distribution
}
}
If the agnostic pair includes an incrementor, as in "77+", we can add a third loop to increment the rank:
for (int rank = Std_Rank_7; rank <= Std_Rank_ACE; rank++)
{
for(int suit1 = StdDeck_Suit_FIRST; suit1 <= StdDeck_Suit_LAST; suit1++)
{
for (int suit2 = suit1 + 1; suit2 <= StdDeck_Suit_LAST; suit2++)
{
card1 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit1) );
card2 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit2) );
StdDeck_CardMask_OR(hand, card1, card2);
}
}
}
And if the agnostic pair specifies a range with a ceiling, as in "JJ-88", we'll just change the condition on the rank loop:
for (int rank = lowRank; rank <= highRank; rank++)
{
for(int suit1 = StdDeck_Suit_FIRST; suit1 <= StdDeck_Suit_LAST; suit1++)
{
for (int suit2 = suit1 + 1; suit2 <= StdDeck_Suit_LAST; suit2++)
{
card1 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit1) );
card2 = StdDeck_MASK( StdDeck_MAKE_CARD(rank, suit2) );
StdDeck_CardMask_OR(hand, card1, card2);
}
}
}
Do the above loop structures look familiar? They should, if you're one of the masochistic few who actually read Exhaustively Enumerating Combinations and Permutations in Code. Converting a textual hand range notation into a concrete distribution is just a special case of combination counting. The above method isn't the most elegant, but it is straightforward.
Amortizing Collisions with Round Robin Access
When Monte Carlo is used to randomly select a single hand from each opponent's distribution, the possibility of collisions can arise. That is, a situation can occur in which every hand in a player's distribution is prevented or blocked by the cards chosen for other opponents during a specific trial. Consider the following four-way matchup:
- Player 1: [QQ+,AJs+,AQo+]
- Player 2: [random]
- Player 3: [A2s+,22+]
- Player 4: [A2s+,ATo+]
Now, what happens if we (randomly) select the [AhKh] for player 1, the [Ad7c] for player 2, and the [AsAc] for player 3?
Answer: player 4's distribution is now completely blocked. Every hand in his distribution requires an Ace, but the four Aces have already been dealt out. This won't happen very often, but it can and will happen. And when it happens, the trial is invalid and should be thrown out. Furthermore, it doesn't take a complete blockage to introduce bias into the results. Even partial collision can bias the results. The reason is simple: the first player to be "dealt" cards always has his entire distribution to choose from; but many of the hands in the last player's distribution will no longer be available.
It's unfair.
So in order to reduce the likelihood of this happening, we change the player pecking order between trials. That is, instead of choosing Player 1's hand followed by Player 2's hand followed by Player 3's, each and every trial, we want to alter the order in which we choose cards for opponents across many trials. Instead of starting with Player 1 every time, we want to start with Player 1 on one trial, Player 2 on the next trial, Player 3 on the trial after that, and so forth.
By choosing the "starting player" in this round-robin fashion, we amortize potential collisions across all players, reducing the likelihood of a) bogus trials that we have to discard and b) bias due to partial collision. And in order to do this cleanly, we'll use a circular linked list to address these players, and increment our "head" with each new trial.
I hope it's becoming clear that when I said in A Circular Dilemma Concluded:
The circle is the fundamental geometry of poker.
This wasn't some theoretical pie-in-the-sky notion! Of course, you don't have to use a circularly-linked list, but it makes the code cleaner.
The XPokerEquity Calculator Source Code
Today's installment includes source code for a full-fledged isometric calculator capable of computing equity for any Texas Hold'em scenario, including weird scenarios such as pocket Aces versus twenty-two random hands before the flop. Using the evaluator is simple:
Just put in your opponent hands/ranges separated by | and go. That version of the function will switch between Monte Carlo and Exhaustive Enumeration based on the MC threshhold. In addition, there are a couple overloads which you can use to force Monte Carlo or Exhaustive Enumeration:
- HoldemCalculator::CalculateMC
- HoldemCalculator::CalculateEE
This evaluator is implemented without optimizations of any kind in order to make the code as transparent as possible.
- No lookup tables. We'll add these in a future installment, but for now, I wanted to focus on the calculation, not the lookup-ation.
- No fancy combinatorics shortcuts. We use classical Monte Carlo and exhaustive enumeration for everything.
- No code refactoring/compaction. You'll find many, many places where the code can be improved. Many.
Despite the lack of optimization, this evaluator is fast enough for typical use, including real-time poker botting in a multi-table scenario.
Download the XPokerEquity source code (751K)
Testing the Evaluator
The XPokerEquity evaluator solution includes a simple test project (console app) which will run various matchups and test the returned equities against PokerStove results:
When it comes to testing your poker calculator, there are three key sanity checks you'll want to employ, especially if you're using the evaluator for something important (a commercial product, a real-money poker bot, etc.):
- Spot-testing against established evaluators like PokerStove.
- Testing preflop equities against the various preflop lookup tables that are available.
- Comparing Monte Carlo results for a given matchup against exhaustive enumeration results for the same matchup.
In practice you'll find that isometric evaluators tend to be either "right" or "wrong". That's not to say they aren't susceptible to obscure bugs, but generally speaking, if an isometric evaluator calculates any multiway matchup correctly, it'll calculate them all correctly. That's not a substitute for robust testing, but it's another benefit of the isometric approach to equity calculation.
Conclusion
I apologize for the length of this post (well, not really) but I wanted to do a (fairly) comprehensive overview of the subject rather than just throwing a brick of source code at you. Needless to say, there are better and more clever ways of doing pretty much everything we've discussed here today.
Anytime you flirt with the boundary between computer science and hard math (or software development and computer science) things start to get a little crazy. Maybe you can use N-ary decomposition across a diagnate infinity of infinities of choice with matrix-based combinations to derive the asymptotic convergence curve and thereby somehow back yourself into a massively parallel exploration of the poker game tree, and you know what? That's fascinating. It really is. But for now let's just deal out a bunch of hands and tally the results. It's easy and it works.
And for those of you who've been wondering what happened to the poker botting series?...stay tuned. Because once you've built your isometric equity calculator, your poker bot can start to do all sorts of nifty things in real time:
- Estimate core EV
- Create EV action trees
- Calculate ICM
- Establish empirical opponent distributions in conjunction with tools like Hold'em Manager (etc.)
So I hope you'll stay with me as we watch our formerly naive poker bots start to grow some teeth. Until then, may the equities always be in your favor.
Posted by James Devlin 61 comment(s)
