Evaluating poker hands with lookup tables and perfect hashing

Photo credit: NBC/Universal Television

Background: how the table turns

  • 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 Math functions 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

class Card {  constructor( suit, rank ) {
this.suit = suit;
this.rank = rank;
}
compare( otherCard ) {
...code to compare two cards
}
}
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
} );
}

Representing cards as 4-byte unsigned integers

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 7462
Source: Coding The Wheel
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;
}
  • 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 rank by 8, left-shifting suit by 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, then push each onto our result array and return it
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
]

Priced for perfection: evaluating hands with lookup tables and a perfect hash function

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
];
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 ) ];
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 ) ) ];
};
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 ) );
--> 4601
console.log( cactus.handRank( drawFive ) );
--> One pair

Conclusion & further reading

  • 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

--

--

--

Oh geez, Josh Frank decided to go to Flatiron? He must be insane…

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Deploying Python APIs on GCP Cloud Run from Cloud Source Repositories

A Simple Guide To Understanding Control Flow Statements With Python

STM32 Shellcode: firmware dump over UART

Why you should stop using CSS shorthand

A Groovy developer peeks enviously at Kotlin

How to create a custom library in Robot Framework.

LeetCode #380 — Insert Delete GetRandom O(1)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Josh Frank

Josh Frank

Oh geez, Josh Frank decided to go to Flatiron? He must be insane…

More from Medium

Guitar Effects, Streaming Music, and ReactJS. A project for Flatiron School.

Learning about Intelligent Code Completion

Knowing the Difference: DOMContentLoaded and Defer

Frustration

Git Commit Hooks, linting and formatting the code with Prettier before committing it to GitHub…