Update: This grew beyond an easy project, and I have written a own page about the issue. In a nutshell, the algorithm proposed below is a) a bit flawed (a fix would be easy, though) and b) not as fast as I had hoped. Which is, in turn, because my old algorithm was not that bad – and I spend most of my time improving it, getting quite competitive results.
It’s been a while since I posted something, and the thing I can post now is from a complete different area than the rest… it is about a Poker Hand Evaluator! I have written one during my PhD time (here it is) which got me a little fame.
This dag-based poker hand evaluator is nice, but it has one design flaw that makes it slower than the competition: for each card it visits, a lookup in a memory table is done. Since that table is big, it is bound to fail second-level caches, and that is where the time is spend. So one day, for a reason I no longer know, I came up with a new idea, which is less beautiful, but can do a hand comparison with just one table lookup. And since I will be programming a lot C++ in the near future, I thought it would make a good exercise to try it out.
So what is a hand evaluator? Basically, an algorithm that, given two poker hands (in our case, we only consider Texas Hold’em, best 5 out of 7 cards) will tell you which one is better. For determining the winner of a round, a very basic algorithm will do (e.g., using a series of “detector” algorithms that look for straight flushes, then four-of-a-kind, etc.). It gets more interesting when, given partial hands (i.e., some known cards with others yet to come), we want to know the likelihood that one hand wins. Like on TV, when they show you the cards the players have, and how likely it is that one hand will win. There is no clever formula – it is done by comparing all possible hands, or doing Monte-Carlo-testing (if there are too many). Hence, a hand evaluator needs to compare a lot of hands in very little time. Think of millions of hands per seconds – that only leaves something in the region of thousand cycles on a modern CPU. Sorting the cards, repeated scans, all that is too slow. The goal is to go through the cards once (maybe twice), and then have the result.
An important observation was done by Cactus Kev (or rather, put in writing so I could build on that) – many distinct hands actually have the same value. Order does not matter, nor the color of cards (unless it is a Flush, in which case the exact color is not important). He wrote a hand evaluator based on that, but for 5-card Poker variants. Here, we do seven cards, which just puts more hands into each equivalence class (e.g., for the Royal flush, the color does not matter, nor do the two cards not being part of the Ace-high straight). So what I did in my last evaluator, and do again, is to find a fast way to calculate the index of the Cactus Kev equivalence class . The lower the equivalence class number, the better the hand.
The approach I take is very straight-forward: let’s ignore the suit for now, so we have 13 cards, with each card being present 0 to 4 times in a hand. We can just create a bitfield that represents just that – how often each of the 13 cards is present – and look into a big, precalculated table to see which class it gives us. However, since we need to store 5 different values, we need 3 bits per card… so, in total, 549 billion entries in a lookup table. Too big. But why consider the case where we have 4 cards at all? That should be very infrequent, so we can detect it and revert to some special routine… and just use two bits per rank, which gives us just 67 million. But while developing it, I recognized that it works if we just ignore the four-of-a-kind case, and here is why:
Since we allocate two bits per rank, adding the fourth card will produce an overflow. It will hence appear as if we got no cards of that particular rank at all, and instead one more of the next-higher rank. Thus, instead of looking at 7 cards, we look at four – and this will produce a number that no other hand will produce (their cross-sum will always be 7). It could even overflow twice – e.g. with four kings, three aces – but then we just get one card. We can even clip that overflow, and get 0 cards for that particular case – the important thing is that it will not collide with another hand, and that it will be the same during creation and use of the lookup table. So we can just use two bits per rank, and ignore overflows (other than clipping the 26-bit field in the end).
0 Comments.