The computer science department of the University of Alberta in Edmonton researches Artificial Intelligence (AI) for Poker. From their site I came upon Cactus Kev's Poker Hand Evaluator which is a killer fast five card hand evaluator. Reading through his algorithm you'll notice that the last step for any yet unclassified hand is a binary search through a list of values. Most hands end up in that search which is the most time-consuming part of the algorithm.
An Optimization
Replacing the binary search with a precomputed perfect hash for the 4888 values in the list yields a significant improvement over the original. The original test code included with Kevin's source (using eval_5hand) runs in 172 milliseconds on my machine and with my eval_5hand_fast it runs in 63 milliseconds. Yay, an improvement of 2.7 times!
fast_eval.c
(Updated 7/10/07)
This post has garnered a bit of attention. Cactus Kev added a comment and a link on his site back to the post and I've had an email conversation with a programmer (anonymous unless he's cool if I mention him) who ported the code to C# and reports:
Kev: 159ms
Your mod: 66ms
My C# version of your mod: 88ms
Pointers for seven hand evaluation? Check out the post 7.
34 comments:
Thanks for sharing!
:)
That's some sweet code, Paul. Poker math geeks unite!!!
--Cactus Kev
have you also written any 7card evaluation routines? i am collecting input on how that could be done with some performance :-)
regards
camel@insecure.at
Actually, I've got a seven card evaluator that's quite fast, but it requires some enormous tables and some pretty hairy code. I'm looking into a better way to do it. The key idea though, is to quickly detect if you've got a flush or not first because if you don't (most of the time), you can use a really large hash table.
I ported Cactus Kev's to Java and I just timed it inside my IDE. 272 milliseconds! I was surprised that it was that fast.
I'm running on AMD 3800+.
There are more than 49,000 unique rank patterns for 7 cards. The max product of their prime numbers is 143,133,271,933 (64-bit integer). How to find a perfect hash to map long integers into 16-bit short integers?
Am I getting something wrong here I thought a perfect hash could take arbitrary indexes. The problem for perfect hashing being the size of the tables required...perfect hash generators are very slow for large tables? But many small tables say 7 flush table 6 flush table etc downwards should present less of a problem.
I have got a Java 7-card evaluator. It enumerates 133M all possible 7-card combinations in 11 sec, 1.7M 2-hand heads-up combinations in 280 msec. How fast is yours?
Can someone post the Java coding somewhere too?
Thanks.
Has anyone wondered why Cactus Kev said that there's 1277 distinct values for Flushes? Isn't an Ace-High Flush equivalent to any other Ace-High Flush regardless of what the other cards are? I was always under the impresion that only the top card is looked at when comparing flushes so if that is correct then there would only be a total of 10 distinct values instead of 1277.
To evaluate a flush's rank you look at the rank of all five cards, just like in a High Card hand. So there are 13 choose 5 (which is actually 1287) different ranks of flushes.
Whoops, that 1287 includes the 10 straight flushes. So it's just 1277 flushes.
Jing said...
There are more than 49,000 unique rank patterns for 7 cards. The max product of their prime numbers is 143,133,271,933 (64-bit integer). How to find a perfect hash to map long integers into 16-bit short integers?
That's only if you need to differentiate hands that include pairs. If you look at the straight table (indexed by the OR of the rank bit from each card) and--why not--expand that table to its full size of 8192=2^13 slots, you can store values for the straights as well as evaluations of each pairless hand. The table should also contain the bit-count function, so you can test whether you have as many bits as cards--if not, you look for what rank has pairs or better.
--Dan Hoey (haoyuep(at)aol.com)
The best Java 7-card evaluator can enumerate 133M hands in ~ 1 sec.
I posted a bit about 7-card hand evaluation. There's more to come soon when I get some code cleaned up to post.
I have written C# code that determines the winner of a two-player Texas Hold'em game. Each player has 2 pocket cards, and there are of course 5 table cards. For each player, there are 21 possible outcomes (5 cards out of 7 cards). My code can determine the best hand for each player based on their seven cards, and then determine who won. It can do all of this in 0.000008 seconds per game. This seems to be way faster than anything out there. It uses a completely different approach to all the others that I have been reading about. If you are interested to know more for commercial purposes, please email me m.harwar@googlemail.com
BTW --- I can get it to go way faster. I just thought of an approach as I was writing the previous post. Let me know if you are interested
And while I am thinking of this, the same approach can work for three-handed games, four-handed games, and so on, up to 10-handed games. Just thought it might be worth a mention if any of you are building stochastic simulations (AKA Monte-Carlo sims).
I have a 5 card evaluator that uses from 12% to 56% less CPU cycles (depending on CPU type) than the perfect hash with no lookup tables. Object code is less than one tenth the size. Not sure how ell the concept will scale up to 7 cards
Any way you could tell me what program you used to generate the perfect hash function? I've created a list of 64 bit integers that I'd like to have perfectly hashed, and I want to know the best way to go about doing this.
I have a free energy device in my garage, and a poker hand evaluator that runs in 0.000000000000000001minutes. But I don't want to leave any contact info or source code. I just wanted you all to know.
BTW Martin, saying your code runs in X seconds is silly for 2 reasons: 1) Why use seconds? If you used hours you could add a bunch more leading 0's. See above example. 2) Compared to what?! Are you running on a 386 or a multicore machine? I must admit I'm suspicious of your fully scalable super-fast algorithm.
I ran eval_5hand_fast with a
eval_5cards
and I'm getting different results ,
any idea what can be a reason ?
hey guys...i am a perl script developer from india...thanks a lot for sharing...some really nice ideas here...
Hi Paul, Thanks a lot for this (realize this is an old post). I implemented this algorithm in PHP5 and it works very well. I had to add a 32 mask to the final "u" calculation to keep the indexes from getting out of bounds since PHP5 does not have any unsigned types.
I do have one question, which you may or may not know the answer. Why is the equivalence class 166 (Hand: 22223) repeated 3304 times in the hash table. None of the other 4887 values are repeated. Are all of those 166's except one, just equivalent to 0?
Regards
Thanks Paul for the great code. I want to rewrite it to PHP language.
I know, that's silly question, but what is the efficient way to make 2-card evaluation?
Currently I use dictionary with 1326 elements to map initial hand to one of 169 equivalent classes. Is there a more efficient way to do this?
I only recently entered the word of optimized code and this hash stuff still looks like magic to me.
This got me inspired though, i never saw bitwise operators used this way !
Can you explain the find_fast function please? Thanks
Hi Daniel,
Are your php scripts available for download anywhere, by any chance?
P
Your c file says copyright you, but what is the licensing on the use of the code/algorithm?
Daniel Shaw is correct - this perfect hash algorithm has an error in it. He pointed out that the value 166 (Hand: 22223) has too many entries AND 7462 isn't on the list, neither is 7461, 7460 and many more.
Super information for your blog, thank you for taking the time to share with us. fantastic perception you have on this, it's exceptional to discover a internet site that information so much information approximately extraordinary artists. Gmod game
Just want to tell what nonsense one can do with your code.
Thanks to Cactus Kev and Paul, I developed an Omaha Evaluator. As I tried to evaluate every Omaha starting hand against any other, I faced an incredible explosion of combinatorics. So I speeded up the algorithm to another level, using lots of precalculation tables and more. Than I ran that stuff on multiple processors. On our most recent 16-Core-engine, I had to expect a runtime of approx. 18 Month. So I used assembler, had a look on processors prefetch queues, optimized some tables to fit into processors L1-Cache, added some network communication ability to achieve a distributed system and finally, on christmas leave, I occupied all available multicore engines in the office. (Only found 8 out there)
Surprisingly, I found out AAKK is NOT the best starting hand. Its AATT. (I can explain that)
That took some weeks of my life but I had lots of fun with it.
Today, I work on an evaluator for the new funny variant "6up", available on Pokerstars. Hopefully will have those fun again.
Post a Comment