Wednesday, January 24, 2007

7

(Updated 7/10/07)
Inspired by the interest in my 5-card poker hand code that plugs into Cactus Kev's evaluator, I've decided to revisit my unholy 7-card evaluator and make a faster?, cleaner one that I can then post up here.

For the 5-card hash I used Bob Jenkin's Perfect Hashing code. Check out his excellent site for great perfect hashing code & ideas.

My current 7 card evaluator first determines if there is a flush. If not, it looks up the final value in a 13 * 13 * 13 * 13 * 13 * 13 * 13 (13^7, 63M entries) precalc'd table. Arghh! If it is a flush, though, it evaluates all 21 combinations (7 choose 5) in the normal (albeit optimized) way.

But this is not how I want my grandchildren to remember my code. Let's think about other options. Now { 52 choose 7 } yields about 133 million possiblities, right? The first crucial step in thinking about optimizing the seven hand evaluation is figuring out a way to efficiently map every unique set of 7 out of 52 cards to one unique number of the 133 million possiblilities.

As it turns out, I've got some code to do that. Nevertheless, I need to do a little cleanup before I post that. So look for "7 Part II" sometime soon.. ;)

Part II: 52 Choose 7

As promised, code to map any 7 of 52 items (7 of 52 bits) to a unique index in the range of 0-133M (52 choose 7).

index52c7.h

This, of course, could be used for a super-fast 7 card hand evaluator with a precomputed table of size 266mb.

Jing, commenting below mentions that a 2+2 forum has some super-fast seven hand evaluators. Glancing briefly at the site I notice claims of 12.5 cycles per evaluation, which seems too good to be true. After all, a single out-of-cache table lookup can cost much more than that. But if it is true - sweet!

Some Clarifications

Andy Reagan emailed me and made some excellent points concerning the readability of index52c7.h.

"[It's hard] to understand what the code was doing without comments and with the generalized table and variable names.."

I apologize for that. Actually, I wrote another program to generate this file, which is one of the reasons why it's so obtuse. It would probably be a good idea to publish the generator program as well, except that I lost it in a hard drive crash.  There were few casualties, but sadly, that was one of them.

"What does the function index52c7 do?"

Here's the reasoning for index52c7:

We can completely represent a hand of 7 cards of 52 with a single 52-bit number with 7 bits set. We assign each possible card in a deck a number between 1 and 52, inclusive. For example, the Queen/Hearts might be 43 and 2/Spades might be 17. Then, we take a 64-bit number (large enough to contain the 52-bits) and set a bit for each of the 7 cards we have. If two of the seven cards we have are Queen/Hearts and 2/Spades we'd set bits 43 and 17 along with the bits that correspond to the other five cards.

Now, if we had unlimited memory, we could just use this number as an index into an enormous and very sparse array. Unfortunately, this array would have 2^52 (4.5 quadrillion) entries. Assuming two bytes per entry, that would require 9 petabytes of memory! So we need to somehow hash this number into a much smaller space. It turns out that the number of possible combinations of 7 items among 52 is about 133 million (52 choose 7), so ideally, we could somehow hash the 52 bit number into a number between 0 and 133 million that uniquely identifies a given hand.

That's what index52c7 does. It translates the 52 bit hand representation into a much smaller, but still unique number. At two bytes per entry, that gives us a table of 266 megabytes, which is large and in certain cases inconvenient, but certainly doable.

Using, say, Cactus Kev's code to evaluate each possible 7-card hand, we'd first generate the 266MB table and populate it by looking up the corresponding index with index52c7. Now that the table's fully populated, we can just pass index52c7 the 52-bit number and use the resulting index to pull the answer straight out of the array.

21 comments:

Jing said...

There is a discussion for a super fast algorithm at 2+2 forum:

evaluator algorithm

I implemented it in Java. 1 sec for 133 M hands. C or C++ only 200 or 300 msec.

Senzee said...

Hi Jing,

Thanks for the head's up. I'm checking it out!

Anonymous said...

Are you still working on this?
Is Jing's java available?
I will check back for comments since I don't have an account.

Senzee said...

For reference -

Combinadics

http://en.wikipedia.org/wiki/Combinadic

Paul said...

If speed is the goal, you might want to give Super Fast Hash a shot; it's supposed to be faster than Bob Jenkin's algorithm.

Senzee said...

Paul, thanks for the link!

Assuming that you're the same Paul that wrote the SuperFastHash article, let me tell you that I love your site - especially the optimization section (http://www.azillionmonkeys.com/qed/optimize.html). You've clearly put an enormous amount of work into it and it's a phenomenal resource!

Anonymous said...

Hi all,

I have written a 5, 6 and 7 card evaluator in PHP (a language certainly not known for it's speed). It is the simplest evaluator I have ever seen and is made up of about 10 lines of very basic code. It takes 16 microseconds (not milliseconds) to score a 7 card hand.

I have used it in my online Texas Hold'em probability calculator which can be seen at http://texas.holdem.poker.probability.cal.culator.org/

My guess is in C++ this evaluator would beat any other for speed, but I don't know C++.

I'd love to get in touch with anyone interested in the code or interested in porting it to a CLI in C++.

Anyone interested can email me at http://bokehman.com/email

Paul Hsieh said...

The Paul above is not the Paul who wrote that code, because *I* am the Paul that wrote that code. :) You will also find a 5 and 7 card poker evaluator on my site as well:

http://www.azillionmonkeys.com/qed/poker.zip

I haven't bothered to benchmark it against anything, so I don't really know how good it is, but I thought you might be interested in checking it out.

P.S. Glad you like my optimization page.

Benno said...

Is the source code for your ranking system available anywhere? I'm trying to play with a few things involving hand ranks and having trouble finding decent ranking code. =)

Anonymous said...

Hi, I don't know about using such a large table for determining hands, but when I tackled this problem I wasn't limiting myself to a possible number of cards. I wrote a peice of code that takes any number of cards and spits out an integer representing the highest possible hand. When you are doing this hand calculations what do you include for benchmarking? I found that the slow part of my algorithm is loading the cards, not calculating the hand value, so do I include that time in the evaluation? I'm new to this and my code was originally ment to run in a game which didn't need speed as a high priority, any advice on how I can benchmark this? Thanks much. (hillplace@gmail.com)

Anonymous said...

Hi, I am writing a Texas Holdem hand evaluator for my pocket pc, just for learning pusposes. I want to make a table from the different possibilities and want to know how you (using Cactus Kevs' code) evaluate your hand (rank) for 7 cards. Thnx in advance.
Marc

Anonymous said...

Hi,

First of all, thank you for your code.
I am a bit at a loss as to how you chop up the 52-bit number. I suppose you split it up in 4x16bit numbers and then do a sort of representation "packing" with _bitcount and indexing. I cannot see through the choosearrays. What do they represent exactly?
I thank you in advance for your time.
(stellaferox@hotmail.com)

Anonymous said...

Here's an idea which might be even faster than computing index52h7, and also requires smaller arrays.
First, we will check for flush, straight flush or four of a kind (the method will be explained later). So assume that there is no flush, sf or four of a kind. Consider a representation for storing the counts of each denomination. Two bits per denomination, for a total of 26 bits.
Each card is now represented as a count of 1 for that denomination. For example, a four: 01 00 00.
Now take the sum of the seven denominations. The maximum index is 60,817,408.
Now, how to check for flush, sf, or four of a kind. Consider a somewhat different representation of each card. Each denomination will have 3 bits devoted to its count. Each suit will have 3 bits devoted to its count. So for example, king of clubs: 000 001 ...11 groups of 000... 000 000 000 001. (here clubs is the smallest suit, and denominations are ordered normally). Now add the seven cards, and this number: 011 for each suit, 000 for each denomination. Finally, bitwise & with 100 for suit and 100 for denomination. The result is non-zero if and only if there's a flush, sf or four of a kind.

Anonymous said...

Sorry, meant to say 4 bits for a suit in the last section. So binary & with this number for suit: 1000.

Anonymous said...

Hi Paul,
thanks for your hard work!
your fasteval.c was really nice!!

but i´ve got a problem with your index52c7.h, i just dont get how to use it, what should I do with the result from the index52c7 func??
could anyone mail me an expample of how-to use this func?? thanks for your time. mail: phazz@gmx.net
with best regards.

Anonymous said...

Hi Paul,
thanks for your hard work!
your fasteval.c was really nice!!

but i´ve got a problem with your index52c7.h, i just dont get how to use it, what should I do with the result from the index52c7 func??
could anyone mail me an expample of how-to use this func?? thanks for your time. mail: phazz@gmx.net
with best regards.

Bruno said...

Hi Paul,

thats a really good work!

I'm really interested on your 64-bits minimal perfect hash generator. Is it possible for you to publish it?

Thank you very much!!

Anonymous said...

Fantastic post. There's a buildable version of this evaluator over at http://www.codingthewheel.com/archives/poker-hand-evaluator-roundup (code to build the 266MB lookup table from index52c7.h and so forth). Paul: any chance we'll see some more poker-hand-evaluation goodness out of you?

Paul said...

Wow, I'm writing a poker bot, and found myself in need of exactly this! I have a table that has a 4 byte rank for each possible 7 card hands. (so about 500MB)....in reality i only need 20 bits per rank, but i figure 32 will be quicker. I read up on combinadics and was bewildered, but your code works!!!!! I tested it by feeding it every possible input and confirmed it genereated every possible output exactly once. THANK YOU.

Anonymous said...

Hi Paul, I wonder if your hashing algorithm works for less than 7 cards as well? Like, put in an int64 with 4 bits set; would the resulting output still be unique? Or could collisions happen in this case?

It would be great if you could help me with this question!

Anonymous said...

7 card poker hand evaluator
7 card hand evaluator