Evaluating poker hands with lookup tables and perfect hashing

Photo credit: NBC/Universal Television

Background: how the table turns

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;
}
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

--

--

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…