![]() |
|
#121
|
|||
|
|||
|
[ QUOTE ]
I will comment it tonight and see if I can post it tomorrow ... 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'! [/ QUOTE ] I totally agree about this thread. It's exciting to see this kind of progress. I'm one of the old pokersource / poker-eval maintainers and I didn't imagine that such gains were possible. In fact, I was coming around to the opinion that the Age of Lookup Tables had passed, thanks to the increasing gap between the time for one instruction and the latency of a cache miss. I thought the next generation of poker-eval would drop all memory accesses and just concentrate on a fast, totally cached instruction stream. Anyway, if any of you feel like sharing code, I'd be happy to add it to the pokersource library. Although all the current code is GPL, you would be free to apply a different license like Apache or whatever to your contributions. As for Ray's C version, if you post that I volunteer to port it to Java. It would be nice to have a superfast java evaluator that people could use without the hassles that come with JNI in the current pokersource code. By the way, the pokersource discussion group is at: http://tech.groups.yahoo.com/group/pokersource/ -pyg |
|
#122
|
|||
|
|||
|
WAY over my head, but I have to agree, one of the most interesting threads in a long time... from the OP:
[ QUOTE ] Hi all, new user but was told this was a good poker forum! Not sure if this is the right place to post, please move if it is not. [/ QUOTE ] So glad you did [img]/images/graemlins/smile.gif[/img] dave. |
|
#123
|
|||
|
|||
|
RayW:[ QUOTE ]
... Can I attach 300-400 lines of code to a message (or if it is reasonable to do so?) [/ QUOTE ]I don't see why not (although I hope replies to it won't quote the whole thing [img]/images/graemlins/blush.gif[/img] ) ...Not to discourage you from contributing to the pokersource library c/o pygmyhipo. |
|
#124
|
|||
|
|||
|
I'd like to show my code, but firstly this is partly for my dissertation so I think my university owns part of it, and secondly, 40 clock cycles and a 250mb lookup is a lot worse than what some other people here have!
|
|
#125
|
|||
|
|||
|
Well, Results are in:
BAD!! = 0 High Card = 23294460 Pair = 58627800 Two Pair = 31433400 Three of a Kind = 6461620 Straight = 6180020 Flush = 4047644 Full House = 3473184 Four of a Kind = 224848 Straight Flush = 41584 Total Hands = 133784560 Validation seconds = 0.5620 Total HighPrecision Clocks = 1127079718 HighPrecision clocks per lookup = 8.424587 This uses Cactus Kev's Eval Routine ref http://www.suffecool.net/poker/evaluator.html Which I moved Paul D. Senzee's Optimized Hand Evaluator ref http://www.geocities.com/psenzee/code/fast_eval.c eval_5hand_fast(int c1, int c2, int c3, int c4, int c5) routine into Cactus Kevs eval_5hand routine. You will need to add the routines in PokerLib.c to poker.h file. Here is the main code which I called HandRankSetup.cpp: <font class="small">Code:</font><hr /><pre> // HandRankSetup.cpp : Sets up the HandRank File for VERY fast Lookups // by Ray Wotton and the 2+2 list My code is GPL, use it as you like #include "stdafx.h" #include "windows.h" #include "poker.h" #include <stdlib.h> #include <string.h> #include <time.h> const char HandRanks[][16] = {"BAD!!","High Card","Pair","Two Pair","Three of a Kind","Straight","Flush","Full House","Four of a Kind","Straight Flush"}; __int64 IDs[612978]; int HR[32487834]; int numIDs = 1; int numcards = 0; int maxHR = 0; __int64 maxID = 0; __int64 MakeID(__int64 IDin, int newcard) // adding a new card to this ID { __int64 ID = 0; int suitcount[4 + 1]; int rankcount[13 + 1]; int workcards[8]; // intentially keeping one as a 0 end int cardnum; int getout = 0; memset(workcards, 0, sizeof(workcards)); memset(rankcount, 0, sizeof(rankcount)); memset(suitcount, 0, sizeof(suitcount)); for (cardnum = 0; cardnum < 6; cardnum++) { // can't have more than 6 cards! workcards[cardnum + 1] = (int) ((IDin >> (8 * cardnum)) & 0xff); // leave the 0 hole for new card } // my cards are 2c = 1, 2d = 2 ... As = 52 newcard--; // make 0 based! workcards[0] = (((newcard >> 2) + 1) << 4) + (newcard & 3) + 1; // add next card formats card to rrrr00ss for (numcards = 0; workcards[numcards]; numcards++) { suitcount[workcards[numcards] & 0xf]++; // need to see if suit is significant rankcount[(workcards[numcards] >> 4) & 0xf]++; // and rank to be sure we don't have 4! if (numcards) { if (workcards[0] == workcards[numcards]) { // can't have the same card twice getout = 1; // if so need to get out after counting numcards } } } if (getout) { return 0; // duplicated another card (ignore this one) } int needsuited = numcards - 2; // for suit to be significant - need to have n-2 of same suit if (numcards > 4) { for (int rank = 1; rank < 14; rank++) { if (rankcount[rank] > 4) { // if I have more than 4 of a rank then I shouldn't do this one!! return 0; // can't have more than 4 of a rank so return an ID that can't be! } } } // 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 // if we don't have at least 2 cards of the same suit for 4, we make this card suit 0. if (needsuited > 1) { for (cardnum = 0; cardnum < numcards; cardnum++) { // for each card if (suitcount[workcards[cardnum] & 0xf] < needsuited) { // check suitcount to the number I need to have suits significant workcards[cardnum] &= 0xf0; // if not enough - 0 out the suit - now this suit would be a 0 vs 1-4 } } } // Sort Using XOR. Network for N=7, using Bose-Nelson Algorithm: Thanks to the thread! #define SWAP(I,J) {if (workcards[I] < workcards[J]) {workcards[I]^=workcards[J]; workcards[J]^=workcards[I]; workcards[I]^=workcards[J];}} SWAP(0, 4); SWAP(1, 5); SWAP(2, 6); SWAP(0, 2); SWAP(1, 3); SWAP(4, 6); SWAP(2, 4); SWAP(3, 5); SWAP(0, 1); SWAP(2, 3); SWAP(4, 5); SWAP(1, 4); SWAP(3, 6); SWAP(1, 2); SWAP(3, 4); SWAP(5, 6); // long winded way to put the pieces into a __int64 // cards in bytes --66554433221100 // the resulting ID is a 64 bit value with each card represented by 8 bits. ID = (__int64) workcards[0] + ((__int64) workcards[1] << 8) + ((__int64) workcards[2] << 16) + ((__int64) workcards[3] << 24) + ((__int64) workcards[4] << 32) + ((__int64) workcards[5] << 40) + ((__int64) workcards[6] << 48); return ID; } int SaveID(__int64 ID) { if (ID == 0) return 0; // don't use up a record for a 0! if (ID >= maxID) { // take care of the most likely first goes on the end... if (ID > maxID) { // greater than create new else it was the last one! IDs[numIDs++] = ID; // add the new ID maxID = ID; } return numIDs - 1; } // find the slot I will find it (by a pseudo bsearch algorithm) int low = 0; int high = numIDs - 1; __int64 testval; int holdtest; 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! memmove(&IDs[high + 1], &IDs[high], (numIDs - high) * sizeof(IDs[0])); IDs[high] = ID; // do the insert into the hole created numIDs++; return high; } int DoEval(__int64 IDin) { // I guess I have some explaining to do here... I used the Cactus Kevs Eval ref http://www.suffecool.net/poker/evaluator.html // I Love the pokersource for speed, but I needed to do some tweaking to get it my way // and Cactus Kevs stuff was easy to tweak ;-) int handrank = 0; int cardnum; int workcard; int rank; int suit; int mainsuit = 20; // just something that will never hit... need to eliminate the main suit from the iterator int suititerator = 0; int holdrank; int workcards[8]; // intentially keeping one as a 0 end int holdcards[8]; int numevalcards = 0; // See Cactus Kevs page for explainations for this type of stuff... const int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 }; memset(workcards, 0, sizeof(workcards)); memset(holdcards, 0, sizeof(holdcards)); if (IDin) { // if I have a good ID then do it... for (cardnum = 0; cardnum < 7; cardnum++) { // convert all 7 cards (0s are ok) holdcards[cardnum] = (int) ((IDin >> (8 * cardnum)) & 0xff); if (holdcards[cardnum] == 0) break; // once I hit a 0 I know I am done numevalcards++; // if not 0 then count the card if (suit = holdcards[cardnum] & 0xf) { // find out what suit (if any) was significant mainsuit = suit; // and remember it } } for (cardnum = 0; cardnum < numevalcards; cardnum++) { // just have numcards... workcard = holdcards[cardnum]; // convert to cactus kevs way!! ref http://www.suffecool.net/poker/evaluator.html // +--------+--------+--------+--------+ // |xxxbbbbb|bbbbbbbb|cdhsrrrr|xxpppppp| // +--------+--------+--------+--------+ // p = prime number of rank (deuce=2,trey=3,four=5,five=7,...,ace=41) // r = rank of card (deuce=0,trey=1,four=2,five=3,...,ace=12) // cdhs = suit of card // b = bit turned on depending on rank of card rank = (workcard >> 4) - 1; // my rank is top 4 bits 1-13 so convert suit = workcard & 0xf; // my suit is bottom 4 bits 1-4, order is different, but who cares? if (suit == 0) { // if suit wasn't significant though... suit = suititerator++; // Cactus Kev needs a suit! if (suititerator == 5) // loop through available suits suititerator = 1; if (suit == mainsuit) { // if it was the sigificant suit... Don't want extras!! suit = suititerator++; // skip it if (suititerator == 5) // roll 1-4 suititerator = 1; } } // now make Cactus Keys Card workcards[cardnum] = primes[rank] | (rank << 8) | (1 << (suit + 11)) | (1 << (16 + rank)); } switch (numevalcards) { // run Cactus Keys routines case 5 : holdrank = eval_5cards(workcards[0],workcards[1],workcards[2],workcards[3],workcards[4]); break; // if 6 cards I would like to find HandRank for them // Cactus Key is 1 = highest - 7362 lowest I need to get the min for the permutations case 6 : holdrank = eval_5cards(workcards[0],workcards[1],workcards[2],workcards[3],workcards[4]); holdrank = __min(holdrank, eval_5cards(workcards[0],workcards[1],workcards[2],workcards[3],workcards[5])); holdrank = __min(holdrank, eval_5cards(workcards[0],workcards[1],workcards[2],workcards[4],workcards[5])); holdrank = __min(holdrank, eval_5cards(workcards[0],workcards[1],workcards[3],workcards[4],workcards[5])); holdrank = __min(holdrank, eval_5cards(workcards[0],workcards[2],workcards[3],workcards[4],workcards[5])); holdrank = __min(holdrank, eval_5cards(workcards[1],workcards[2],workcards[3],workcards[4],workcards[5])); break; case 7 : holdrank = eval_7hand(workcards); break; default : // problem!! shouldn't hit this... printf(" Problem with numcards = %d!!\n", numcards); break; } // I would like to change the format of Catus Kev's ret value to: // hhhhrrrrrrrrrrrr hhhh = 1 high card -> 9 straight flush // r..r = rank within the above 1 to max of 2861 handrank = 7463 - holdrank; // now the worst hand = 1 if (handrank < 1278) handrank = handrank - 0 + 4096 * 1; // 1277 high card else if (handrank < 4138) handrank = handrank - 1277 + 4096 * 2; // 2860 one pair else if (handrank < 4996) handrank = handrank - 4137 + 4096 * 3; // 858 two pair else if (handrank < 5854) handrank = handrank - 4995 + 4096 * 4; // 858 three-kind else if (handrank < 5864) handrank = handrank - 5853 + 4096 * 5; // 10 straights else if (handrank < 7141) handrank = handrank - 5863 + 4096 * 6; // 1277 flushes else if (handrank < 7297) handrank = handrank - 7140 + 4096 * 7; // 156 full house else if (handrank < 7453) handrank = handrank - 7296 + 4096 * 8; // 156 four-kind else handrank = handrank - 7452 + 4096 * 9; // 10 straight-flushes } return handrank; // now a handrank that I like } int _tmain(int argc, _TCHAR* argv[]) { int count = 0; int card; __int64 ID; int IDslot; clock_t timer = clock(); // remember when I started int handTypeSum[10]; memset(handTypeSum, 0, sizeof(handTypeSum)); // init memset(IDs, 0, sizeof(IDs)); memset(HR, 0, sizeof(HR)); // step through the ID array - always shifting the current ID and adding 52 cards to the end of the array. // when I am at 7 cards put the Hand Rank in!! // stepping through the ID array is perfect!! int IDnum; int holdid; printf("\nGetting Card IDs!\n"); // as this loops through and find new combinations it adds them to the end // I need this list to be stable when I set the handranks (next set) (I do the insertion sort on new IDs these) // so I had to get the IDs first and then set the handranks for (IDnum = 0; IDs[IDnum] || IDnum == 0; IDnum++) { // start at 1 so I have a zero catching entry (just in case) for (card = 1; card < 53; card++) { // the ids above contain cards upto the current card. Now add a new card ID = MakeID(IDs[IDnum], card); // get the new ID for it if (numcards < 7) holdid = SaveID(ID); // and save it in the list if I am not on the 7th card } printf("\rID - %d", IDnum); // just to show the progress -- this will count up to 612976 } printf("\nSetting HandRanks!\n"); // this is as above, but will not be adding anything to the ID list, so it is stable for (IDnum = 0; IDs[IDnum] || IDnum == 0; IDnum++) { // start at 1 so I have a zero catching entry (just in case) for (card = 1; card < 53; card++) { ID = MakeID(IDs[IDnum], card); if (numcards < 7) IDslot = SaveID(ID) * 53 + 53; // when in the index mode (< 7 cards) get the id to save else IDslot = DoEval(ID); // if I am at the 7th card, get the HandRank to save maxHR = IDnum * 53 + card + 53; // find where to put it HR[maxHR] = IDslot; // and save the pointer to the next card or the handrank } if (numcards == 6 || numcards == 7) { // an extra, If you want to know what the handrank when there is 5 or 6 cards // you can just do HR[u3] or HR[u4] from below code for Handrank of the 5 or 6 card hand HR[IDnum * 53 + 53] = DoEval(IDs[IDnum]); // this puts the above handrank into the array } printf("\rID - %d", IDnum); // just to show the progress -- this will count up to 612976 same as above! } printf("\nNumber IDs = %d\nmaxHR = %d\n", numIDs, maxHR); // for warm fuzzys timer = clock() - timer; // end the timer printf("Training seconds = %.2f\n", (float)timer/CLOCKS_PER_SEC); // display training time LARGE_INTEGER timings, endtimings; // for high precision timing timer = clock(); // now get current time for Testing! // another algorithm right off the thread int c0, c1, c2, c3, c4, c5, c6; int u0, u1, u2, u3, u4, u5; QueryPerformanceCounter(&timings); // start High Precision clock for (c0 = 1; c0 < 53; c0++) { u0 = HR[53+c0]; for (c1 = c0+1; c1 < 53; c1++) { u1 = HR[u0+c1]; for (c2 = c1+1; c2 < 53; c2++) { u2 = HR[u1+c2]; for (c3 = c2+1; c3 < 53; c3++) { u3 = HR[u2+c3]; for (c4 = c3+1; c4 < 53; c4++) { u4 = HR[u3+c4]; for (c5 = c4+1; c5 < 53; c5++) { u5 = HR[u4+c5]; for (c6 = c5+1; c6 < 53; c6++) { handTypeSum[HR[u5+c6] >> 12]++; count++; } } } } } } } QueryPerformanceCounter(&endtimings); // end the high precision clock timer = clock() - timer; // get the time in this for (int i = 0; i <= 9; i++) // display the results printf("\n%16s = %d", HandRanks[i], handTypeSum[i]); printf("\nTotal Hands = %d\n", count); __int64 clocksused = (__int64)endtimings.QuadPart - (__int64) timings.QuadPart; // calc clocks used from the High Precision clock // and display the clock results printf("\nValidation seconds = %.4lf\nTotal HighPrecision Clocks = %I64d\nHighPrecision clocks per lookup = %lf\n", (double)timer/CLOCKS_PER_SEC, clocksused, (double) clocksused / 133784560.0) ; // output the array now that I have it!! FILE * fout = fopen("HandRanks.dat", "wb"); if (!fout) { printf("Problem creating the Output File!\n"); return 1; } fwrite(HR, sizeof(HR), 1, fout); // big write, but quick fclose(fout); return 0; } ///////////////////////////////// end code!! </pre><hr /> Wow!! I don't give any promises, but I verified it to the best of my ability over the last few days... As I said earlier, with the setups mentioned above, you will run the setup in about a minute, and poker hands (hand card order doesn't make any difference by the way!!) VERY quickly!! Any questions let me know... As I mentioned in the code, my stuff can all be GPL'd. pygmyhipo, you guys with the pokersource are absolutely incredible what you can do!! Whenever I had a general purpose evaluator to do, that is what I used! I know I should have used the pokersource for the evaluator for this, but perhaps you could rewrite the DoEval section to stub out the pokersource lib... This was a thread project, and it works GREAT!! Have a Profitable Day... Ray... |
|
#126
|
|||
|
|||
|
Just Thought I would put out the entire report for the code:
Getting Card IDs! ID - 612976 Setting HandRanks! ID - 612976 Number IDs = 612977 maxHR = 32487833 Training seconds = 57.71 BAD!! = 0 High Card = 23294460 Pair = 58627800 Two Pair = 31433400 Three of a Kind = 6461620 Straight = 6180020 Flush = 4047644 Full House = 3473184 Four of a Kind = 224848 Straight Flush = 41584 Total Hands = 133784560 Validation seconds = 0.5780 Total HighPrecision Clocks = 1141158660 HighPrecision clocks per lookup = 8.529823 Also some code to get you started using the file: <font class="small">Code:</font><hr /><pre> // TestHandRank.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "windows.h" #include <stdlib.h> #include <string.h> #include <time.h> const char HandRanks[][16] = {"BAD!!","High Card","Pair","Two Pair","Three of a Kind","Straight","Flush","Full House","Four of a Kind","Straight Flush"}; int HR[32487834]; // hold the handranks LARGE_INTEGER timings, endtimings; // for good timing int _tmain(int argc, _TCHAR* argv[]) { int count = 0; int handTypeSum[10]; int c0, c1, c2, c3, c4, c5, c6; int u0, u1, u2, u3, u4, u5; memset(handTypeSum, 0, sizeof(handTypeSum)); // do init.. memset(HR, 0, sizeof(HR)); FILE * fin = fopen("..\\HandRanks.dat", "rb"); // get the hand array saved by HandRankSetup if (!fin) { // problem say so printf("Problem Opening Input File!\n"); return 1; } size_t bytesread = fread(HR, sizeof(HR), 1, fin); // get the HandRank Array fclose(fin); // close up clock_t timer = clock(); // start regular clock QueryPerformanceCounter(&timings); // start High Precision clock for (c0 = 1; c0 < 53; c0++) { // run the test u0 = HR[53+c0]; for (c1 = c0+1; c1 < 53; c1++) { u1 = HR[u0+c1]; for (c2 = c1+1; c2 < 53; c2++) { u2 = HR[u1+c2]; for (c3 = c2+1; c3 < 53; c3++) { u3 = HR[u2+c3]; for (c4 = c3+1; c4 < 53; c4++) { u4 = HR[u3+c4]; for (c5 = c4+1; c5 < 53; c5++) { u5 = HR[u4+c5]; for (c6 = c5+1; c6 < 53; c6++) { handTypeSum[HR[u5+c6] >> 12]++; count++; } } } } } } } QueryPerformanceCounter(&endtimings); // end the high precision clock timer = clock() - timer; // end the regular clock for (int i = 0; i <= 9; i++) // display results printf("\n%16s = %d", HandRanks[i], handTypeSum[i]); printf("\nTotal Hands = %d\n", count); __int64 clocksused = (__int64)endtimings.QuadPart - (__int64) timings.QuadPart; // calc clocks used from the High Precision clock // and display the clock results printf("\nValidation seconds = %.4lf\nTotal HighPrecision Clocks = %I64d\nHighPrecision clocks per lookup = %lf\n", (double)timer/CLOCKS_PER_SEC, clocksused, (double) clocksused / 133784560.0) ; return 0; } </pre><hr /> Which returns: BAD!! = 0 High Card = 23294460 Pair = 58627800 Two Pair = 31433400 Three of a Kind = 6461620 Straight = 6180020 Flush = 4047644 Full House = 3473184 Four of a Kind = 224848 Straight Flush = 41584 Total Hands = 133784560 Validation seconds = 0.5620 Total HighPrecision Clocks = 1127908727 HighPrecision clocks per lookup = 8.430784 Not Bad [img]/images/graemlins/smirk.gif[/img] Have a Profitable Day! Ray... |
|
#127
|
|||
|
|||
|
This is soooo sweet! [img]/images/graemlins/cool.gif[/img]
I just gave it a quick test and it's running at 233 million evals per second on my machine (~12.7 clocks per lookup). That totally blows away the old 21 million evals per second I was getting with pokersource... Time to convert my old code to use unpacked hands me thinks!!! I'm assuming the only benefit to using the perfect hash version faster lookup creation? (I just used Cactus Kev's source). Thanks - Juk [img]/images/graemlins/smile.gif[/img] PS: One other (unrelated) small thing I just worked out was how to get the code from within code-tags without losing all of the indentation: just hit "quote" and copy the text from within the edit box... |
|
#128
|
|||
|
|||
|
[ QUOTE ]
I'd like to show my code, but firstly this is partly for my dissertation so I think my university owns part of it, and secondly, 40 clock cycles and a 250mb lookup is a lot worse than what some other people here have! [/ QUOTE ] Hey think of it this way: if you hadn't of made the original post, then this thread would never have started, so we have alot to thank you for! Juk [img]/images/graemlins/smile.gif[/img] |
|
#129
|
|||
|
|||
|
Hi Juk!
[ QUOTE ] I'm assuming the only benefit to using the perfect hash version faster lookup creation? (I just used Cactus Kev's source). [/ QUOTE ] Yes, the only reason I suggested Paul D. Senzee's Optimized Hand Evaluator was to keep the initial creation under a minute (and my debugging sanity [img]/images/graemlins/crazy.gif[/img])... You don't need it (you only run this once anyway). [ QUOTE ] PS: One other (unrelated) small thing I just worked out was how to get the code from within code-tags without losing all of the indentation: just hit "quote" and copy the text from within the edit box... [/ QUOTE ] Thank You for that Tip!! I was trying to figure out how to keep the formatting going on and coming out of this BBS. [img]/images/graemlins/blush.gif[/img] Sounds like you are Blazin' so I guess the instructions weren't toooo bad! Have a Profitable Day! Ray... |
|
#130
|
|||
|
|||
|
This is quite possibly the only time I've looked at someone else's code and knew what they were doing the whole way.
I like the additional vector [0] to give 5, and 6 card evaluations as well. My code peaked out at 12.5 cycles. Since our access method is the same, I've got to believe the difference is due to my 10 year old compiler. |
![]() |
|
|