7 Card Hand Evaluators

[mykey1961]

[ QUOTE ]
[ QUOTE ]
My evaluator uses a perfect minimal hashing technique, and I can get 45 million evaluations per second, which comes down to about 45 cycles per hand.

[/ QUOTE ]
Sounds like your speed is equivalent to D&L's. He's getting between 4.5 and 8 (lol - just put it in a for loop you dummy and get an exact number, you don't have divide by 0.015) billion cycles per second on his machine. Which equates to about 200 million hands/sec under your code.

[/ QUOTE ]


He's a lawyer, he's expected to make those kinds of mistakes. I'll have to send him a bill for $600 to cover the 3 minutes it took to point that out.

[RayW]

[ QUOTE ]
[ QUOTE ]
I just gave the primitive loop as a base to work on, I've just managed to speed mine up a lot by creating arrays holding values to loop through, eliminating the need of all the ORs.

[/ QUOTE ]

I think an updating double linked list of unused cards might allow for faster looping.

[/ QUOTE ]

One fairly fast and easy Way to ignore the used cards:
int cardused[52]; // keep track of cards used

memset(cardused, 0, sizeof(cardused)); // init first

as you use a card
if (cardused[card]) continue; // forget this one...
cardused[card] = 1; // remember it is used

when completed using a card
cardused[card] = 0; // mark this card as available

Ray...

[Mogobu The Fool]

[ QUOTE ]
[ QUOTE ]
Anyway, as soemone noted, there are very few actual hand rankings in poker, because so many hands reduce to the same ranking. In 5-card poker, there are 7462 different rankings. In 7-card poker, there are only 4824 of them.

[/ QUOTE ]

A perfect hash is not what you want.

Since there are 133784560 combos, a perfect hash would produce a hash in the range of 0..133784559 or larger.

If you could devise a hash that wasn't perfect so it overlapped just the right combo of cards, that's still not enough, you also need the value of the hash is in the right order.

[/ QUOTE ]

I'm using the hash to index a lookup table, so order has no impact here.

Since the solution set has less than 5k different values, you can reduce to a hash table which is far smaller than your source set. It's simply a matter of refining the code used to find the perfect hash such that hash collisions are not considered collisions if the value stored in the hash table the same for both inputs. In other words, if two equivalent hands hash to the same element in the hash table, it is not a collision.

[ QUOTE ]

If you notice in creating the hash, for each card, there would be a lookup, shifts, xor's etc. That's gotta be slower than one lookup per card.

[/ QUOTE ]

Actually, it would be against a compressed format where the entire card set is represented in a single 52-bit value. So there would be one "round" of bit manipulations per evaluation. In theory, it could also accomodate 5, 6, and 7 card hands in one function - but then you would need the larger result set of all 7462 possible hands (no big difference, but an efficient function would be harder to find.)

[jukofyork]

[ QUOTE ]
Agreed, Juk... most interesting thread I've seen for a long time. I've been out of poker and coding for months now - have a Corp job in Manhattan again - but I decided to peek back here, and found the most interesting thread by looking for where you've been commenting! [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
Hey, glad to hear the new job is going well. I've also been having been having a break from coding (and poker) over the last month or so, but as always have a whole lot of new ideas built up ready for 2007.

[ QUOTE ]
Some of the techniques here have been making my head flex, which feels good... don't really understand all of them at first read, but thanks, all, for contributing.

Wanted to throw one more wrench in the works for you all; it's what I was planning to look into next time I was revisiting my hand eval code, which will probably never happen now. (Actually, I had dropped my hand-eval code, which was an optimized version of pokeval ported to VB, and started using Keith Rule's C# version, which you can find at codeproject.com.)

Anyway, as soemone noted, there are very few actual hand rankings in poker, because so many hands reduce to the same ranking. In 5-card poker, there are 7462 different rankings. In 7-card poker, there are only 4824 of them. (Yeah, fewer hands with 7 cards. Think of it this way - give yourself the lowest ranking 5-card hand. Now add two cards without making a better hand. Can't. Therefore, a whole set of 5-card hands are impossible in 7-card poker.)

Anyway, since there are only 4824 results, it seems that mapping the 52!/45! different random poker hands to the 4824 results is a natural fit for a perfect hash problem.

There are a couple of well-described perfect hash generators out there (see, for example, http://burtleburtle.net/bob/hash/perfect.html). Anybody take a stab at playing with them for the poker evaluation problem? Run time on finding the perfect hash might be pretty intensive, but once a solution is found, you've got a VERY fast evaluator. You don't even need a minimal perfect hash - a fast hash which maps to a table with 64k entries will still be plenty small in memory, and will potentially allow a great many more solutions.

[/ QUOTE ]
I remember you mentioning this along time ago, but up until recently I never really put much thought into improving hand evaluators; expecting only minimal performance increases possible in the evaluators themselves (how wrong I was!!!).

Anyway, off back to nurse the hangover... Happy new year! Juk [img]/images/graemlins/smile.gif[/img]

[jukofyork]

Nothing to do with a "perfect hash" (or hand evaluators), but just wondered if anybody knew of a better/faster way to do the following.

I use this function to index into a hashtable (of size "NumEllementsPow2") when passed a 64bit key.

<font class="small">Code:</font><hr /><pre>int FoldKey(unsigned long long N,int NumEllementsPow2)
{ // Get the required (index) key from the large 64-bit key.
// This uses the folding method, as the low/high bits of the random number
// generator ar poor on their own.
// NOTE: Do NOT simply and out the requires bit or use modulous as this will
// give a very poor distribution of indexes using the current scheme.

int IndexKey=0;
int I;

// Make sure all bits are used for the index to get a good distribution.
for (I=64-NumEllementsPow2;I&gt;0;I-=NumEllementsPow2)
IndexKey^=(N&gt;&gt;I);
if (I!=0)
IndexKey^=(N&amp;((1&lt;&lt;(I+NumEllementsPow2+1) )-1));

// Take just the bits we need.
return IndexKey&amp;((1&lt;&lt;NumEllementsPow2)-1);

} // End FoldKey.</pre><hr />
In theory I wish I could just use the much faster version (which fails to distribute the hash entries properly...):

<font class="small">Code:</font><hr /><pre>int GetKey(unsigned long long N,int NumEllementsPow2)
{ // Get the required (index) key from the large 64-bit key.
return N&amp;((1&lt;&lt;NumEllementsPow2)-1);
}</pre><hr />

Since I only have to make the hash codes once, I could use a much more computationally expensive random number generator than I currently use, but so far I can't seem to find one which lets me get away with the code above, always requiring the slow FoldKey() function every time I want to map from 64bit key to the hash table index itself...

Does anybody know of a RNG which will let me just take the bottom N bits and still give a good distribution, and/or a faster method by which I could fold the keys?

Juk [img]/images/graemlins/smile.gif[/img]

[Steve Brecher]

[ QUOTE ]
Does anybody know of a RNG which will let me just take the bottom N bits and still give a good distribution, and/or a faster method by which I could fold the keys?

Juk [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
George Marsaglia, who devoted his professional (academic) life to RNGs, posted the following articles to the usenet sci.math group a few years ago. I think you might find them of interest:

http://groups.google.com/group/sci.m...66dd138f?hl=en

http://groups.google.com/group/sci.m...f4d574a5?hl=en

[TheCardGeek]

I don't know if my hand evaluator is faster than yours (We would have to exchange benchmark code wouldn't we?), but I've spent a long time writing evaluators for different games too. I find it faster to use a 64 bit int as a bit mask for my evaluator than using seperate ints to represent the cards. Card order is irrelevant when represented in a bit mask, and you can represent a hand of any number of cards in a single 52 (64) bit integer.

[Phil153]

I believe this is what poker-eval (aka pokersource) uses. The trouble is, those 5 or 7 bits shifts to create the mask, and then the bitwise operations on that mask to determine duplicates, flushedness, and the if...else operations etc all take CPU cycles. Even with lookup tables it's hard to get the CPU cycles down. Every table lookup for bit counts or straight evaluation or whatever is more time gone.

The optimizations in this thread are a step up. Packing a hand into one ulong simply isn't an optimal strategy.

[jukofyork]

[ QUOTE ]
[ QUOTE ]
Does anybody know of a RNG which will let me just take the bottom N bits and still give a good distribution, and/or a faster method by which I could fold the keys?

Juk [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
George Marsaglia, who devoted his professional (academic) life to RNGs, posted the following articles to the usenet sci.math group a few years ago. I think you might find them of interest:

http://groups.google.com/group/sci.m...66dd138f?hl=en

http://groups.google.com/group/sci.m...f4d574a5?hl=en

[/ QUOTE ]
Thanks, I'll give them a try.

Juk [img]/images/graemlins/smile.gif[/img]

[RayW]

Hi,

I finished a consolidated version of the "7 Card Hand Evaluators" written in C. I will comment it tonight and see if I can post it tomorrow... Can I attach 300-400 lines of code to a message (or if it is reasonable to do so?) I did modify things a bit, using a 53 card layout to use the 0 card for current hand strength at 5 and 6 cards. Order doesn't matter, and it gets it all done with an average of less then 10 clock cycles per lookup, about .6 seconds on an amd x2 machine (using one processor for this run) to run the full test at the beginning of this list. File size is: 129,951,336 bytes and the setup program writes out the HandRank file in about a minute.
If you folks know a better way to get the code let me know...
BTW. I have been a lurker on this board for almost 2 years, but this thread is the best I have seen... Keep it goin'!

Ray...