Evaluating Poker Hands with Bit Math

New year, new decade, new project wrapped!

This one is my second iOS app - I built a simple utility for calculating poker outcome probabilities for standard Texas Hold’em rules (find it on the App Store here).

I thought about ending the post here with a bad poker pun, but since my brain ended up drawing dead (heh), instead here is a write-up on how the app works.

Theoretically, exact probabilities can be calculated using combinatorics, but practically speaking this is impossible for a smartphone app given computing power limitations. Instead, Monte Carlo simulation can be used to approximate the chance of winning.

Setting up a Monte Carlo simulation to play out poker games is pretty simple to conceptualize - all we need to do is randomly sample cards to complete the table, pick the winner, and aggregate the results. The hard part is implementing an algorithm to “pick the winner” that’s fast enough to scale up to a large number of simulations.

So with that, here’s the fun part -

The Algorithm

We want a function that takes an input hand and outputs a numeric rank that can be used to compare different hands to choose a winner.

While researching, I found this great resource for publicly available poker hand evaluators (unfortunately, none are written in Swift). Many of the algorithms listed there are based on direct lookup tables, where hands and scores are pre-computed and stored in large arrays. Using tables is fast, but they end up taking a lot of space.

Eventually, I came across this evaluator written in JavaScript (licensed under Code Project Open License), which I used as the basis for the evaluator used in my app. The crux of this evaluator is bit math - operations on bit patterns or binary numerals at the level of their individual bits.

1) TRANSLATE HANDS TO BIT FIELDS

First, we translate the input 5-card poker hand into two bit fields. The first holds information on the face values of the hand:

[9, 10, J, Q, K]

[9, 9, 9, K, K]

The second holds information on the count of face values:

[9, 10, J, Q, K]

[9, 9, 9, K, K]

2) RANK HANDS BASED ON COUNT OF FACE VALUES

The magic bullet here is modulo division of the second bit field by 15 - let’s try a few examples:

Four Of A Kind:

[9, 9, 9, 9, K] translates to binary 000000010000000000001111000000000000000000000000000000000000 which equals decimal 4504630419521536

4504630419521536 mod 15 = 1

Full House:

[9, 9, 9, K, K] translates to binary 000000110000000000000111000000000000000000000000000000000000 which equals decimal 13511279918448640

13511279918448640 mod 15 = 10

Three Of A Kind:

[9, 9, 9, K, 7] translates to binary 000000010000000000000111000000010000000000000000000000000000 which equals decimal 4504080932143104

4504080932143104 mod 15 = 9

Two Pairs:

[9, 9, K, K, 7] translates to binary 000000110000000000000011000000010000000000000000000000000000 which equals decimal 13511005308977152

13511005308977152 mod 15 = 7

One Pair:

[9, 9, K, 8, 7] translates to binary 000000010000000000000011000100010000000000000000000000000000 which equals decimal 4503810349203456

4503810349203456 mod 15 = 6

High Card:

[9, 8, 7, 6, 5] translates to binary 000000000000000000000001000100010001000100000000000000000000 which equals decimal 73300705280

73300705280 mod 15 = 5

The magic is that each of the six hand types, after translating to binary using the method above and calculating mod 15, always produces the same result regardless of what the actual five cards are. What mod 15 does is equivalent to summing the values of each 4-bit card representation (check this out for more info). So [2, 2, 2, 3, 3] produces 10 which corresponds to Full House, as does [3, 3, 3, 4, 4], [4, 4, 4, 5, 5], and so on - feel try it out yourself.

So now, we have a way to identify six hand types based on the count of each face in the hand, which we can easily use to compare hands. For example, if one hand outputs 6 (One Pair) and another hand outputs 9 (Three Of A Kind), we know that the second hand wins.

3) CHECK FOR STRAIGHT

You might have noticed that the “High Card” example was actually a straight, but we’re unable to identify straights using modulo division.

However, we can do this with the first bit field representation, using the fact that binary 11111 equals decimal 31. Let’s go through another example:

• [5, 6, 7, 8, 9] translates to binary 000001111100000.

• We use bitwise AND with the negative of itself to get the least significant bit: 000001111100000 & -000001111100000 = 100000

• We divide the original bit field by the LSB which normalizes it: 000001111100000 / 100000 = 11111

This method works for any straight (try it yourself), so we can now reliably check for a straight by transforming the first bit field and seeing if it equals binary 11111 (decimal 31). We only need to add one final check to see if the bit field equals 100000000111100 (an Ace-low Straight).

4) CHECK FOR FLUSH

This is actually the simplest part of the algorithm - simply check if all the suits are equal. Bit math isn’t technically necessary, just makes it a little quicker to do.

If there are five of the same suit then we have a Flush, and there’s just one more step to check if the first bit field equals 111110000000000 (Royal Flush).

5) BREAK TIES

In the event that two hands are the same hand type (i.e. both hands are Full House), we break ties by sorting the 5 cards first by order of occurrence and then by face value, and use bit shifting to create a comparable score. Example with two full house hands:

First hand is [9, 5, 9, 9, 5], sorted to [9, 9, 9, 5, 5]. Take the first number and bit shift to the left by 16, the second number by 12, the third by 8, the fourth by 4, the fifth by 0. Then combine all five shifted numbers with bitwise OR.

• First 9 becomes 10010000000000000000

• Second 9 becomes 1001000000000000

• Third 9 becomes 100100000000

• First 5 becomes 01010000

• Second 5 stays as 0101

• Combine with bitwise OR to get 10011001100101010101, which equals decimal 629077

Second hand is [8, 6, 8, 8, 6]. Following the same steps above, we get 10001000100001100110, or decimal 559206.

Since 629077 > 559206, the first hand wins.

PUT IT ALL TOGETHER

So the full algorithm works like this:

• Use modulo division on the second bit field to check for Four Of A Kind, Full House, Three Of A Kind, Two Pairs, Pair, or High Card.

• Divide the first bit field by the LSB to check for a Straight, including an extra check for an Ace-low Straight.

• Check for five of the same suit for a Flush, including an extra check for a Royal Flush.

• Break ties by sorting hand by occurrence then face value, and use bit shifting to calculate comparison score.

What’s Next?

With this app - nothing major planned, might spend some time trying to cut down on execution time. Hopefully people will find it useful as a learning tool...if not, well, I still learned a ton building it.

In general though, I’m hoping to be more active in 2020. I’ve got a few project ideas in the pipeline, but it’ll depend on how quickly I can make progress. Stay tuned!