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

What is Makefile and make? How do we use it?

Unit Testing Delays, Errors & Retries with Kotlin Flows

3 Tips To Avoid Bad Code

VLOG: Design Your Life On Purpose

Dog Fight — Python VS Golang VS Rust for JSON Processing

FUZZY PID CONTROLLERS

What is Quality in Software development….importance of code reviews

CS373 Fall 2021: Week of Sep. 27

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

Breaking the Flappy Bird

Reduce your API calls while searching using Debouncing

Unit tests code style

Unit tests code style

.prototype vs. .__proto__ vs. [[Prototype]], and Creating “new” Objects the OLOO Way