Evaluating Poker Hands

Using our set of cards and our bit representations we can now evaluate poker hands using excessive bit twiddling. The general approach is to shuffle the bits for each suit around and combine them with various logical operations to work out what hand we have. We will work with bit masks where the ace is in the high position (bit 13 as opposed to bit 0) because in the vast majority of hands we need the ace to be high; only straight/straight flushes of ace to five need the ace to be low.

The first step is to horizontally reduce our bit mask of cards with OR. This will give us all the unique ranks in our hand. From this we can narrow the potential hands down. For example if there are two unique ranks then we either have four-of-a-kind (four of one rank plus a high card) or a full house. (two of one rank and three of another) We check the count in order of which is most common to improve performance, e.g. we check for five unique ranks first as this corresponds to a straight, a flush or a high card, which is the majority of hands.

Two Unique Ranks - Four-of-a-Kind or a Full House

To determine which hand we have we can horizontally reduce our bit mask of cards with AND. As four-of-a-kind has the same rank in every suit this will leave us with the rank of the four. A full house will be zero because it doesn't have the same rank in each suit.

Four-of-a-Kind

We now have our OR reduction with bits for both ranks and our AND reduction with a bit for the four. Combine these with a XOR and we will be left with a bit for the rank of the high card which is all we need to return our PokerHand.

Full House

We have our OR reduction with a bit for the two cards and a bit for the three. If we perform a horizontal XOR reduction of the original hand then this will give us a bit for the three; combining two cards of the same rank will give 0, so then combining with the third will leave a bit for the three cards. We can then combine the OR and XOR reductions in a similar way to four-of-a-kind to isolate the rank of the two cards and we're done.

Three Unique Ranks - Three-of-a-Kind or Two Pair

A horizontal XOR reduction will come in handy again here. We will be left with a 1 when there is an odd number of the same rank and a 0 when there is an even number. For three-of-a-kind we have three of one rank and then two other ranks, which will leave us with three set bits in total. A two pair has two of the same rank twice plus the single high card giving us one set bit in total. So performing the XOR reduction and counting the bits tells us which hand we have.

Three-of-a-Kind

Isolating the three from the two single cards is a little tricky; a XOR won't help us here because all the ranks are an odd number. There are four possible combinations of the three suits, spades/hearts/diamonds, spades/hearts/clubs, spades/diamonds/clubs and hearts/diamonds/clubs. All of these have either spades and diamonds or hearts and clubs. As our hand masks are laid out clubs > diamonds > hearts > spades we can shift our hand mask two suits (32 bits) to the right and combine with the original hand mask via an AND.

So what do we have now? We either have a bit corresponding to the three card rank in bits 0 -> 15 (spades/diamonds) or bits 16 -> 31. (Hearts/clubs) If we shift this right 16 bits and OR it with the original we will then have the three card rank in bits 0 -> 15. We might however still have a bit in 16 -> 31 so we will need to clear that out with a suitable AND mask. Now we've isolated the three we can XOR it with the original OR reduction to get the ranks of the high cards.

Two Pair

This one is fairly straightforward as our horizontal XOR reduction contains just the high card rank so we can just XOR it with our OR reduction to get the ranks of the two pairs.

Four Unique Ranks - Pair

Only one possibility for four unique ranks; a pair. One bit for the pair and one bit for each of the three other cards. Using a horizontal XOR reduction again will isolate the ranks of the three other cards, and we can then XOR this with our horizontal OR reduction to get the rank of the pair.

Five Unique Ranks - Flush, Straight or High Card

We first start with a special case. As we are treating aces high if the horizontal OR reduction is 10000000011110 then we have a straight or a straight flush from ace to five. To differentiate between the two hands we need to determine if all the cards are in a single suit or not. This can be done by isolating each 16 bit section via a suitable AND mask and seeing if the value is the same as the hand mask overall, i.e.

    private static bool IsSingleSuit(ulong handMask) =>
        (handMask & Bits0To15) == handMask |
        (handMask & Bits16To31) == handMask |
        (handMask & Bits32To47) == handMask |
        (handMask & Bits48To63) == handMask;

Note that we're not using the short circuit || operator here! It turns out that doing that slightly reduces performance as the overhead introduced by the branching is greater than just performing all four branches.

Straight

We need to determine if all five bits are sequential. An easy way to do this is to take our horizontal OR reduction, shift it one bit to the right and AND it with the original value. This will give us a 1 bit everywhere that there is a run of two cards, with the bit being the lower of the two cards. We don't have to worry about bit zero being shifted off to the right as that would only matter for an ace to five straight and we've already handled with our special case. For a run of five we must have four sequential and overlapping runs of two. Therefore if our number of 1 bits is four we have a straight; if they weren't sequential and overlapping we would get a smaller number.

What if all the cards the same suit? If so we have a straight flush instead of a straight. We can use the same method as for the special case above to determine this. One last check is then needed for a straight flush - if we have a straight flush that includes an ace (which is easy to check with an AND of the ace high rank) then we have a royal straight flush.

Flush or High Card

We now either have a flush or a high card. If it's a flush then they must all be the same suit, so we can use the same single suit check from above to determine which hand we have.

Performance

So how quick is it? I wanted it to be as fast as possible as that enables us to use brute force to evaluate lots of hands to calculate things like probability rather than having to perform the maths. Using Benchmark.NET to test evaluating every one of the 2,598,960 possible five card hands using a single thread on my 3.20GHz Intel Core i7-8700 gives:

|               Method |     Mean |   Error |  StdDev |
|--------------------- |---------:|--------:|--------:|
| EvaluateFiveCardHand | 193.3 ms | 1.36 ms | 1.20 ms |

So under 200ms for all possible five card hands, or roughly 74ns per hand. I'll take that!

Find the source code at https://github.com/MrKWatkins/cards-cs.