28 April 2010

A Texas Hold'em 7-card evaluator: Part I

(This post is a continued in Part II here.)

The idea for a new 7-card evaluator was inspired by Cactus Kev's blog, describing his 5-card evaluator. Setting flushes to one side for the time being, his idea is to assign thirteen pairwise distinct prime numbers as the face values of each card. He chooses the first thirteen prime numbers, from 2 to 41 inclusive. Every integer greater than or equal to 2 is uniquely expressed as a finite product of primes so all the information we need regarding the five-card hand modulo flushes can be recovered from the product of its face values, its "signature" or key. This neatly gets around having to worry about whether or how a hand should be presented in some standard form before carrying out a lot of computationally expensive sorting to achieve this. It's a smart thing to do.

On the other hand, we recognised that we really don't need anything like the full power of the fundamental theorem here. For instance we don't need to know that 43*47*53*59*61 is a unique factorisation, and more to the point we don't even need to know that 41*41*41*41*41 is also a unique factorisation because no legitimate poker hand ever contains five cards with the same face value. Pushing this scheme further a legitimate 7-card hand could find itself with the key 143,133,271,933 (~143 billion), equal to the product 41*41*41*41*37*37*37 and corresponding to a 7-card hand comprising all four aces and three of the four kings. An array of short-integers that size would be enormous, requiring almost 280Gb of contiguous memory virtually all of which would go unused. We can use a 5-card evaluator to evaluate 7-card hands but we will always be faced with the overhead of comparing the twenty-one possible 5-card hands from a hand of seven.

With these observations we've found a new key-scheme that gives us just enough uniqueness to correctly identify the integral rank of any 7-card hand, where the greater this rank is the better the hand we hold and two hands of the same rank always draw. We computed by brute force the first thirteen non-negative integers such that the sum of exactly seven with each taken at most four times is unique among all such sums, namely 0, 1, 5, 22, 98, 453, 2031, 8698, 22854, 83661, 262349, 636345 and 1479181. A valid sum might be 0+0+1+1+1+1+5 = 9 or 0+98+98+453+98+98+1 = 846, but invalid sum expressions include 0+262349+0+0+0+1 (too few summands), 1+1+5+22+98+453+2031+8698 (too many summands), 0+1+5+22+98+453+2031+8698 (again too many summands, although 1+5+22+98+453+2031+8698 is a legitimate expression) and 1+1+1+1+1+98+98 (too many 1's).

We assign these integers as the card face values and add these together to generate a key for any non-flush 7-card hand. The largest non-flush key we see is 7825759, corresponding to any of the four quad-of-aces-full-of-kings, and similarly the largest flush key we see is 7999, corresponding to any of the four 7-card straight flushes with ace high. These keys are all small enough to act as indices for all of the ranks stored in two arrays, one for the non-flushes and one for the flushes. The memory footprint can be reduced by mapping the array of 7-card ranks on to a circle of circumference 4565145, again computed by brute force; given the Birthday problem, it seems lucky that such a good circumference should even exist. This all comfortably runs on 32-bit systems.

We expect this schema can be applied in other similar contexts.

An early beta version of this work is now available publicly over on Google Projects under GNU General Public License (GPL). The accuracy of this work is in no way guaranteed by the author and, needless to say, it is to be used entirely at your own risk. We advise that you therefore carry out your own due diligence before making any use of this algorithm. That is, don't just take our word for it that we are correct.

Click SpecialKEvalBeta to begin downloading a .zip file containing the Objective-C, Java and C++ source code files. In doing so you are accepting all of the terms and conditions of the GNU General Public License v3 under which the work is distributed. Please also carefully report any bugs you encounter either by commenting on this article or by sending an e-mail to the address made available here.

The list of references here is not intended to be exhaustive or even representative of what is available online these days, it's just the result of sifting through the first twenty pages or so of a Google search. If there's a hand evaluator you would like to have linked here that is not already listed then by all means let us know and we'll be happy to oblige. If you decide to include my work and ideas in a GPL-project of your own I'd appreciate being openly acknowledged in your work and if you would like us to advertise your project here let us know and we will be happy to oblige.

A commercial-grade evolution of the beta evaluator has been released under a different license and in a different guise on the iTunes Store. It's called "Poker Ace".