April 23, 2010
I occasionally play poker (Texus Hold-em mainly) Being a software developer I naturally want to simulate the game using a computer. This inevitably leads to needing to code up an algorithm for ranking poker hands and comparing them. It also leads into interesting topics like random number generation. If you haven't tried writing a hand ranking algorithm in C++ before I'd suggest giving it a try, as there are several approaches to the problem. Why use C++? Mainly because a lot of places still use C++ and this provides a small enough example to demonstrate some of the good and some of the bad parts of the C++ language.
For an overview of poker see http://en.wikipedia.org/wiki/Poker. This article is only concerned with ranking a standard five card hand using a standard four suit, thirteen rank, 52 card deck (no jokers, wild cards, etc.).
The rankings of the hands go: high-card (HC), one-pair (1P), two-pair (2P), three-of-a-kind [aka trips] (3K), straight (ST), flush (FL), full-house [aka full boat] (FH), four-of-a-kind [aka quads] (4K), straight-flush (SF), and royal-flush (RF). Straights include A-2-3-4-5, and royal-flush is just a fancy name for the highest possible straight-flush
To rank of hand of five unique cards from the standard 52 card deck we first sort the cards in order by rank. We then compute three things: are they in sequence (remember to account for A-2-3-4-5 or t-j-q-k-a), are they all the same suit, and a match pattern. The match pattern is computed by comparing each card to its neighbor, yielding a four-bit value. For example 2-2-3-7-7 would yield a match pattern of 1001 (2 matches 2, 2 doesn't match 3, 3 doesn't match 7, and 7 matches 7) in binary which translates to 9 in decimal.
A this point if it is both a straight and a flush you check the highest card and if it is a ace you return RF, otherwise return SF.
If it is just a straight return ST, and if it is just a flush return FL.
So far no reordering of cards has been needed, since all five cards where involved in determining the result. For the next steps some of the match patterns will require reordering the cards to move the groups past the non-grouped cards so when we compare hands of equal rank they compare correctly. (e.g. 2-2-q-k-a is reordered to q-k-a-2-2 so that when compared with other 1P hands the 2's are considered high.)
We now look at the sixteen possible match patterns:
At the point the cards will be ordered from lowest to highest with larger groups following smaller groups so hands can be compared by rank first, and then in reverse order (from highest to lowest) to determine which hand is better.
I've attached a Visual Studio project that contains the C++ code. The code is broken up into a few pieces. The uitl.h contains a simple random number generator that will ensure the results are the same regardless (mostly) of the platform the code is compiled on. The card.h/.cpp files contain an class for representing a simple int as a card. I use shifts and masks instead of bit fields since some compilers have trouble with bit fields. The hand.h/.cpp files contain a class for analyzing an ranking a hand.
I use std::random_shuffle and std::sort. In a production environment I'd likely replace these with something else or at least move to pointer based collections rather than shuffling/sorts the larger data in place. Sorting a hand of five cards can likely be done faster with a fixed length sorting approach than using the more generic sort as well.
There are also test.h/.cpp files that cover off some basic testing of the code provided. Passing any argument to the program will cause it to run those tests.
Some of you might be wondering about the while loop in the random number generator for producing random numbers in the range [0,n). If you want to generate a uniform distribution from 0 to 9 inclusive using a binary generator you need the while loop. Doing random(0..15)*10/16 will overweight certain numbers as the sixteen possible returns are mapped onto ten possible return values, causes six of the values to be twice as likely as the other four. By rejecting the extra six results and retrying until one of the results is in the range of 0 to 9 we ensure that each result is equally likely. Since we only consider enough bits to represent the range our worst case is a 50% (minus epsilon) rejection rate so while the loop can in theory execute forever in practive it tends to exit quite quickly.
This is just one method of determining hand rankings, and I'm sure their are more methods available and lots of room for optimizations to speed up the hand ranking process. Extending this to handle cases with jokers, wild cards, and best five card hand from seven cards (efficiently) would be the obvious next steps to take.