7 Card Hand Evaluators

[A.Nironen]

[ QUOTE ]
PokerBolide.com, wow, just running again and it's superb. My solution used look up tables, some faily large in size, and yours does not seem to at all. Superb.

[/ QUOTE ]
My algorithm does use lookup tables, but they are not big (no more than a couple of megabytes) and they are calculated in a moment at program start.

Andrzej Nironen

[Gullanian]

Dear Andrzej,

Yeah I had kind of guessed that, a no LUT solution would be impossible.

Anyway, I've thought of a new solution that could potentially be incredibly fast without the need of (large) LUT's, keep an eye on this post and I will let you know how it gets on.

Tom

[mykey1961]

[ QUOTE ]
Pretend we have two players that play only two hands:

AK or AA.

First player: AK - 16 combos, AA 6 combos, total 22
First Players chance of playing AK is 16/22
First Players chance of playing AA is 6/22

Now assign the second player:

If player 1 was assigned AK (p = 16/22), then
Player 2: (Baysian updating)
Plays AK with 9/12 probability
Plays AA with 3/12 probability
If player 1 was assigned AA (p = 6/22), then
Player 2: (Baysian updating)
Plays AK with 8/9 probability
Plays AA with 1/9 probability

Now what is Player 2's chance of playing AA
(16/22)*(3/12) + (6/22)*(1/9) = 7/33

Now the problem: Player 1 and Player 2 had the same distributions. But 7/33 != 6/22. The problem is that assigning PLAYER 1 his distribution frist, gives player 2 an unequal chance of getting AA. The player most likely to be dealt pocket pairs, is the one where all the aces are in deck when he gets a card on his distribution. Notice that Player 2's chance of being distributed AA is less than Player 1, regardless of whether Player 1 was dealt AK or AA. (6/22 >> 3/12 or 1/9)

A correct algorithm, would at the very least, have to give both players (with equal distributions) an equal chance of getting AA. Thus, dealing everyone random hands, and discarding until everyone gets a hand on their distribution is an unbiased, but albeit extremely slow method of getting the right answer.

[/ QUOTE ]

Your Baysian process ignores the times where one/both of the players have an unplayable hand.

Of the times both players have playable cards:

Player 1 will have AA, and Player B will have AA with probability 1/41.
Player 1 will have AA, and Player B will have AK with probability 8/41.
Player 1 will have AK, and Player B will have AA with probability 8/41.
Player 1 will have AK, and Player B will have AK with probability 24/41.

[_D&L_]

how fast is pokerboldies?

NM - 35Mil a second.

Anyways I see you are all really smart people (exception Phil). If someone could figure out a way to assign a unique index value between 1 and 133784560 for 7 unordered cards, you could dump everything into a 133 MB lookup table.

I wouldn't mind doing that, since my code isn't really for commercial use, and I think the throughput would go up from my 117 million a second, to maybe a few billion.

But, i haven't figured out a way to assign a unique ID to 7 unordered, (up to 52 - noduplicating) numbers. At least not a method that doesn't require putting them in order first, which might negate the speed advantages.

[jukofyork]

[ QUOTE ]
how fast is pokerboldies?

NM - 35Mil a second.

Anyways I see you are all really smart people (exception Phil). If someone could figure out a way to assign a unique index value between 1 and 133784560 for 7 unordered cards, you could dump everything into a 133 MB lookup table.

I wouldn't mind doing that, since my code isn't really for commercial use, and I think the throughput would go up from my 117 million a second, to maybe a few billion.

But, i haven't figured out a way to assign a unique ID to 7 unordered, (up to 52 - noduplicating) numbers. At least not a method that doesn't require putting them in order first, which might negate the speed advantages.


[/ QUOTE ]
I tried something similar to this as a method to speed existing hand evaluators: Using the idea of Combinadics it's possible to assign a unique lexicographical index for each ordered combination.

If the hand is represented by a 52 bit number with 7 bits set true to indicate which cards you have in your hand (ie: like pokersource's "packed" format), then you can calculate the lexicographical index as though the cards are ordered (ie: the bitstring representation orders them implicitly) by traversing the bitstring from the least(/most) significant bit.

The naive approach would require testing and summation of each of the 52 bits individually, but using a lookup table it is possible to create partial sums of C() and do whole blocks of 16 bits at a time and thus just do 4 summations rather than all 52 (actually it's possible to do just 3 if you use 18 bits, but this requires 4x more memory to hold the lookups).

The idea is then that we can use the lexicographic index we created to then index into another lookup of 133784560 precomputed 16bit hand evaluations (this means you can use any old [unoptimized] hand evaluator and just concentrate on optimizing the lookup accessing code...).

I tested the idea out very quickly just using the pokersource hand evaluator to create the lookup, and managed to get aprroximately a 2x speedup (21 million hands/sec -> 42 million hands/sec on a 3GHz P4), at the expense of using about 500MB of lookup tables.

I haven't yet tried optimizing the generated assembler (which looked fairly suboptimal) nor have I yet tried using the x86's special BSF/BSR instructions to scan the bitstring (using BSF/BSR we can do just 7 summations and without the need for 2d/3d index dereferencing used by the partial sum method outlined above).

<font class="small">Code:</font><hr /><pre>// FastHandEval.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "random.h"
#include &lt;Crtdbg.h&gt;
#include &lt;time.h&gt;

#include &lt;iostream&gt;

#ifdef __cplusplus
extern "C" {
#include "poker_defs.h"
#include "deck_std.h"
#include "inlines/eval.h"
}
#else
#include "poker_defs.h"
#include "inlines/eval.h"
#endif

using namespace std;

// How mnay iterations do we want to run the etsts on.
#define ITERS 1000000000

// How many tests shall we generate.
#define NUM_TESTS 10000

// Precomputed combination lookups (huge factorials like 52! are a pain to generate here...).
int C[52][8]={
{0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0},
{0,2,1,0,0,0,0,0},
{0,3,3,1,0,0,0,0},
{0,4,6,4,1,0,0,0},
{0,5,10,10,5,1,0,0},
{0,6,15,20,15,6,1,0},
{0,7,21,35,35,21,7,1},
{0,8,28,56,70,56,28,8},
{0,9,36,84,126,126,84,36},
{0,10,45,120,210,252,210,120},
{0,11,55,165,330,462,462,330},
{0,12,66,220,495,792,924,792},
{0,13,78,286,715,1287,1716,1716},
{0,14,91,364,1001,2002,3003,3432},
{0,15,105,455,1365,3003,5005,6435},
{0,16,120,560,1820,4368,8008,11440},
{0,17,136,680,2380,6188,12376,19448},
{0,18,153,816,3060,8568,18564,31824},
{0,19,171,969,3876,11628,27132,50388},
{0,20,190,1140,4845,15504,38760,77520},
{0,21,210,1330,5985,20349,54264,116280},
{0,22,231,1540,7315,26334,74613,170544},
{0,23,253,1771,8855,33649,100947,245157},
{0,24,276,2024,10626,42504,134596,346104},
{0,25,300,2300,12650,53130,177100,480700},
{0,26,325,2600,14950,65780,230230,657800},
{0,27,351,2925,17550,80730,296010,888030},
{0,28,378,3276,20475,98280,376740,1184040},
{0,29,406,3654,23751,118755,475020,1560780},
{0,30,435,4060,27405,142506,593775,2035800},
{0,31,465,4495,31465,169911,736281,2629575},
{0,32,496,4960,35960,201376,906192,3365856},
{0,33,528,5456,40920,237336,1107568,4272048},
{0,34,561,5984,46376,278256,1344904,5379616},
{0,35,595,6545,52360,324632,1623160,6724520},
{0,36,630,7140,58905,376992,1947792,8347680},
{0,37,666,7770,66045,435897,2324784,10295472},
{0,38,703,8436,73815,501942,2760681,12620256},
{0,39,741,9139,82251,575757,3262623,15380937},
{0,40,780,9880,91390,658008,3838380,18643560},
{0,41,820,10660,101270,749398,4496388,22481940},
{0,42,861,11480,111930,850668,5245786,26978328},
{0,43,903,12341,123410,962598,6096454,32224114},
{0,44,946,13244,135751,1086008,7059052,38320568},
{0,45,990,14190,148995,1221759,8145060,45379620},
{0,46,1035,15180,163185,1370754,9366819,53524680},
{0,47,1081,16215,178365,1533939,10737573,62891499} ,
{0,48,1128,17296,194580,1712304,12271512,73629072} ,
{0,49,1176,18424,211876,1906884,13983816,85900584} ,
{0,50,1225,19600,230300,2118760,15890700,99884400} ,
{0,51,1275,20825,249900,2349060,18009460,115775100 }
};

// Used to store the precomuted 16bit partial sums of C(a,b) along with the current set-bit count.
typedef struct LookupType {
unsigned int Index16;
unsigned char Count16;
} LookupType;

// The main lookup for the combinadic partial sums.
LookupType LookupTable[4][0x10000][8];

// Used to pregenerate the tests.
unsigned long long TestL[NUM_TESTS];
unsigned int Tests[NUM_TESTS][2];

// The eval lookup indexed using the lexicographical index.
unsigned int Evals[133784560];

// -------------------------------------------------------------------------------------

// Had to put this here to avoid problems with nested macros in the pokersource lib...
void GenLookup(CardMask &amp;PossibleExtraCards) {

unsigned int InputA,InputB;
int Index;
int J;

// This holds all of the cards we have used so far.
CardMask AllUsedCards;
CardMask_RESET(AllUsedCards);

uint64 T=(uint64)PossibleExtraCards.cards.spades
|((uint64)PossibleExtraCards.cards.clubs&lt;&lt;13 )
|((uint64)PossibleExtraCards.cards.diamonds&lt;&lt ;26)
|((uint64)PossibleExtraCards.cards.hearts&lt;&lt;3 9);

InputA=T;
InputB=(T&gt;&gt;32)&amp;(0x100000-1);

Index=LookupTable[0][InputA&amp;0xffff][0].Index16;
J=LookupTable[0][InputA&amp;0xffff][0].Count16;
Index+=LookupTable[1][InputA&gt;&gt;16][J].Index16;
J=LookupTable[1][InputA&gt;&gt;16][J].Count16;
Index+=LookupTable[2][InputB&amp;0xffff][J].Index16;
J=LookupTable[2][InputB&amp;0xffff][J].Count16;
Index+=LookupTable[3][InputB&gt;&gt;16][J].Index16;

// Use the pokersource lib to create the evaluation value for the lookup.
Evals[Index]=Hand_EVAL_N(PossibleExtraCards,7);
}

// -------------------------------------------------------------------------------------

void InitLookups(void) {

// This hold the emumerated turn and river card combos.
CardMask PossibleExtraCards;

// Clear the lookups.
for (int InputX=0;InputX&lt;4;InputX++) {
for (int InputY=0;InputY&lt;0x10000;InputY++) {
for (int Count=0;Count&lt;8;Count++) {
LookupTable[InputX][InputY][Count].Index16=0;
LookupTable[InputX][InputY][Count].Count16=0;
}
}
}

// Create the lookups.
for (int InputX=0;InputX&lt;4;InputX++) {
for (int InputY=0;InputY&lt;0x10000;InputY++) {
int CurrentInput=InputY;
for (int StartCount=0;StartCount&lt;7;StartCount++) {
int CurrentCount=StartCount;
for (int I=0,J=1;I&lt;16 &amp;&amp; CurrentCount&lt;7;I++) {
if ((CurrentInput&gt;&gt;I)&amp;1LL) {
LookupTable[InputX][InputY][StartCount].Index16+=C[(InputX*16)+I][(CurrentCount++)+1];
}
}
LookupTable[InputX][InputY][StartCount].Count16=CurrentCount;
}
}
}

// Clear to be sure (no need really)...
for (int I=0;I&lt;133784560;I++) {
Evals[I]=0;
}

// Make the ranking lookups.
// ### NOTE: This will mess up if Hand_EVAL_N is nested in it...
DECK_ENUMERATE_N_CARDS(StdDeck,PossibleExtraCards, 7,
{
GenLookup(PossibleExtraCards);
}); // End Enumerate all combos.

}

// -------------------------------------------------------------------------------------

void InitTests(void) {

// lets make the tests.
for (int I=0;I&lt;NUM_TESTS;I++) {
TestL[I]=0;
for (int T=0;T&lt;7;T++) {
int R;
do {
R=RandInt(51);
} while ((TestL[I]&gt;&gt;R)&amp;1LL);
TestL[I]|=(1LL&lt;&lt;R);
}
Tests[I][0]=TestL[I]&amp;0xffffffff;
Tests[I][1]=(TestL[I]&gt;&gt;32)&amp;0xffffffff;
}

}

// -------------------------------------------------------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
int J;

unsigned int InputA,InputB;
int Index;

unsigned int MyEval;

// Make the looups and the test data.
cout &lt;&lt; "Creating Lookups &amp; Tests... "; cout.flush();
InitLookups();
InitTests();
cout &lt;&lt; "Done." &lt;&lt; endl;

// Store the start time.
clock_t StartTime=clock();

for (int K=0;K&lt;ITERS;K++) {

// Get the lexicographical index.
InputA=Tests[K%NUM_TESTS][0];
InputB=Tests[K%NUM_TESTS][1];

Index=LookupTable[0][InputA&amp;0xffff][0].Index16;
J=LookupTable[0][InputA&amp;0xffff][0].Count16;
Index+=LookupTable[1][InputA&gt;&gt;16][J].Index16;
J=LookupTable[1][InputA&gt;&gt;16][J].Count16;
Index+=LookupTable[2][InputB&amp;0xffff][J].Index16;
J=LookupTable[2][InputB&amp;0xffff][J].Count16;
Index+=LookupTable[3][InputB&gt;&gt;16][J].Index16;

// Use the evaluation index by the lexicographical index.
MyEval=Evals[Index];

/********* UNOPTIMIZED COMPARISON (HACKY CRAP...) **********
CardMask TestCards;
TestCards.cards.spades=TestL[K%NUM_TESTS];
TestCards.cards.clubs=TestL[K%NUM_TESTS]&gt;&gt;13;
TestCards.cards.diamonds=TestL[K%NUM_TESTS]&gt;&gt;26;
TestCards.cards.hearts=TestL[K%NUM_TESTS]&gt;&gt;39;

// Use the original pokersource eval function fior camparison.
MyEval=Hand_EVAL_N(TestCards,7);
************************************************** *********/

}

// Print this heare to force the optimizing compiler to not ignore the above loop...
cout &lt;&lt; MyEval &lt;&lt; endl;

// Print the timings.
cout &lt;&lt; (double)(clock()-StartTime)/(double)CLOCKS_PER_SEC &lt;&lt; " seocnds" &lt;&lt; endl;
cout &lt;&lt; (int)((double)ITERS/((double)(clock()-StartTime)/(double)CLOCKS_PER_SEC)) &lt;&lt; " hands per second" &lt;&lt; endl;

return 0;
}</pre><hr />

NOTE: To use the above code you need both the pokersource hand evaluation library (or you can use ANY hand eval library so long as you set the Evals[133784560] correctly) and a function "RandInt(X)" which generates a random integer in the range {0..X}.

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

PS: Sorry the code is very hacky, but I just wrote this to test it out quickly today and didn't spend much time on it. Hopefully it should help explain the method I outlined above.

[_D&L_]

Great post Juk. I gotta book mark this one, so i can come back and study it. I don't know C++ (or combinadics theory) so its like learnign two things at once .

[Gullanian]

Just a note D&amp;L, you don't need to return a number between 1 and 130 million for the strength of a hand, you can collapse the hands into unique equivalence classes, which there turn out to be about 7,500 unqiue hands.

[Gullanian]

Also, because my evaluator has been beaten hands down, I will publish my technique very soon. I'll post a link in this thread when it is done.

[Gullanian]

Jukofyork has basically done what I have done in my technique, looking at the lexographical index of all precomputing hand ranks. The ordering part of my code is the best, classical sorting algorithms are too slow for this job.

[A.Nironen]

[ QUOTE ]
If someone could figure out a way to assign a unique index value between 1 and 133784560 for 7 unordered cards, you could dump everything into a 133 MB lookup table.


[/ QUOTE ]
Single byte for hand's strength is not enough, so the table must be 266 MB at least.

Andrzej Nironen