7 Card Hand Evaluators - Page 16

Steve Brecher · #**151** 01-07-2007, 12:09 AM

I modified RayW's TestHandRank.cpp to do either random hands or enumeration, each with any of three evaluators.

LOOKUP is the mykey1961 big-table evaluator as implemented by RayW; HANDEVAL is mine; EVALN is the pokersource Eval_N.

RANDOM1M is 1,000,000 random hands; ENUMERATE is all 52c7 hands.

For each evaluator/test, the best of three consecutive runs:

LOOKUP/RANDOM1M:
HighPrecision clocks per lookup = 1977.461472

HANDEVAL/RANDOM1M:
HighPrecision clocks per lookup = 112.314720

EVALN/RANDOM1M:
HighPrecision clocks per lookup = 91.655640

LOOKUP/ENUMERATE:
HighPrecision clocks per lookup = 16.126806

HANDEVAL/ENUMERATE:
HighPrecision clocks per lookup = 79.533031

EVALN/ENUMERATE:
HighPrecision clocks per lookup = 81.567737

The source code is at
http://www.stevebrecher.com/misc/TestHandRank.cpp

Smelly Cat · #**152** 01-07-2007, 08:44 PM

I have a pure Java 7-card evaluator with 12 million/sec on 2.2GHz Athlon 3500+. Check it out at:
http://www.jbridge.net/jimmy

Gullanian · #**153** 01-08-2007, 06:38 AM

Just a thought, my evaluator uses the 250MB LUT which is one of it's main downsides, but zipped up it reduces to around 7.5mb due to the large amount of repeating data in it. I know a little about zipping, but don't know how slow it would be to calculate the region you are trying to read in the compressed file. Probably too slow, but it makes a solution that is similar to mine more scalable.

mark007 · #**154** 01-08-2007, 04:04 PM

Hey guys, I found this thread fascinating. I am not very fluent in C++ so my attempt to convert the code to Java didn't seem to work. Did anyone have an attempt to convert the code to other languages yet to see how it performs.

darse · #**155** 01-09-2007, 08:41 PM

For those who haven't achieved full clarity yet, here is a post I made to the Poker Academy forums on the same topic (http://forums.poker-academy.com/viewtopic.php?t=4787).

----

Here is a high-level explanation of the nested table approach, with an example. This is a description of the system I use, which I think is the same as the one in the 2+2 thread (there might be some minor differences, but they should be pretty close since it is the natural thing to do, for some value of "natural").

Imagine six separate tables, corresponding to the number of cards we have currently processed. Each table holds an index value (or a pointer to a particular location) into the next table. It's like a network of pointers, expanding at each stage, but having a branching factor much less than 52 because each set of cards is sorted and reduced to only the essential information.

Let's suppose the first card is the 9h. It is represented as the 1-card hand "9h". The table entry for the 9h contains 52 indices (or pointers) corresponding to the 52 cards in the deck. The pointer for 9h[9h] might point to -1, indicating an error, since a legal hand can't have two 9h.

The second card is the Kc. The hand ID is the full hand sorted by rank and suit, so we currently have the hand "Kc9h". This entry in the second table is pointed to from two places in the first table, namely 9h[Kc] and Kc[9h]. There are 52 out-going pointers for this hand, two of which point to an error state.

The third card is the Kh. Kc9h[Kh] => KhKc9h. There are six different paths through the network leading to this state.

The fourth card is the Qc. KhKc9h[Qc] => KhKcQc9h. We retain the suit information because both hearts and clubs have a potential flush after 7 cards. If this card had been the Qd, then neither diamonds nor clubs could make a potential flush. They would be mapped to a "meta-suit" for no possible flush, which I will call "o" for "offsuit" or "other". Thus, the Qd would have produced KhKc9h[Qd] => KhKoQo9h.

The fifth card is the 2h. KhKcQc9h[2h] => KhKoQo9h2h. Clubs are now irrelevant with respect to possible flushes.

The sixth card is the 5h. KhKoQo9h2h[5h] => KhKoQo9h5h2h. Each entry of the sixth (and largest) table also has 52 out-going pointers, but instead of an index, they contain hand values.

The seventh card is the 7s. KhKoQo9h5h2h[7s] = value(KKQ97) which is 3844. If this had been the 7h, the table entry would contain the value of K9752f, which is 6367.

Note that a 6-card hand with five flush cards can ignore the offsuit card, as it cannot have a bearing on the final value. Thus, the large 6-card table can be reduced in size a little by using a "meta-rank" for "don't care", merging many cases into one. We cannot eliminate the smallest rank of a 6-card flush, however, because it might be part of a straight flush after the seventh card is known.

Note also that the sequential composition of hand IDs uses a lot less memory than more simplistic approaches. This can be further reduced if we dispense with the duplicate cards pointing to an error state, but the indexing gets trickier.

There are two main reasons this method is much faster for systematic enumeration tasks. First, we move most of the work out of the inner-most loops, and do it once instead of repeating it many times. Second, we ensure cache coherence to minimize the number of expensive accesses to main memory. For example, each fetch of an 8K block contains exactly the information that will be needed for the upcoming enumeration cases.

This technique might also be useful for hybrid Monte Carlo simulations over sets of cases, such as all possible river cards for a given 4-card board, or all possible 2-card hands in connection with a random board.

- Darse.

mark007 · #**156** 01-10-2007, 12:57 PM

I have converted the code to Java but when running it, I am getting an out of bounds exception at one point.

I am not an expert on the differences between c++ and java but I think my conversion of the following line may be incorrect.

Code:<hr /><pre>if (suit = holdcards[cardnum] & 0xf) { // find out what suit (if any) was significant
mainsuit = suit; // and remember it
}</pre><hr />

Is suit being assigned to holdcards[cardnum] & 0xf, or being compared to it? Also the problem may lie with the SWAP function. I have created a swap function as follows

Code:<hr /><pre>
public static void SWAP(int I, int J) {
if (workcards[I] < workcards[J]) {
workcards[I]^=workcards[J];
workcards[J]^=workcards[I];
workcards[I]^=workcards[J];
}

}
</pre><hr />

but I am pretty sure this can be converted to

Code:<hr /><pre>
Arrays.sort(workcards);
</pre><hr />

in java as this should sort the array fine.... I'm lost as to where else c++ differs as my code is compiling fine.

RayW · #**157** 01-10-2007, 01:45 PM

Hi!

[ QUOTE ]
Is suit being assigned to holdcards[cardnum] & 0xf, or being compared to it? Also the problem may lie with the SWAP function.

[/ QUOTE ]

The holdcards[cardnum] is bitwise anded with the lower 4 bits to get the suit,
Then it is assigned to the variable suit.
Then if suit is non-zero it will do the mainsuit = suit (the if)

I shouldn't do equalities in IF statements, but it is a weakness of mine...

Out of bounds wouldn't hit you here though... Most likely it is in the MakeID routine, either the sorting or creating the new ID itself. If you can debug and see where the out of bounds error occurs, I might be able to tell you what went wrong... I have a feeling, I seen every out of bounds that could happen in this code! [img]/images/graemlins/grin.gif[/img]

Just know if that the Arrays.sort routine will return the psuedo cards in the lower order bits, and that should work, but if you SWAP routine works, isn't that good enough? Keep in mind that the cards will be pretty much in order already, so if the Arrays.sort routine uses qsort, it would be VERY inefficient (worse than a bubble sort).

Ray...

mark007 · #**158** 01-10-2007, 01:58 PM

Thanks for that Ray. I have changed that line to reflect what it should do (just in more Java friendly terms).

Code:<hr /><pre>
suit=holdcards[cardnum] & 0xf;
if (suit!=0){ // find out what suit (if any) was significant

mainsuit = suit; // and remember it
}
</pre><hr />

and the code runs without problems BUT there seems to be a difference between using Array.sort and the swap function as I get the array out of bounds exception.

Code:<hr /><pre>
public static void SWAP(int I, int J)
{
if (workcards[I] < workcards[J])
{
workcards[I]^=workcards[J];
workcards[J]^=workcards[I];
workcards[I]^=workcards[J];
}
}
</pre><hr />

The out of bounds exception occurs at

Code:<hr /><pre>
while (high - low > 1) {
holdtest = (high + low + 1) / 2;
testval = IDs[holdtest] - ID;
if (testval > 0) high = holdtest;
else if (testval < 0) low = holdtest;
else return holdtest; // got it!!
}
// I guess it couldn't be found so must be added to the current location (high)
// make space... // don't expect this much!

// OUT OF BOUNDS BELOW, high reaches value 612978
IDs[high] = ID; // do the insert into the hole created
numIDs++;
return high;
}
</pre><hr />

Its baffling me because there were very few changes needed in your code, mostly the addition of a few !=0 's...

Any ideas where the code is having problems?

RayW · #**159** 01-10-2007, 05:47 PM

Hi Mark,

I believe the best way to get this working is to put a bit of test code in the MakeID routine to notice when the numcards goes from one level to another and print out the numIDs when it changes. If the count is correct through the 3rd card, but is off on the 4th then you know that it is the grouping function of makeids (or the SWAP or Arrays.sort not working right).

So add just before in MakeID:
int needsuited = numcards - 2;
Code:<hr /><pre>
if (oldnumcards > numcards) {
printf("numcards = %d\tnumIDs = %d\n", numcards, numIDs);
oldnumcards = numcards; // break point here if you need it
}
</pre><hr />
compare the numIDs with the numbers that mkey had, that will tell you a lot.
I would leave it with the SWAP routine if you have a choice.

Does it blow up with the swap in place?

Ray...

mark007 · #**160** 01-10-2007, 06:21 PM

Hi Ray,

I have reverted to the old SWAP and it seems to work perfect (verified it was sorting correctly myself).

I did make the mistake of removing the line

Code:<hr /><pre>
memmove(&IDs[high + 1], &IDs[high], (numIDs - high) * sizeof(IDs[0]));
</pre><hr />

My conversion from this to java would be

Code:<hr /><pre>
System.arraycopy(IDs,high,IDs,(high+1),(numIDs - high) );
</pre><hr />

And all ID's seem to be created now (not sure if they are correct). Java uses the "number of items" when copying from one array to the other, not the amount of data as in C. In this case I got numIDs - high from your code, which seems correct?

The problem is that, now after creating the IDs, when DoEval is ran, after approximately 260000 iterations, I get an out of bounds exception in my eval_7hand routine (which I know for a fact works perfectly).

My eval_7hand sees that the first card it encounters with this ID, has a card value of more than 12 [img]/images/graemlins/frown.gif[/img] Ill do my best to investigate this but I assume it isn't creating the ID correctly at some point.