I am no poker player, but I know the basic rules (Texas Hold'em), having casually played one to one games against the computer on a friend's iPad. In the process I got interested in how the computer evaluates the strength of the hands as in quite a few cases an exhaustive enumeration of all possibilities is very long / impossible and in almost all cases a hand evaluator must be really fast to have any practical value...
So, perusing the internet, I ran into SpecialK's blog and was instantly admirative. His algorithm is so elegant, so simple, and therefore lightning fast, that the next time I blinked, I saw the allegory of speed and elegance combined... The glorious vision was something like this.
And it is so improbably fitting computers architecture (specifically 32 bit integers) that there is almost a divine touch to it...
Ok, after the emotion following the discovery, here is some information.
The objective is to evaluate the rank of a full 7 card poker hand: 2 card in the hand, 5 on the board.
Each card has a face, from 1 to 13 (from 2 to Ace), and a suit, from 1 to 4 (spades, hearts, diamonds, clubs). Each face and suit is associated to 2 integers, the first one will be used if the hand is not a flush (face-noflush key), the second if the hand is a flush (face-flush key). Each suit is associated to an integer (suit key).
The suit keys are such that any 2 sums of different 7 suit keys (corresponding to the 7 cards of the evaluated hand) are different.
For face-noflush keys, the best heuristic series I found is {0, 1, 5, 22, 98, 453, 2031, 8698, 22854, 83661, 262349, 636345, 1479181}. No better than SpecialK. An exhaustive search is even less possible in this case. If the higher integer is assumed to be lower than 2^16/7~9362 (to try and fit in 16 bits), the number of candidate series is ~10^42. Out of reach.
No let us check the assumption of about the sizes is valid.
For the 7 card hand evaluator:
4*1479181+3*636345=7825759 < 2^23
So, perusing the internet, I ran into SpecialK's blog and was instantly admirative. His algorithm is so elegant, so simple, and therefore lightning fast, that the next time I blinked, I saw the allegory of speed and elegance combined... The glorious vision was something like this.
And it is so improbably fitting computers architecture (specifically 32 bit integers) that there is almost a divine touch to it...
Ok, after the emotion following the discovery, here is some information.
The objective is to evaluate the rank of a full 7 card poker hand: 2 card in the hand, 5 on the board.
Each card has a face, from 1 to 13 (from 2 to Ace), and a suit, from 1 to 4 (spades, hearts, diamonds, clubs). Each face and suit is associated to 2 integers, the first one will be used if the hand is not a flush (face-noflush key), the second if the hand is a flush (face-flush key). Each suit is associated to an integer (suit key).
The suit keys are such that any 2 sums of different 7 suit keys (corresponding to the 7 cards of the evaluated hand) are different.
The face-noflush keys are such that any 2 sums of different 7 face no flush keys with taken at most 4 times are different.
The face-flush keys are such that any 2 sums of different 5 to 7 face-flush keys with taken at most once are different.
These properties of the suit/face-noflush/face-flush keys are such that a 7 card hand can be associated with a unique set of 2 keys, (i) the sum of the suit keys, (ii-1) the sum of the face-noflush keys if the hand is not a flush or straight flush, or (ii-2) the sum of the face-flush keys if the hand is a flush or straight flush.
Then in order to evaluate a 7 card hand, add up all 7 suit keys. This sum, uniquely associated to this hand, enables to determine whether the hand is a flush or not. If it is not a flush, add up all 7 face-noflush keys. If it is a flush, add up all 7 face-noflush keys. The sum of the relevant face keys is uniquely associated to this hand. Assume a table of all 7 card hand ranks indexed by the relevant face keys was built beforehand, then look up the sum of the relevant face keys and read the hand rank.
Now assume that the largest sum of suit keys + Max[the largest sum of face-noflush keys, the largest sum of face-flush keys] is smaller than 2^32-1. It is already obvious at this stage that the largest sum of face-noflush keys will prevail in the Max[ ] function as the face-noflush keys must be unique over a much larger range of combinations.
Which implies the entire information necessary to determine a hand rank can be stored in an machine integer, specifically an 'unsigned int'. Which in turn allows to define card keys as the juxtaposition of the face-noflush keys and suit keys in the 32 bits available in an integer.
Then practically the hand evaluation works as follows:
(1) sum the 7 card keys
(2) extract the sum of the suit keys using a bit mask/shift
(3) look up the sum of suit keys in a table containing the flush suit if the hand is a flush or a noflush tag
(4) if the hand is not a flush, extract sum of the face-noflush keys using a bit mask/shift
(5) look up the sum of the face-noflush keys in a table containing the hand rank assuming no flush
(4 bis) if the hand is a flush, add up the face-flush keys of the suited cards among the 7 in the hand
(5 bis) look up the sum of the face-flush keys in a table containing the hand rank assuming flush
As you can judge, this hand evaluator is very fast.
If the hand is not a flush (97.11% probability) the method determines the hand rank in 6 additions, 2 bit mask/shift, and 2 table lookups. If the hand is a flush (2.88% probability), add 7 tests and 7 additions. All operations on 32 bit (unsigned for the hand key) integers.
Now, well, do these keys exist ? Are they reasonably small ?
For suit keys, an exhaustive search is feasible. The best result is {0, 1, 29, 37} for {spades, hearts, diamonds, clubs}.
For face-flush, and a fortiori face-noflush keys, the range of possibilities is way to large to explore exhaustively. So a convenient approach is to search lexicographically i.e. to solve the problem for n, and start from this solution to try and determine the solution for n+1, all the way up to 13. Thus the search, however very imperfect, remains tractable, but even so, it takes several hours to find a solution.
The best heuristic series I found is {1, 2, 4, 8, 16, 32, 64, 128, 240, 464, 896, 1728, 3328} for {2, 3, 4,.., Q, K, A}.
Now to search exhaustively taking the heuristic solution as a higher bound, i.e. constraining the higher integer in the series to be 3328 or lower, means to go through ~10^36 candidate series of 13 integers, and each requires more than 10^4 sums to test. Out of reach.
For face-noflush keys, the best heuristic series I found is {0, 1, 5, 22, 98, 453, 2031, 8698, 22854, 83661, 262349, 636345, 1479181}. No better than SpecialK. An exhaustive search is even less possible in this case. If the higher integer is assumed to be lower than 2^16/7~9362 (to try and fit in 16 bits), the number of candidate series is ~10^42. Out of reach.
The equivalent keys for a 5 card evaluator can be:
face-noflush = {0, 1, 5, 22, 94, 312, 992, 2422, 5624, 12522, 19998, 43258, 79415}
face-flush = {0, 1, 2, 4, 8, 16, 32, 56, 104, 192, 352, 672, 1288}
As you can see from the largest face-noflush key, a 5 card hand evaluator is a lot less difficult to create than a 7 card hand evaluator.face-flush = {0, 1, 2, 4, 8, 16, 32, 56, 104, 192, 352, 672, 1288}
No let us check the assumption of about the sizes is valid.
For the 7 card hand evaluator:
4*1479181+3*636345=7825759 < 2^23
7*37=259 < 2^9
23+9=31 < 32
64+128+240+464+896+1728+3328=6848 < 2^13
For the 5 card hand evaluator:
4*79415+3*43258=447434 < 2^19
Finally look up tables are be built.
First, the 5 card hand look up table is built by going through all distinctly ranked hands from the lowest to the highest. There are only 7462 distinctly ranked poker hands, for C(52,5)=2598960 distinct hands. This was a bit of a surprise...
Then, the 7 card look up table is built by going through all distinctly hand ranked hand. Each hand is ranked taking the best 5 card hand it contains. There a are 4824 distinctly ranked poker hands, for C(52,7)=133784560 distinct hands. This can be an even bigger surprise, but the explanation of this paradox lies in the observation that most of the missing hands are in the lowest rankings. The extra 2 cards not used to determine a 7 card hand rank can sometimes only increase the value of the hand. For example, the lowest rank (1, corresponding to 23457 and no flush) is impossible with a 7 card hand. Any additional card necessarily increases the value of the hand.
The flush table is built in the same way. It is a vector of 259 integers containing the suit {1,2,3,4} if the hand is a flush (meaning that 5 or 6 or 7 cards in a 7 card hand are suited), -1 if it is not a flush, and 0 if the index cannot be the sum of suit keys.
The face-noflush table is a vector of 7825759 integers containing a hand rank, or zero if the index cannot be the sum of face-noflush keys.
All the look up tables, in sparse array format but for the smallest ones, are available on this GitHub repository.
23+9=31 < 32
64+128+240+464+896+1728+3328=6848 < 2^13
For the 5 card hand evaluator:
4*79415+3*43258=447434 < 2^19
7*37=259 < 2^9
19+9=28 < 32
104+192+352+672+1288=2608 < 2^12
19+9=28 < 32
104+192+352+672+1288=2608 < 2^12
First, the 5 card hand look up table is built by going through all distinctly ranked hands from the lowest to the highest. There are only 7462 distinctly ranked poker hands, for C(52,5)=2598960 distinct hands. This was a bit of a surprise...
Then, the 7 card look up table is built by going through all distinctly hand ranked hand. Each hand is ranked taking the best 5 card hand it contains. There a are 4824 distinctly ranked poker hands, for C(52,7)=133784560 distinct hands. This can be an even bigger surprise, but the explanation of this paradox lies in the observation that most of the missing hands are in the lowest rankings. The extra 2 cards not used to determine a 7 card hand rank can sometimes only increase the value of the hand. For example, the lowest rank (1, corresponding to 23457 and no flush) is impossible with a 7 card hand. Any additional card necessarily increases the value of the hand.
The flush table is built in the same way. It is a vector of 259 integers containing the suit {1,2,3,4} if the hand is a flush (meaning that 5 or 6 or 7 cards in a 7 card hand are suited), -1 if it is not a flush, and 0 if the index cannot be the sum of suit keys.
The face-noflush table is a vector of 7825759 integers containing a hand rank, or zero if the index cannot be the sum of face-noflush keys.
The face-flush table is a vector of 6848 integers containing a hand rank, or zero if the index cannot be the sum of face-noflush keys.
Now is this coding efficient ? The question applies essentially to the face-noflush look up table. It is relatively large (31.3MB) and essentially empty (99.37%). Could it be made smaller ?
SpecialK found something unbelievable here: It turns out that this table can be folded roughly around its mid point (exactly 4565146) without ANY overlap in the non zero values. Which enables to 'compress' the file to 58.33% of it original size (18.26MB). The counterpart for this reduction in the memory footprint of the table is an additional test and occasionally an extra addition. Bearable.
It did not immediately occur to me how improbable the existence of this folding point is. But if you assume the non zero values in the face-noflush table take up 0.63% of the space and are randomly distributed, then the probability of no overlap is virtually zero (<10^-40). This fact is connected to the birthday paradox, good explanations of which can found on Wikipedia and on the Coursera Cryptography Course (Collision Resistance/Generic Birthday Attack/2mn20s).
It did not immediately occur to me how improbable the existence of this folding point is. But if you assume the non zero values in the face-noflush table take up 0.63% of the space and are randomly distributed, then the probability of no overlap is virtually zero (<10^-40). This fact is connected to the birthday paradox, good explanations of which can found on Wikipedia and on the Coursera Cryptography Course (Collision Resistance/Generic Birthday Attack/2mn20s).
Another solution, much more efficient in terms of memory but also somewhat slower would be to store the table as a sparse array (only the sum and the corresponding hand ranks are stored, the rest being zero by default). The access could still be relatively fast by indexing the hand keys (as a MySQL database does when it is requested to built and INDEX). I have not explored this route as 30MB memory does not seem outrageous and the table can still be stored as a sparse array while not used. Its size is then reduced 36.75 times (852KB).
All the look up tables, in sparse array format but for the smallest ones, are available on this GitHub repository.
Below are two interactive CDFs.
The first displays a 5 card hand having the hand rank you select.
The second displays the hand rank of the 5 card hand you choose.
You can view them with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.
The first displays a 5 card hand having the hand rank you select.
The second displays the hand rank of the 5 card hand you choose.
You can view them with the free CDF (computable document format) player.
The CDFs were created with Mathematica 8.0.4 and the CDF player enables you to locally run Mathematica code.
You may have to 'Enable Dynamics' to view the contents.
