Evaluating poker hands with lookup tables and perfect hashing
Today’s blog post continues my series on computer poker with a brief exploration of lookup tables and perfect hashes. Huge thanks and acknowledgments are in order before we begin to Kevin Suffecool, Paul Senzee, and Mike Benson — without a doubt the founding fathers of modern computer poker. Feel free to fork/clone my repository to follow along as you read about their work, which has resulted in one of the most diabolically clever algorithms ever written…
Background: how the table turns
A lookup table is, essentially, a “phone book” or “encyclopedia” or “directory.” Instead of using math or logic to parse/return data, it’s often much, much faster to define an array of pre-calculated values — even if that array is very large. Lookup tables have a wide variety of useful and critically important applications:
- Image processing; i.e., converting a color photo to grayscale with a lookup table that stores each color’s corresponding gray value
- Trigonometry: many of JavaScript’s
Mathfunctions use lookup tables as they’re much faster than algebraic calculation - Data validation: lookup tables can match user inputs quickly to valid values
- Database management: lookup tables can speed up frequently-used operations in complex databases with lots of
JOINs
Parsing hands the naïve way
If I were to ask you, dear reader, to write code to parse a poker hand, you might be inclined, for example, to write an ES6 class that looks a bit like this:
class Card { constructor( suit, rank ) {
this.suit = suit;
this.rank = rank;
} compare( otherCard ) {
...code to compare two cards
}}
Or you might decide, as I did at first, to represent a card as something simpler — a primitive datatype like a string or a number:
const fullDeck = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 ];// or, alternately
const fullDeck = [ ...Array( 52 ).keys() ].map( i => i + 1 );function value( hand ) {. // an Array( 5 ) as an argument
const countByPair = [ 0, 0, 0, 0 ];
const countBySuit = [ 0, 0, 0, 0 ];
hand.forEach( card => {
...iterate through each card and update counter
} );
}
Approaches like these make sense intuitively, and thousands have been written thanks to undergraduate computer science courses. The problem? All that sorting, iterating to count ranks/suits, and branching to check for specific hand ranks like flushes is slow as molasses — barely fast enough for basic analysis and nowhere near fast enough for a poker bot or poker strategy tool.
Long ago, in a galaxy far away, an engineer and poker enthusiast named Kevin Suffecool (CactusKev) confronted this problem and sold his soul for a solution: representing cards as bits, then using lookup tables to reduce/eliminate the branching necessary in the approaches above. The code that resulted has been widely admired, discussed and improved upon since. Put on some sunscreen and some goggles — we’re taking a deep dive…
Representing cards as 4-byte unsigned integers
In a previous blog post I wrote about k-combinations, I explained that all card games are combinatorics games: the deck is our collection, and the hand size is our k (combination size/length). Five-card Jacks or Better, the game Vegas video poker is based on, is a 52-combination-5 game, meaning that there are 2,598,960 possible five-card poker hands.
The real genius of CactusKev’s pokerizer is the understanding that many of these hands have the same value. For example, a player holding the hand [ “Ace of Spades", “Jack of Spades", “9 of Spades", “Four of Spades", “2 of Spades" ] (a flush of spades) has a hand ranked exactly the same as a player with [ “Ace of Clubs", “Jack of Clubs", “9 of Clubs", “Four of Clubs", “2 of Clubs" ] (a flush of clubs). These two different hands have the same rank and would therefore tie and split the pot in a game of draw poker. This means that from the nearly 2.6 million unique five-card poker hands, we get only 7,462 unique poker hand ranks:
Hand Value Unique Distinct
Straight Flush 40 10
Four of a Kind 624 156
Full House 3744 156
Flush 5108 1277
Straight 10200 10
Three of a Kind 54912 858
Two Pair 123552 858
One Pair 1098240 2860
High Card 1302540 1277
TOTAL 2598960 7462CactusKev’s approach evaluates each hand to a rank from 7,462 (the lowest possible seven-high hand) to 1 (a royal flush). It does this by representing each card as a four-byte integer: “The high-order bytes are used to hold the rank bit pattern, whereas the low-order bytes hold the [suit & rank] of the card.” Furthermore, each rank is also represented by a prime number, such that multiplying the card’s lowest 6 bits results in a uniquely identifiable multiplicand:
With all this in mind, consider the code below, which returns an array of 52 integers — each a CactusKev poker card:
const fullDeck = () => {
const rankPrimes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ], result = [];
for ( let rank = 0; rank < 13; rank++ ) for ( let suit of [ 8, 4, 2, 1 ] )
result.push( ( rankPrimes[ rank ] ) | ( rank << 8 ) | ( suit << 12 ) | ( ( 1 << rank ) << 16 ) );
return result;
}Let’s break down the bulk of the action on lines 2 and 3:
- Take note we’re representing suits as set bits: 8 (
0b1000) for clubs, 4 (0b0100) for diamonds, 2 (0b0010) for hearts, and 1 (0b0001) for spades - We loop through each possible rank (0 for a two up to 12 for an ace) and each possible suit
- We use bit shifting to set bits in a card integer properly: left-shifting
rankby 8, left-shiftingsuitby 12, and left-shifting the rank bit,1 << rank, by 16 - Finally we use bitwise or
|to smush our set bits together like a PB&J sandwich, thenpusheach onto our result array and return it
The result looks like this:
fullDeck()
--> [
// clubs diamonds hearts spades
98306, 81922, 73730, 69634, // 2
164099, 147715, 139523, 135427, // 3
295429, 279045, 270853, 266757, // 4
557831, 541447, 533255, 529159, // 5
1082379, 1065995, 1057803, 1053707, // 6
2131213, 2114829, 2106637, 2102541, // 7
4228625, 4212241, 4204049, 4199953, // 8
8423187, 8406803, 8398611, 8394515, // 9
16812055, 16795671, 16787479, 16783383, // 10
33589533, 33573149, 33564957, 33560861, // J
67144223, 67127839, 67119647, 67115551, // Q
134253349, 134236965, 134228773, 134224677, // K
268471337, 268454953, 268446761, 268442665 // A
]In the repository/package for this blog post, you’ll see I’ve added a shuffle argument to fullDeck() that randomizes the order of the returned “deck” array. It’s not difficult to understand so I won’t explain it here for the sake of brevity; feel free to see for yourself that fullDeck( shuffled ).slice( 47 ) is just like “drawing” the top 5 cards from a shuffled “deck.”
Priced for perfection: evaluating hands with lookup tables and a perfect hash function
Now that we have a “deck” (an Array( 52 )) of “cards,” it’s time to get to the heavy lifting: parsing hands.
You’ll also see I’ve translated some arrays from CactusKev’s original code in C and stuck them in a file called lookupTables.js, which looks like this:
exports.flushes = [
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, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1599, 0, 0, 0, 0, 0, 0, 0, 1598, 0, 0, 0, 1597, 0, 1596,
...and so on
];exports.fiveUniqueCards = [
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, 1608, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 7462, 0, 0, 0, 0, 0, 0, 0, 7461, 0, 0, 0, 7460, 0,
...and so on
];exports.hashAdjust = [0, 5628, 7017, 1298, 2918, 2442, 8070, 6383, 6383, 7425, 2442, 5628, 8044, 7425, 3155, 6383, 2918, 7452, 1533, 6849, 5586, 7452, 7452, 1533, 2209, 6029, 2794, 3509, 7992, 7733, 7452, 131, 6029, 4491, 1814, 7452, 6110, 3155, 7077, 6675, 532, 1334, 7555, 5325, 3056, 1403, 1403, 3969, ...and so on ];exports.hashValues = [
148, 2934, 166, 5107, 4628, 166, 166, 166,
166, 3033, 166, 4692, 166, 5571, 2225, 166,
5340, 3423, 166, 3191, 1752, 166, 5212, 166,
166, 3520, 166, 166, 166, 1867, 166, 3313,
166, 3461, 166, 166, 3174, 1737, 5010, 5008,
166, 4344, 2868, 3877, 166, 4089, 166, 5041,
...and so on
];
What on earth is this crap!? Looks like huge arrays of random gobbledygook, right? These are, in fact, our lookup tables — each index corresponds to a rank obtained with some simple, fast bitwise operations on all cards in a hand.
Let’s look at the function in our index.js file that makes use of these lookup tables and break it down. We start with some functions to perform our bitwise operations:
exports.flush = hand => hand.reduce( ( total, card ) => total & card, 0xF000 );
// same as exports.flush = hand => hand[ 0 ] & hand[ 1 ] & hand[ 2 ] & hand[ 3 ] & hand[ 4 ] & 0xF000;exports.flushBitPattern = flush => flush.reduce( ( total, card ) => total | card , 0 ) >>> 16;
// same as exports.flushBitPattern = hand => ( hand[ 0 ] | hand[ 1 ] | hand[ 2 ] | hand[ 3 ] | hand[ 4 ] ) >>> 16;exports.flushRank = flush => flushes[ this.flushBitPattern( flush ) ];exports.fiveUniqueCardsRank = hand => fiveUniqueCards[ this.flushBitPattern( hand ) ];
As it turns out, when representing cards this way, bitwise-and-ing each card in a hand with 0xF000 will return 0 if the hand is not a flush! Still more incredibly, bitwise-or-ing each card in a hand and right-shifting the result over 16 bits will yield an index pointing to an element of one of our two lookup tables, flushes or fiveUniqueCards, corresponding to that hand’s rank if the hand is a flush or has five unique cards. Try it and see for yourself!
Take especial note that in the code above, we’re using the unsigned shift operator >>>! That’s because JavaScript is not a strongly-typed language like C; we’ll get some weird incorrect indexes if we use the garden-variety shift operator >>. Feel free to read this blog post I wrote explaining weak typing in JavaScript for a deeper dive into why this is important here.
If the hand is not a flush and doesn’t contain fiveUniqueCards, we’ll next check for twos- or threes-of-a-kind. Here’s where our prime numbers will enter stage right:
exports.primeMultiplicand = hand => hand.reduce( ( total, card ) => total * ( card & 0xFF ), 1 );
// same as exports.primeMultiplicand = hand => ( hand[ 0 ] & 0xFF ) * ( hand[ 1] & 0xFF ) * ( hand[ 2 ] & 0xFF ) * ( hand[ 3 ] & 0xFF ) * ( hand[ 4 ] & 0xFF );exports.findFast = u => {
u += 0xe91aaa35;
u ^= u >>> 16;
u += u << 8;
u ^= u >>> 4;
let a = ( u + ( u << 2 ) ) >>> 19;
return a ^ hashAdjust[ ( u >>> 8 ) & 0x1ff ];
};exports.handRank = hand => {
if ( this.flush( hand ) ) return this.flushRank( hand );
let fiveUniqueCardsRank = this.fiveUniqueCardsRank( hand );
if ( fiveUniqueCardsRank ) return fiveUniqueCardsRank;
return hashValues[ this.findFast( this.primeMultiplicand( hand ) ) ];
};
First, we define a method primeMultiplicand, which bitwise-ands each card with 0xFF. This snips the prime number corresponding to a card’s rank off the end of the card and multiplies them all together.
This prime multiplicand is unfortunately very large, far too large to use directly as an index in a lookup table as with flushes and fiveUniqueCards, so we’ll need a little optimization with a method called findFast — a perfect hash function. Perfect hash functions map pieces of data to integers with no collisions — no two elements will ever produce the same result. Perfect hashes are often used in concert with lookup tables, and they’re used liberally in data management and network monitoring. In this case, they translate a hand’s primeMultiplicand to an index in a lookup table holding ranks for pairs, two-pairs, threes-of-a-kind and full-houses.
Now, at long last, we can tie it all together with a method that returns a handRank for a hand by checking for flushes, then straights/high-card hands (both of which have five unique ranks), then finally for pairs/threes with our perfect hash function:
exports.handRank = hand => {
if ( this.flush( hand ) ) return this.flushRank( hand );
let fiveUniqueCardsRank = this.fiveUniqueCardsRank( hand );
if ( fiveUniqueCardsRank ) return fiveUniqueCardsRank;
return hashValues[ this.findFast( this.primeMultiplicand( hand ) ) ];
};exports.handValue = hand => {
const value = this.handRank( hand );
if ( value > 6185 ) return "High card";
else if ( value > 3325 ) return "One pair";
else if ( value > 2467 ) return "Two pair";
else if ( value > 1609 ) return "Three of a kind";
else if ( value > 1599 ) return "Straight";
else if ( value > 322 ) return "Flush";
else if ( value > 166 ) return "Full house";
else if ( value > 10 ) return "Four of a kind";
else return "Straight flush";
};...in the console...drawFive = fullDeck( true ).slice( 0, 5 );console.log( drawFive.map( cactus.cardName ) );
--> [ 'Nine of Clubs', 'Ten of Clubs', 'Six of Clubs', 'Nine of Diamonds', 'Five of Diamonds' ]console.log( cactus.handValue( drawFive ) );
--> 4601console.log( cactus.handRank( drawFive ) );
--> One pair
Conclusion & further reading
As usual, this shallow dive into lookup tables and perfect hashing doesn’t even begin to do justice to these amazing and crucially important subjects — that’s a job for university computer science departments. Nevertheless I highly recommend some of the below additional resources if you’re interested in exploring the wonderful world of lookup tables:
- Coding The Wheel is a very funny and informative blog with just about the most digestible summary of poker algorithms on the internet, including CactusKev’s lookup tables and various variations/improvements thereof
- This set of lecture notes from Carnegie Mellon University provides an interesting (but dense) introduction to perfect hashing and its applications
- I’ve had this web page bookmarked for more than a decade — Sean Eron Anderson of Stanford University shares some mind-blowing tricks for bit manipulation, many of which rely extensively on lookup tables
