Analyzing a Poker Hand Analyzer

Introduction

subskybox wrote an intimidating 5-card poker hand analyzer in four lines of JavaScript. The original is somewhat tricky to understand initially:

Of course, by somewhat tricky I mean extremely tricky, and by initially I mean always. The shock and awe factor of the first look at the code is pretty much only equalled by the shock and awe felt once you’ve worked through it and seen what it does and how it does it.

I burnt through several thousand neural connections working it out, so I figured I may as well write it down before my brain shuts down altogether. Even now the light is fading and I hear what seem to be distant ghostly voices calling me. Anyways…

The original code feels a lot like Assembly / C, in that it reuses variables and uses cunning bit manipulations (which were of course part of the author’s plan). There are a couple of ideas that are used in the code that are necessary to understand before you can fully grok the code. Over the course of looking at it, we are going to reformat the code completely to make it easier to understand. Although I have not done speed tests, the chances seem good that the original is faster. Ours will be significantly more readable and much longer.

There is also a mix of standard bit operations with standard arithmetic operations. As he explains in the original article, this is because the bit operations are limited to working with 32-bits and we need to use 52-bits.

The suit ranks are stored in two different formats although both store information on a bit level. In one format, each card is stored and information on any duplicates found is preserved. This format uses the full 52-bits available to it, using 4 bits for each different card rank. For each duplicate entry, an additional bit is set to 1. This bit field is used to work out the majority of the different hands, as we can find evidence for cases such as 3 of a kind, pairs, etc. Because we are using 52-bits, operations on this bit field need to be done using arithmetic operations.

In the other format, duplicates are discarded and we keep information only on which cards we have seen. For this bit field, we simply put a 1 in the index corresponding to the card’s rank. To make the creation of this bit field easy, the array is not modified to remove the unused 0 and 1 index. This array is used to detect straights, so some additional 0’s on one end of it make no difference. As this array takes up only 13-bits (one for each rank), we can safely use normal bit operations on it.

The code begins by declaring some constants – one array containing the different hands (in a very specific order, as we will see shortly), a couple of convenience constants for declaring card values (including importantly that the Ace is high with a value of 14) and a neat little underscore array containing the actual suit symbols which is kinda neat.

The function declaration uses cs and ss to represent the card ranks and card suits. This is somewhat inconvenient, so in my readable code examples I’ve renamed them cardRanks and cardSuits .

First up, we create the array used to detect straights. In creating it we run into our first bit operation – the bit shift.

The Straight Bit Field

The bit shift, notated by a <<  or a >>  depending on the direction that we are shifting, shifts a set of bits up or down a certain number of  positions.  For example, if we were to shift the number 9 one bit to the left, notated as 9 << 1 , we would get

To fill in a bit in a position corresponding to a specific card value, we need to shift up 1 to that position. For example, if we had a card with the value 8, we would need to shift 1 up 8 times, that is 0000 0001 << 8 .

This is the process followed to create the straight array. If our next card was a 4, we would add a similar array to our existing array. First, we need to shift 1 up 4 times.

Next, we need to combine the two arrays that we have – 1 0000 0000  and 0001 0000 – so that we can store information on each card in a single field. This is done using the boolean operator OR, represented by a | (a pipe). The | operator returns true (or 1 in our case) if either of its operands are true (or 1). In a bit operation, it is run on each bit in turn. If it was to be run on our two fields, we would get the following:

The result is a field containing information on both arrays. To create this field containing information on each of the cards we have been passed, we need to do the bit shift operation for each card value and then OR all of the shifted values together, as is done in the line:

With this, we have our bit field containing information on which values we have seen. This array will need some further tweaking before we can use it, but that occurs later in the code.

The Card Rank Field

Calculating the card rank bit field is somewhat more difficult. In this case we wish to preserve information about how many times we’ve seen each card – this will allow us to work out hands such as full houses, pairs, etc.

The original code does all of this formatted in one line, although given that there is a for loop as well as a loop body the operation actually occurs over several lines. The original code is:

There’s a lot going on here. First off, we have three different variables – a counter i , that is used for the current position in the card rank array  cs  (which we have dubbed  cardRank), a value  o which is used to represent the nibble position which corresponds to the current card rank and a value  v which represents the card count field which we are building up – let’s redub that one  cardCountBitField.

Substituting the confusing variable names for some easier ones and reformatting this loop slightly gives us the following.

As noted in the original article, the first loop where index == -1 does nothing, but the loop termination check sets up the first nibblePosition. The loop is generally fairly confusing, so we’re going to break down all of its operations until it becomes easier to understand. Our final loop will look as follows.

As can be more clearly seen in this loop, what we’re trying to do is count the number of times we’ve seen each card rank. We do this by storing the various rank counts in the card count bit field, then whenever we encounter that rank again we retrieve the current count, increment it by one and store it back in the bit field.

The original code uses several bit manipulation tricks to do this – we’ll examine them each in turn, beginning with how we find the correct position in the bit field to store the count for a specific card rank.

Bit Field Position

The code which achieves this, in the original program, is

Referring to the original pictures, each card rank is going to take up four bits in our bit field. Given a card rank, we need to determine where in the bit field that rank is going to be stored. Basically, we need to start at 0 and then move up 4 indices each time.

However, we are not working within a traditional array, so it isn’t as simple as moving indices. We are working with values, and we to change the value at a specific bit we need to use a number which has that bit set. As mentioned in the original, and as per our earlier discussion on bit shifting, this would normally be done as

If, for example, we wished to place a bit at index 3, we would have 1 << 3 == 1000 . We could then use our | operator to include this value in the array as we did before when we were using the card ranks.

This case requires some extra manipulation – because we are representing each additional card with a 1 in the appropriate index, instead of just adding 1’s, each rank will take up four bits. This means that the value for the base index will actually be

Thanks to some clever bit trickery, we don’t need to work out how many 1’s have already been put in place and then find the next available space. We’ll look at how to do that soon, but we still have one problem here – we cannot use the convenient bit shift operation, as the card rank count bit field needs to use up all 52 bits (13 ranks, 4 bits each).

The bitshift operator in JavaScript only works on 32-bit values, so if we were to use it we would lose a considerable proportion of the value each time. Instead, the original code works out the value that would place a 1 in the required index manually.

Thinking back to binary, a 1 in the required index and 0’s elsewhere simply indicates that the number can be expressed as – that’s how binary works. With this in mind, we can formulate a new way to get the current position as

Next up we’ll have a look at how, given this value, we can retrieve the current value from the bit field – we need this to include the new information that we have.

Retrieving the Current Value

Let’s have a look at the case where we could use the bit shift operators first. What we’d like to do is, given a card rank, retrieve the 4 bits that correspond to the current value we have stored for that card rank.

We know that its position would be at  index * 4  – in order to extract just the 4 bits starting at that point, we’ll first shift our bit field down by that position so that the bits we’re interested in are located at bit 0.

Now that we’ve removed all of the bits on the right of our target field, we want to remove the bits on the left of our field. To do this will require a new boolean operator – the AND (&) operator.

Remember the OR operator returns true if one of its operands is true. The AND operator is similar, but it returns true only if both of  the operands are true.

We can exploit this property and set a range of bits, corresponding to the bits that we wish to keep, to 1. Remember, our bits are now at position 0, and we want to preserve 4 bits of information. We therefore use a value with the first 4 bits set to 1, and AND them together.

This zeros out all bits that aren’t in the first 4 locations, leaving us with just the area that we’re interested in. Awesome – that’s just what we’re after.

Except of course that we can’t use the bit shift operator – we’re working with that pesky 52-bit field still. We need another way to shift right, similar to how we shifted left earlier.

In our earlier equation, , what was missing was the implicit before . Although we didn’t need it, it was there – we can view it as though we were pushing the 1 up via the multiplication.

In a similar way, we could push the one down using division. For example, moving a bit from 1 0000  to 0 0010 – that is, shifting it right 3 places – can be expressed as

More wordily, we can simulate a bitshift right by dividing instead of multiplying by the appropriate power of 2. Conveniently, once we’ve bit shifted right we can use the AND boolean operator – we’re only interested in the first 4 bits, so it’s not a problem if our value is truncated to 32-bits.

Finally, we can code a function to retrieve a value from our bit  array. This function will have to use the  getPositionForCardRank function we wrote previously – that function returns a power of two already, so we can do the division and ANDing directly. A field with the first 4 bits set to 1 is equal to 15, so we AND with 15 to extract the final value.

Now that we can calculate the position in the array where we need to place values and we can extract that position, we need to set the next bit to 1 to increase our count when we encounter duplicate cards.

Setting the bit field

All of this is accomplished in the following from the original.

Our task now is to set the next free bit to 1. Normally we would just increment the value and overwrite the existing value (via some bit trickery), but in this case we are not incrementing but instead setting the bits like flags.

This is accomplished by some trickery – first, imagine the case where we have already seen two of the current card rank.

0011

Our aim is to set the next bit along to a 1. In order to do this, we add 1 to the existing field, giving us a new value of

0100

Now, if we add that value to our original value, we end up with 0111 – just what we were after. In order to have this work with our code, we first extract the current value from the bit field giving us a 4-bit value of the current flags. We add one to set the bit we’re now after, and reshift the value back up to its proper position. We then add it to our field.

The code to achieve this is in two parts – first, we need to add a value to an existing array, to accomplish the +1 action above.

Using this, we can add the correct value to our bit field. Shown here is the complete loop that would correspond to  for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);} in the original code.

That’s two lines down, two to go. Halfway there! Just some magic to go.

Checking For Hands

The Magic

Now that our fields are mostly set up, we can start checking for the existence of hands. The line we’re going to focus on now is

This line does several things. It checks for the existence of almost all the hands except for the flush, straight flush and the royal flush. Let’s dive on in.

First off, the modulus operation. Although this would normally return the remainder if the value was divided by fifteen, when we’re looking at things at a bit level the result is that each of our separate card ranks of 4 bits are summed. Fifteen is used because it is the maximum value that can be stored in 4 bits.

This is where the hands array comes in – it turns out that for each hand combination, this summed value is unique.

More interesting is that, regardless of the different combinations of cards, the value is always the same for each hand regardless of the cards that made it up. Although this seems kind of crazy initially, when you think about how we’re summing the card values separately it starts to make sense.

Let’s think about the two of a kind hand as an example. For this to occur, we need one group to have 2 bits set (to represent the two identical cards that we’ve seen) and two other individual bits will be set on other cards.

You’ll notice that we’ve not mentioned any specific cards here – this holds true for any two of a kind. As such, any combination of cards would produce the same value –  0011 + 0001 + 0001 + 0001 == 6 in this case.

Thanks to this magic, all we need is an array with the hands set at the appropriate positions and we can read off a large range of our hands – in code:

Because arrays are indexed from 0, in order to use all of the array values, we simply subtract one from our total to get the correct array value. You’ll notice that several positions in the array are still available and are currently filled with “” – these values are used for our other hands. Next up, the straight.

Straights

The straight check uses the bit field we created earlier where duplicates are discarded. A straight requires that we have five cards in a row – that is, our array has a row of five 1’s in it.

This is detected by removed all 0’s on the right side of our bit field. If we have removed all 0’s, then the first bit must be a 1. If we have a straight, then the bits to the left of that 1 must also be ones.

The value corresponding to  1 1111 is 31 – that means we can check if the resulting bit field is equal to 31. If it is, then we have a straight.

But how do we remove the 0’s? This is called normalizing the bit field. Stuff like this has names, who knew?

First off, we need to find the first 1 in the bit field. Once we have that position, we can just shift the field down so that that 1 is at position 0 using the techniques developed earlier. But how do we do that?

The original write up hints at how it is done – requiring that we know two’s complement binary representation. Two’s complement is a method of storing negative numbers used by most modern computers where the last bit is used to indicate whether or not the number is negative.

If so, the rest of the appropriate bit values are added to the negative number to reach our total. For example,  1001 in two’s complement would mean .

Converting a number to two’s complement is fairly easy – all of the bits of the positive version of the number are flipped and then we add one.

Starting from 7, being  0111 , inverting the bits gives us  1000 . Adding 1 to this gives us the final value –  1001 .

Finding the first 1 exploits this. Let’s take a more interesting case where the first bit is not 1 already. For 6, we have  0110 . -6 would be  1010 . ANDing these two together gives us  0010  – that equals 2, the position of the first non-zero bit.

This is guaranteed to work for all numbers – once we invert the number, all of the 0 bits that existed will change to 1. Adding one to this has a ripple-like effect where each bit overflows until it finally reaches a spot where there is a 0 to overflow into and turns it into a 1.

This was also a 1 in the original value – we now have two number where the only identical bit position is the first 1. Because of that, ANDing the two together gives us that position only and all of the rest go to 0.

Now we can shift down that many positions to move the 1 to the beginning of the bit field. In the original code, this is done by

This takes the existing value and its negative, ANDs them together to get the first 1 position and finally divides the original number by that position to shift the bit down to the start. Pretty sneaky.

Because we only have five cards, we are guaranteed that there is a maximum of five bits set. Thanks to this, we can compare the value directly to a 5-bit field made up of only 1’s – the value corresponding to this is 31.

If this resolves to true, then we have a straight, as we have five bits in a row all set to 1. There is one hand that we’re missing however – we’ve been working in the case where the Ace is high. We need to check for a straight with a low Ace.

Luckily, there is only one set of cards that will have this – Ace, two, three, four and five. This means that our non-duplicated array will be set as  1 0000 0000 1111 . The value of this field is fairly high – in hexadecimal, it is 403c. We can test directly for this value by checking if our bit field equals it. In the original code,

If this condition is true, then we have a straight. The original code recycles the second unused position in the array to store our straight in.

It also rolls all of this code up into one line, subtracting 3 from the straight’s combined value of 5 ( 0001 + 0001 + 0001 + 0001 + 0001 ) in order to correctly extract the straight value from the array. If we do not have a straight then 1 is subtracted, just to align correctly with the array’s index beginning at 0 as we mentioned earlier.

In more readable code with magic numbers extracted, we could write this as

Awesome! We now have the majority of our hands and the hardest work done. Next up we need to check for flushes, which is much easier.

Flushing

We have a flush if all of our cards’ suits are identical. The check for this is based on a simple idea – if we OR together two identical numbers, the result is the same as the original number. Conversely, if we OR together different numbers, we will end up with a completely different number.

The code checks for this by seeing if the first card’s suit is equal to all of the other cards’ suits ORed together. In code, that is

Relatively very easy. The only other thing we need to check for is a Royal Flush – we are guaranteed that a royal flush will have a rank bit field with a value of 0x7c00 – all of the card positions are set. So we need to check if our bit field has this value.

Finally, we need to fill up our array with the missing values – straight flush, flush and royal flush. The original write-up’s explanation for this is reasonable –

If there is a flush, then this implies that the value in v could only be that of high card or a straight. Subtracting 1 from these indexes turns high card into a flush and turns a straight into a straight flush.

We end up with a hands array with the following values, including one for the royal flush.

Finally, the code checks for the existence of a royal flush, and offsets the index into the hands array. This is all wrapped up into

 And Done

We can now detect all different hands. Here’s the readable form of the code – four lines blown up into something much longer.

Thanks for going through this with me – it was quite an experience working it out. I’m sure that for some people this code was fairly easy to understand – bit manipulation magic is a dark art however, and not one that I’m familiar with. And thanks to subskybox for sending me on this epic journey!