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:
  1. the order of the cards does not matter,
  2. colors only matter for flushes,
  3. 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),
  4. 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:

  1. 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!).
  2. 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:
ColumnNameFunctionValues
1Node IDThe ID of the node, which corresponds to the line number (-1)0-76513
2-14Next pointersPointers 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.
15Flush classThe 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)
16Rank classThe ID of the equivalence class if no flush is present-1 (no seven cards yet), 11 (Four Aces) - 7462 (Seven High)
17CardsA textual depiction of the cards in this equivalence classThings like [J, 4, 2]
18Worst normal handThe equivalence class ID of the worst hand reachable with this cards11-7462
19Worst flush handThe 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
20Best normal handThe equivalence class ID of the best hand reachable with this cards (excluding flushes)11-7462
21Best flush handThe 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:
Moritz Hammer, 26.1.2008