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.
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
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
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
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.
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
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.
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.
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.
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.