Lateral thinking in Action
The problem: compare poker hands to see which is better. The traditional way is to give each a score and compare but there's a clever way of doing it invented by "Cactus Kev". There are 2,598,960 possible poker hands.
What he did was realize that because there are particular hands are the same (e.g. 4 Royal flushes is 1 Flush ), the actual number of distinct hands reduces to 7,462. So his evaluator just looks up a hand and finds its score from basically a look up table. But there's more. To get round needing to sort cards, he devised a scheme where each card had a prime number value and multiplied them together. This has been further improved by a perfect hash by Paul Senzee who has put his C code into the public domain. Can anyone else improve on this?
- Link to C Tutorials
Okay. I’ve got it! Robert C. Cartaino’s Ultimate Poker Hand Evaluator (patent pending):
Assign each card in the deck a value (52 cards with a value 0-51). A “hand” is represented in a 52-bit data type where each bit represents a card in the hand (one bit set for each card in the hand). The value of the resulting 52-bit number is used as an index into a lookup table containing the relative strength of each hand which has been pre-computed. So we have:
long handIndex = card1bit | card2bit | card3bit … etc;
short handStrength = lookupTable[handIndex];
The hand with the highest hand strength wins. Blazingly fast!
Unfortunately, with a 52-bit index, the lookupTable needs to be more than 90,000 TerraBytes long (90 million gigabytes), which is about 700,000 times what 64-bit Vista Ultimate can handle.
Okay. How about this? Maybe we can come up with a hash function that can map 4.5 quadrillion keys into about 7,462 values without any collisions. I’m gonna need some caffeine.
Robert C. Cartaino
Why such a large number? I reckon that you can store a card in 6 bits. 2 bits for the suite and 4 bits for the value. So for five cards that’s 30 bits i.e. a 32 bit int.
The score occupies another 2 bytes (1..7,462). So that’s 6 bytes per card + score. Multiply that by 2,598,960 = 15,593,760, ie under 16MB.
Of course there’s the time for bit packing the 5 cards into 30 bits.