A hand evaluator for 7-card poker games

A while ago I spent some time on researching Poker (more specifically, Texas Hold'em) since I figured that a Poker-bot would give a good example for adaptive software. I still believe so, but it became evident that such a software requires a lot of fine-tuning and that the adaptivity would be but a small feature rather than a solid basis to build upon. In the wake of this research, I came up with a hand evaluator for "best 5 out of 7" card poker games like Texas Hold'em. Since I feel that I will never find enough time to do more research in this topic, I will publish it here in the hope that someone will find it useful.

This page describes the algorithm, gives some observations, and also provides source-code in C and Java.

What is a hand evaluator doing?

It gets a little confusing if you do not keep in mind what a hand evaluator is all about: It assigns a ranking to a hand. For example, the hand

9C 7D QS KS JS AS TS

is given the highest ranking, as it is a royal flush; the hand

8S 9S QS KS JS AS TS

is given the same ranking, so if one player has the 9C &D hole cards and the other one has 8S 9S, it is a split pot. Other hands rank lower, with a "Nine-high" hand being the worst possible hand for Texas Hold'em. When it comes to a showdown, all 7-card hands (consisting of the two hole cards and 5 community cards) are ranked, and the one with the best ranking wins.

Hand evaluators can be used to simulate games, preferrably a lot of them, hence they need to be fast (on a modern PC, they should rank millions of hands in a second). Such simulations can be used for producing fancy graphics like this one:

(An explanation of what that is and more statistics can be found here).

The basic approach

Cactus Kev has published a very interesting hand evaluator for 5-card games, which assigns each 5-card-hand to an equivalence class which identifies the "worth" of the hand - see the webpage for a very good explanation. A purportedly faster approach uses perfect hashing. I did not want to come up with a perfect hashing for 7-card games (frankly, I would not have known how to do it), but followed a more direct approach that employs a directed acyclic graph (DAG). This idea is based on some observations:

the order of the cards does not matter,
colors only matter for flushes,
there can only be one flush color (i.e., if there is a flush of spades, there cannot be a flush of hearts in the same 7-card hand),
if there is a flush, there cannot be a better 5-card-combination that is independent of colors, i.e. no full house or four-of-a-kind.

Let us ignore the colors for a while. The idea of using a DAG is best illustrated for a simplified deck which consists only of the cards 1,2,3 (in the four colors) which is used for a game with 3-card hands. We can now build a DAG like this (only a small part is shown):

Calculating this DAG is done in a precaculation step, so we can take our time for figuring out which rank the nodes on the last layer are given (which is the difficult part.)

Now, ignoring the colors, we can evaluate a hand like 1,2,1 by following the arrows: We start at the node {1}, go to the node {1,2} and continue to node {1,1,2}, where we see that the hand is a pair of 1's with 2 as a kicker. (Basically, we use rule 1 here.) The same thing works for Texas Hold'em, where we need to distinguish 13 cards (ignoring colors again) and have 7 cards in a complete hand, which gives the DAG seven layers. For each node in the final layer, we then calculate the equivalence class (which I borrowed from Cactus Kev).

How to deal with colors? Well, there are two ways:

Either we count the colors when traversing the DAG, and check if one of them is present more than five times, in which case a flush is present (with a unique color, see rule 3): We then follow the DAG again, but this time only considering the flush colored cards, we then arrive at a node at level 5 to 7; since there cannot be a higher hand, this is the best equivalence class (see rule 4 - if you have a flush, then five of the seven cards are of the same color, therefore there can only be two pairs or one three-of-a-kind, which ranks below the flush - remember that it is all about a single player's hand!).
Or we walk the DAG with five "pointers" at once: one for each color, and one for the rank only; if one of the color pointers reaches level 5 or above, we have a flush, otherwise we take the ranking of the "color-less pointer".

Actually, I compared both approaches and found them to be almost equally fast, with a slight advantage for the two-stage approach.

Why not build a DAG for all 52 cards? Simple answer: It would be too big. The 13-card DAG has 76514 nodes (we do some pruning here, nodes with 5 cards of the same rank are not reachable by a real hand). The first three layers of a 52-card-DAG have already twice as much nodes, and the entire DAG would have 157,036,243 nodes; assuming 32bit pointers and an affinity to pointer arithmetics, we would need roughly 2.5GB memory to store it (requiring 52*4 bytes for the nodes on level 1-5, on level 6 we require 52*2 bytes to store the equivalence class index).

The DAG

Here it is (GZ'ipped for size). It is a tab-separated list whose columns have the following function:

Column	Name	Function	Values
1	Node ID	The ID of the node, which corresponds to the line number (-1)	0-76513
2-14	Next pointers	Pointers to the next node, from a "2" to an "A", so if we see a card with rank "J", we go to the node with the ID found in column 11.	0-76513, 0 indicating that seeing such a rank (again) is not possible.
15	Flush class	The ID of the equivalence class if this node was reached by cards of the same color	-1 (indicating that this is not a flush yet), 1 (Royal flush) - 1599 (Seven high flush)
16	Rank class	The ID of the equivalence class if no flush is present	-1 (no seven cards yet), 11 (Four Aces) - 7462 (Seven High)
17	Cards	A textual depiction of the cards in this equivalence class	Things like [J, 4, 2]
18	Worst normal hand	The equivalence class ID of the worst hand reachable with this cards	11-7462
19	Worst flush hand	The equivalence class ID of the worst hand reachable with this cards, if they are from the same color, and a flush in this color is achieved	-1 for flush-incompatible cards (featuring pairs), 1-1599
20	Best normal hand	The equivalence class ID of the best hand reachable with this cards (excluding flushes)	11-7462
21	Best flush hand	The equivalence class ID of the best flush hand reachable with this cards	-1 for flush-incompatible cards, 1-1599

Of course, only column 2-16 are really required. Cactus Kev's list of equivalence classes can be found here. For seven-card games, many of the classes are unreachable (like a "7 high"), but I neverless retained them.

Sources

The DAG was calculated using a Java program, and the hand evaluator itself was written in C. I also provide a JNI wrapper so that it can be used under Java. I also reimplemented the evaluation algorithm in Java, because I was interested in how much speed is lost (you know, some people claim that Java is actually faster than native code, see below).

Everything is found in this archive. It includes Cactus Kev's equivalence class list with his generous permission. The source-code is released under a BSD-style license.

You need to edit configure.local in order to run make (it contains the location of the JDK, which is required for javah and the JNI header files). Java sources need to be compiled by hand or in an IDE.

The code is pretty much undocumented, but should be easy to understand. The Java sources in src/handevaluator/generator are used for generating the DAG, the other sources are for testing it. The C sources may use the "SIMD-oriented Fast Mersenne Twister", which can be obtained here. (I named the object file SFMT.eo, so a make clean does not delete it.) Use it as you see fit, or edit randomgenerator.h so that the standard rand() function will be used.

Misc stuff

Writing this hand evaluator was pretty interesting. Some points are:

Most of the time, you will not evaluate entirely random hands, but hands with a set of cards fixed (e.g., you have the flop cards and wish to simulate the outcome of all games for the remaining two cards, plus random cards assigned to your opponents). It seems pretty feasible then to pre-evaluate the DAG, and keep a pointer to the node(s) which are already reached by the fixed cards. This should cut the evaluation time for the other cuts - but it doesn't. At least not with my implementation. One of the reasons is that much time is consumed by the management of the deck and the generation of random numbers (remember, we talk about millions of hands per second!). But why I totally failed to produce a speedup, I cannot understand.
Representing decks: When simulating a lot of games, you want an efficient deck representation (i.e. a data structure that keeps track on which cards have already been dealt). It is very tempting to use a 52-bit array here, but then, for dealing a random card, you would have to calculate random values until you found a card that has not been dealt yet. I use a different representation: an array of 52 byte values, which invariantly contains the numbers 0 to 51. Also, I maintain a "undealt card counter" c that is initialized with 51. For drawing a random card, I select a random value in the range [0 .. c]. The entry at this position is the value of the drawn card. I then swap this entry's value with the value of the entry c and decrease c. For resetting the deck, I just need to set c to 51 again.
Given a value v between 0 and 51, I calculate the rank and the color of the card like this:
- color = v & 3
- rank = v >> 2
I.e., the lowest two bits are used for the color and the upper bits for the rank.
Generally, I know little about optimization beyond the algorithmic stuff. It would be very nice to have someone with a proper background in optimization check the algorithm to see if things like the cache usage can be improved. If you find such things entertaining, please let me know!

Given that this algorithm is fairly easy and is used from both Java and C programs, I decided to write it both in Java and C and compare the runtime. Here are some measurements:

Experiment	Trials	Time in ms
Java Overhead	3M	4353
Java One-Pass	3M	7235
Java Two-Pass	3M	7071
JNI	3M	6736
C Overhead	3M	1470
C Two-Pass	3M	2435
Java Overhead	15M	21795
Java One-Pass	15M	36106
Java Two-Pass	15M	34686
JNI	15M	33779
C Overhead	15M	5931
C Two-Pass	15M	11896

Basically, n hands are generated and their equivalence class is determined. The "overhead" experiments omit the equivalence class determination; the time they consume is spent on "shuffling" the deck. JNI tests use a JNI call for evaluating a hand; of course, nobody would do it this way but rather also calculate the decks in the native source. All times exclude the initialization phase, where the DAG and the equivalence class list are read.

I do not claim accuracy for this times - I did not run multiple tests etc. However, it is evident that pure Java is comparable to Java with JNI calls, both evaluating approx. 1M hands per second (excluding shuffling times).
The C-only version is three times as fast, both in shuffling the deck (using the Mersenne twister, which is faster than the standard rand() function) and ranking them. On my almost vintage P4 3Ghz I obtain approx. 3M ranked hands and 1.3M simulated hands per second. The speedup over Java is smaller than I experienced before (I once got a 150x speed-up for a model checker, but then the C version also incorporated a lot of algorithmic improvements over the Java version), but nevertheless expected. I think that neither the Java nor the C version of the algorithm are really maxed out with respect to optimization, though. Note that the algorithm does not involve allocation/deallocation of memory (after initialization).

If you use this evaluator, I'd be happy to hear about it! If you want to write a Poker-Bot, I'd also be happy to share some ideas.

Moritz Hammer, 26.1.2008