7 Card Hand Evaluators

[mykey1961]

[ QUOTE ]
MyKey,

Am I right in saying that your procedure doesn't need a sort for the input cards. If you "train" your array with all the permutations, it would give the correct handrank no matter what order the cards come in (True?).

[/ QUOTE ]

This is correct.

[ QUOTE ]
Another thought is to reduce the size of the array by half by using the 7462 (i.e. unsigned short) possible hand ranks (ref cactus key). Most possibilities for one hand rank group (pairs) is 2860 (12 possible pairs + Combin(12,3) for the other 3 cards) for the bottom 12 bits, while using the top 4 bits for the 9 main hand ranks (high card, pairs, 2pair...). A sixty meg array feels twice as good as a 120 meg one. [img]/images/graemlins/wink.gif[/img]

Thank You for the interesting posts, I am definitely watching with interest.

Thank You,
Ray

[/ QUOTE ]

I lumped everything into one big table for ease of use.

If I used a different table for each # of cards, and sized them to the most efficent 1-byte/2-byte/4-byte, usage would drop from 120Mb down to 90Mb.

I'm not sure that would be the most efficient in terms of speed though.

There may be some time lost when the CPU loads a 16 bit value from an address that isn't a multiple of 4.

Since I was using just 32 bit values, everything was aligned "properly".

[mykey1961]

[ QUOTE ]
I believe it to be a better test bed because with the other test, the cards are presented ordered already, which means that some sort algorithms by nature will out perform others. In this scenario, the two sets of 7 cards are not always ordered (but partially ordered). I think it's a fairer test.

[/ QUOTE ]

This test wouldn't change my times significantly.

int ps1, ps2, ps3, ps4, ps5, ps6, pRank;
int os1, os2, os3, os4, os5, os6, oRank;


holeCard1 = 0;
holeCard2 = 1;

ps1 = Table[holeCard1];
ps2 = Table[ps1+holeCard2];
for(opCard1 = holeCard2 + 1; opCard1 < 51; pCard1++){
cout<<".";cout.flush();
os1 = Table[opCard1];
for(opCard2 = opCard1 + 1; opCard2 < 52; opCard2++)
{// Loop through all the deck cards > holecard2
os2 = Table[os1+opCard1];
for(c1 = holeCard2 + 1; c1 < 48; c1++){
if(c1 == opCard1 || c1 == opCard2)continue;
ps3 = Table[ps2+c1]; os3 = Table[os2+c1];
for(c2 = c1 + 1; c2 < 49; c2++){
if(c2 == opCard1 || c2 == opCard2)continue;
ps4 = Table[ps3+c2]; os4 = Table[os3+c2];
for(c3 = c2 + 1; c3 < 50; c3++){
if(c3 == opCard1 || c3 == opCard2)continue;
ps5 = Table[ps4+c3]; os5 = Table[os4+c3];
for(c4 = c3 + 1; c4 < 51; c4++){
if(c4 == opCard1 || c4 == opCard2)continue;
ps6 = Table[ps5+c4]; os6 = Table[os5+c4];
for(c5 = c4 + 1; c5 < 52; c5++){
if(c5 == opCard1 || c5 == opCard2)continue;
pRank = Table[ps6+c5]; oRank = Table[os6+c5];
// evaluate and tally here}}}}}}}
compare pRank to oRank

[mykey1961]

I modified a version that becomes a large quantity of pointers.

Rank = State0^[c1]^[c2]^[c3]^[c4]^[c5]^[c6]^[c7]

Ain't that pretty?

It also is just a bit faster.

Now a "State" is actually a pointer, to an array of pointers.. etc ... Lions, Tigers, and Bears... oh my.

[RayW]

[ QUOTE ]
I modified a version that becomes a large quantity of pointers.

Rank = State0^[c1]^[c2]^[c3]^[c4]^[c5]^[c6]^[c7]

Ain't that pretty?

It also is just a bit faster.

Now a "State" is actually a pointer, to an array of pointers.. etc ... Lions, Tigers, and Bears... oh my.

[/ QUOTE ]

Interesting tweak,

How are you able to save your trained array? You were saying that it is faster... How long does it take for the thread's test now?

Ray...

[Mogobu The Fool]

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]

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.

[mykey1961]

[ 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]

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 ]


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.

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.

[mykey1961]

[ QUOTE ]
MyKey,

Am I right in saying that your procedure doesn't need a sort for the input cards. If you "train" your array with all the permutations, it would give the correct handrank no matter what order the cards come in (True?).

Another thought is to reduce the size of the array by half by using the 7462 (i.e. unsigned short) possible hand ranks (ref cactus key). Most possibilities for one hand rank group (pairs) is 2860 (12 possible pairs + Combin(12,3) for the other 3 cards) for the bottom 12 bits, while using the top 4 bits for the 9 main hand ranks (high card, pairs, 2pair...). A sixty meg array feels twice as good as a 120 meg one. [img]/images/graemlins/wink.gif[/img]

Thank You for the interesting posts, I am definitely watching with interest.

Thank You,
Ray

[/ QUOTE ]


Since D&L talked about trillions of calculations, and I've been asked how I generate the tables. Here is a partial example of the process I chose to use.

This calculates a StateID for any given 4 card combo. It doesn't have to be lightneing fast, because this is only used to build the tables, not while they are in use.

function Make4(c1, c2, c3, c4 : integer) : int64;
var
ID : int64;
t : integer;
sc : array[1..4] of integer;
begin

// In my "world" 2s = 0, 3s = 1,.....Kc = 50, Ac = 51.
// However in the ID process I prefered that
// 2s = 0x21, 3s = 0x31,.... Kc = 0xD4, Ac = 0xE4
// This allows me to sort in Rank then Suit order

c1 := (((c1 mod 13)+2) shl 4) + (c1 div 13)+1;
c2 := (((c2 mod 13)+2) shl 4) + (c2 div 13)+1;
c3 := (((c3 mod 13)+2) shl 4) + (c3 div 13)+1;
c4 := (((c4 mod 13)+2) shl 4) + (c4 div 13)+1;

// sc[1..4] is a counter of suits (how many spades do I have, etc)

fillchar(sc,sizeof(sc),0);
inc(sc[c1 and $F]);
inc(sc[c2 and $F]);
inc(sc[c3 and $F]);
inc(sc[c4 and $F]);

// if we don't have at least 2 cards of the same suit, we make this card suit 0.

if sc[c1 and $F] < 2 then c1 := c1 and $F0;
if sc[c2 and $F] < 2 then c2 := c2 and $F0;
if sc[c3 and $F] < 2 then c3 := c3 and $F0;
if sc[c4 and $F] < 2 then c4 := c4 and $F0;

// my Q&D sort in Rank then Suit order

repeat
if c1 < c2 then begin t := c1; c1 := c2; c2 := t; end;
if c2 < c3 then begin t := c2; c2 := c3; c3 := t; end;
if c3 < c4 then begin t := c3; c3 := c4; c4 := t; end;
until (c1 >= c2) and (c2 >= c3) and (c3 >= c4);

// the resulting ID is a 64 bit value with each card represented by 8 bits.

ID := c1;
ID := (ID shl 8) + c2;
ID := (ID shl 8) + c3;
ID := (ID shl 8) + c4;
Make4 := ID;
end;

// I cycle thru the 270725 combinations of 4 card hands,
// and save all of the ID's to an array. I sort the array,
// then remove all duplicate ID's. This gives me an array
// of 84448 4-card IDs in sorted order. The value of a
// state, is the index into that array to holds a matching
// StateID.

// EL0 is a pointer to an array of integers
// EL0^[c1] = state1;
// EL1 thru EL6 is an pointer to an array of arrays of integers
// EL1^[state1][c2] = state2;


for c1 := 0 to 48 do
for c2 := c1+1 to 49 do
for c3 := c2+1 to 50 do
for c4 := c3+1 to 51 do
begin

// Check to see if this combo has already been assigned

s4 := EL3^[EL2^[EL1^[EL0^[c1]][c2]][c3]][c4];
if s4 = -1 then
begin

StateID := Make4(c1,c2,c3,c4);

// Binary search for the stateID in the list of StateID's
// keeping the index where we find it

hi := MaxState4; lo := -1; d := -1;
while d <> 0 do
begin
s4 := (hi + lo) shr 1;
d := StateID - StateList4^[s4];
if d < 0 then hi := s4;
if d > 0 then lo := s4;
end;
end;

// We don't need to do all the permutations of 4 cards

EL3^[EL2^[EL1^[EL0^[c1]][c2]][c3]][c4] := s4;
EL3^[EL2^[EL1^[EL0^[c1]][c2]][c4]][c3] := s4;
EL3^[EL2^[EL1^[EL0^[c1]][c4]][c3]][c2] := s4;
EL3^[EL2^[EL1^[EL0^[c4]][c2]][c3]][c1] := s4;
end;
assignfile(f,'Eval3.dat');
rewrite(f,sizeof(TEvalVector));
blockwrite(f,EL3^,MaxState3);
closefile(f);

[Gullanian]

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.

[_D&L_]

I would try using one of the no-sorting algorithms. My "259 mill" a sec algorithm (which i would like to partially retract mykey was right part of the code was optimized out in that test - its more like 145 mill a second with a trivial checksum counter (if rank <> 0 then count ++) - anyways, that algorithm doesn't sort. It rights values in multiple locations in arrays, because flush space (4^7) and number space (13^7) are small tables, and combines them to figure out straight flushes, and flush values. In fact 13^7 and 4^7 are overstatements, because it also has its own version of mapped arrays, and reduction by equivalent or impossible classe...just one mapped array though from 5 card to 7 card (thats my index + subindex).

I'm writing a 52 card mapped array for comparison purposes.
The tables will be much bigger, so we see if size of LU tables slow things down when there is a large difference in size.

[Phil153]

[ 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.