Introduction
In this article, I'll explain how I went from a brute-force poker hand analyzer algorithm to a quick and slick JavaScript implementation — in just four lines of code. The code itself is not considered readable code and therefore perhaps not all that advantageous, but the journey while writing it, proved to be most useful. It was my obsession with bit manipulations, my desire to exploit weakly typed variables and a long-time mission to improve an age old poker algorithm that drove me down the path to poker hand analysis Nerdvana.
Background
When I was a teenager, I programmed a poker game in BASIC on a Commodore 64. It worked. I was proud of myself… but it was painfully slow. It wasn't just that the Commodore 64 had a whopping 1.023 MHz processor, the algorithm to analyze the hand itself, was a deuce. Back in those days, I already had a curiosity for bit manipulations. What I didn't realize at the time, was what you could actually accomplish with all those 1s and 0s. I was yet to discover just how succinct one could be in a weakly typed language such as JavaScript. The fact that a language could allow you to freely slide between a float, an integer and back to boolean had the potential to satisfy my mission:
"Write an algorithm in any language, using mostly bit/mathematical operations such that I
could one day revisit that BASIC code, and give it the speedier algorithm it deserved."
Although this was the original mission, it only loosely served as forward momentum. I had stumbled upon a webpage titled Bit Twiddling Hacks by Sean Eron Anderson. There is some real "magic" happening on this page. Sean had collected the best of the best as far as known bit manipulations and optimizations. This was my introduction to Mersenne numbers, which in the grand scheme of things, became part of the pinnacle operation in the algorithm.
The Code
The four main lines of code are presented here at the top of the rankPokerHand function:
function rankPokerHand(cs,ss) {
var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
...
The function takes two arrays. The cs array is an array of five integers that represent the rank of each card with Aces high (14) — as is typical by many algorithms dealing with cards. The ss array is an array of five integers (flag values) that represent the suit of each card. At first glance, the code can look intimidating. Before I explain this code line by line, the main concept is that there are two bit fields being used to store the rank and rank counts of the poker hand.
The Bit Fields
The first is the s bit field. The purpose of this bit field is to record a 1 bit for each rank – duplicates are lost. Only 13 bits are needed as correspond with the card ranks (2 - Ace). The two LSBs (Least Significant Bits) are not used in order to simplify the loading of this bit field. There is no need to shift these bits to the 13 LSBs as the card rank values are not important here. It is the proximity to their neighbours that is.
Card Ranks (cs) | Bit Fields (s) | Value (hex) |
| 2,3,4,5,6 | [0,0,0,0,0,0,0,0,1,1,1,1,1,0,0] | Not Important |
| 2,4,6,7,9 | [0,0,0,0,0,1,0,1,1,0,1,0,1,0,0] | Not Important |
| A,2,3,4,5 | [1,0,0,0,0,0,0,0,0,1,1,1,1,0,0] | 0x403C |
| 10,J,Q,K,A | [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0] | 0x7C00 |
The second is the v bit field. The purpose of this bit field is to record the count of each rank. There is more than one way to represent this information in a bit field, but ultimately what I wanted was one that could be summed for each rank using the modulus operator and an appropriate Mersenne number. Figuring this out is left to the reader, but essentially this has the power of summing each nibble in the bit field in parallel.
I needed a scheme that would produce a unique value for all combinations of rank duplicates (i.e. 1 pair, 2 pair, 3 of a kind, 4 of a kind, full house).
Here the bit field represents the hand (A,A,Q,Q,9):
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
 | | | | | | | | | | | | |
| A | K | Q | J | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
Each nibble (4 bits) is responsible for capturing the count of each rank. If two of a rank is found, the 2 lower bits of the nibble will be set. If three of a rank is found, the 3 lower bits will be set.
Here is a Full House (A,A,J,J,J):
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | | | | | | | |
| A | K | Q | J | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
And here is a Four of a Kind (K,K,K,K,7):
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | | | | | | | |
| A | K | Q | J | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
From the previous examples, the value of the Ace nibble is 3 (the two low bits are set). It follows that the value of the Jack nibble is 7 (the three low bits are set) and the value of the King nibble is 15(0xF).
Now that you have an understanding of the bit field structures, it’s interesting to note that there are 52 cards in a deck and that a JavaScript floating point number uses 52 bits to store its mantissa.
JavaScript’s 52 bit Floating Point Mantissa
I realize that the details of a floating point number’s binary representation might not interest you. If this is the case then feel free to read ahead to the Line-by-Line Code Breakdown. Otherwise, read on.
JavaScript’s floating point numbers follow the IEEE-754 standard. This standard defines many details, but most important is the way a number is stored in binary form. For a 64 bit IEEE-754 float, the standard dedicates the MSB (Most Significant Bit) as the sign bit. This is common practice for any signed number format. Next, 11 bits are dedicated to recording the exponent and the remaining bits (52) are used to record the normalized mantissa. The standard has problems when dealing with certain decimal number representations (which won’t be discussed here) but for our purposes, it is just perfect.
NOTE: I found a great webpage to help visualize this concept.
In contrast, integers use 32 bits in JavaScript. These numbers allow you to apply bitwise operations to them such as AND(&), OR(|) and XOR(^). This is great for reading and setting individual bits, but this problem needed full access to 52 bits if it was to succeed. As mentioned, JavaScript’s floating point numbers use 64 bits. “Perfect”, I thought – until I realized that you couldn't perform bitwise operations on them. When you do, the floating point number is truncated to the lower 32 bits and implicitly converted to an integer.
After some experimenting, I figured out that I could use standard mathematical operators to achieve the desired effect. Multiplication, division and modulo division were all supported on floats and could be set-up to mask, read and set bits as required.
Line-by-line Code Breakdown
The first line of code is fairly straight-forward:
var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
We initialize our four local variables. The bit fields are v and s, our loop iterator is i and our bit offset is o. As described earlier, the s bit field is initialized with a bit set for each rank in our poker hand.
The next line of code is a loop designed to fill the v bit field with the counts of the ranks in our poker hand:
for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
The first iteration is a wash. It’s simply in place to avoid the redundancy of having to initialize o with the same value it calculates each iteration. The first iteration jumps directly into the body of the loop. Here, v gets incremented by 0 because multiplying by o is a multiplication by 0. Some of you may have noticed that on the other side of the multiplication, is a division by 0. Now some languages are able to optimize and not evaluate the rest of the expression if there is a multiplication by 0, but not JavaScript. Instead, JavaScript evaluates the entire expression. This results in 0/0 = NaN followed by a bitwise AND. JavaScript nicely coerces this operation result back to a 0 and finally adds 1.
Now it’s time to set the bits in our v bit field. This is actually achieved as a series of additions. The reason for this is that JavaScript only allows bit operation on integers. This means we can only set the lower 32 bits, but this strategy needs to set any of 52 bits. I found this could be accomplished using addition. Since no bit would ever be set twice and the body expression would always yield a power of 2, it was safe to do this.
The remaining iterations set i within the range of 0-4 which are the indexes of the card array (cs). Each iteration, our bit offset o gets set to the appropriate offset using Math.pow(2,cs[i]*4) rather than using the much more traditional 1<< cs[i]*4. This is because JavaScript only allows bit shifting on integers. Even though the number is stored as a float, its bits can still be manipulated. The expression in the body nicely bit shifts the desired nibble down to the four LSBs. Here it can easily be masked with 15 (0xF). This step doesn't care that the number is being truncated to 32 bits to perform this bitwise operation because it is only interested in the lower four. Once the bits in question are isolated, 1 is added to the value. This has the effect of setting the next highest bit in the nibble. For example: 0000 becomes 0001, 0011 becomes 0100 and 0111 becomes 1000. Lastly, this value is multiplied by the offset o to bring it back to the correct position. MAGIC!
Actually, the real “magic” is in the third line of code:
v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
The first operation is modulo division. You may be wondering what v % 15 could possibly achieve? If you figured it out earlier, this has the unique property of summing all the values of each nibble in the bit field. The interesting part about it is that regardless of which cards you have, this operation will return the same value based on the unique count of card ranks recorded in the bit field. Using the bit field examples from earlier, you can see that High Card (No Pairs) yields a value of 5, One Pair yields 6, Two Pair yields 7, Three of a Kind yields 9, a Full House yields 10 and Four of a Kind yields 1 (16%15). These values actually fall within the range of 1 to 10 and can act as an index into our poker hands array. So far we have this:
hands = ["4 of a Kind","","","","High Card","1 Pair","2 Pair","","3 of a Kind","Full House"];
Arrays are 0-indexed so we will need to subtract 1 from the value of v. This is what we do in the next operation:
v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
Now it’s time to decipher what is happening in the OR condition. This is checking to see if there is a straight present in the hand. Since our bit field s has a bit set for each rank, a straight would have 5 bits set in sequence. Note that a bit field with the 5 LSBs set is equal to 31:
[0,0,0,0,0,0,0,0,1,1,1,1,1] = 31
By dividing s by its LSB (s&-s) the bit field becomes normalized. This is left to the reader to figure out but a hint is that it requires knowing the representation of an integer in two’s compliment. This condition will be true if a straight exists. There is one exception and that is a straight with the Ace low. Since an Ace is treated as high by default (14), there is one additional thing to check s==0x403c. Looking back to the examples shown earlier, this special case is shown as its bit field representation. If we find that a straight exists, subtract 3 from the value of v. This covers the 1 needed for the 0-indexed array plus an additional 2. Since a straight would only occur if no duplicates were found, the value of v begins as 5 and becomes 2 (i.e. 5-3). Our hands array now looks like this:
hands = ["4 of a Kind","","Straight","","High Card","1 Pair","2 Pair","","3 of a Kind","Full House"];
The final line of code is in place to make the last remaining adjustments. It’s now time to check the information in our suit array (ss):
v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
The first comparison checks to see if we have a flush. JavaScript nicely coerces this boolean into an integer (0 for False and 1 for True). If there is no flush, then the index in v is already correct and we simply subtract 0. 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. There is only one more type of flush remaining, the royal flush. Back to the examples from earlier, the value of a royal flush is s==0x7c00. Since there is only one open position left in out hands array, it is now claimed and we add 5 to v to make the final adjustment. Here is the final code all together:
hands=["4 of a Kind", "Straight Flush", "Straight", "Flush", "High Card",
"1 Pair", "2 Pair", "Royal Flush", "3 of a Kind", "Full House" ];
var A=14, K=13, Q=12, J=11, _ = { "♠":1, "♣":2, "♥":4, "♦":8 };
function rankPokerHand(cs,ss) {
var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
document.write("Hand: " + hands[v] + (s == 0x403c?" (Ace low)":"")+"<br/>");
}
rankPokerHand([10, J, Q, K, A], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] );
rankPokerHand([ 4, 5, 6, 7, 8], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] );
rankPokerHand([ 2, 3, 4, 5, A], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] );
rankPokerHand([ 8, 8, 8, 8, 9], [ _["♠"], _["♣"], _["♥"], _["♦"], _["♠"] ] );
rankPokerHand([ 7, 7, 7, 9, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] );
rankPokerHand([10, J, 6, K, 9], [ _["♣"], _["♣"], _["♣"], _["♣"], _["♣"] ] );
rankPokerHand([10, J, Q, K, 9], [ _["♠"], _["♣"], _["♥"], _["♣"], _["♦"] ] );
rankPokerHand([ 2, 3, 4, 5, A], [ _["♠"], _["♣"], _["♥"], _["♣"], _["♦"] ] );
rankPokerHand([ 4, 4, 4, 8, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] );
rankPokerHand([ 8, 8, J, 9, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] );
rankPokerHand([ 8, 8, 3, 5, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] );
rankPokerHand([10, 5, 4, 7, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] );
Conclusion
Working out the details of this algorithm brought me into many areas of JavaScript and bit operations that I had never explored in the past. Although I will never use this code in any project, getting acquainted with the low level details of a language gave me confidence in knowing that I really understand what’s happening under the hood.
Revision History
- March 31 2013 - Initial revision.
- April 1 2013 - Added tags and fixed typos.
