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

9C 7D QS KS JS AS TSis given the highest ranking, as it is a royal flush; the hand

8S 9S QS KS JS AS TSis 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 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.

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".

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).

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 |

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.

- 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*

- 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 *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