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