Poker Hand Evaluation evaluation

Question

Several days ago, a question on this topic was posted to SO. The problem turned out to be the OP's test cases did not reveal a deficiency in the code. This challenge caught my attention. Writing the following has provided entertainment for a number of rainy hours.

I've had a look at several "Review" postings (looking for C language solutions). I believe this code embodies a representation of the data (card values and tallies) that improves upon those I've seen. (Without its verbose commentary, assess() is almost trivial.) My focus has been on the code, with little interest in the game of poker. Thank you for your time.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum {
    highCard, onePair, twoPair, threeOfKind, straight,
    flush, fullhouse, fourOfKind, str8Fl, royalFl,
    nTallies,
    nCard = 7, // # of cards in one hand
    aFlush = 5, // # of cards in a flush, royal or otherwise
    oneSuit = 0x10, // # "suits" contain cards represented by 0 to 0xC of 0 to 0xF (4 bits)
    b43210 = 0x1F // bits 4 to bit 0 (five contiguous set bits)
};

char *name[] = { // for outout
    "0 High Card", "1 One Pair", "2 Two Pair", "3 Three of a kind", "4 Straight",
    "5 Flush", "6 Full House", "7 Four of a kind", "8 Straight Flush", "9 Royal Flush",
};

int isSTR8( uint64_t x ) { // determine if low order 13 bits contain a "straight"
    for( x &= 0x1FFF; x >= b43210; x >>= 1 ) // return as soon as search becomes futile
        if( (x & b43210) == b43210 ) return 1;
    return 0;
}

int assess( int h[] ) { // assess the hand into one of the ten categories
    uint64_t bits = 0, str8 = 0, popS = 0, popV = 0, big1 = 1;

    // convert 7 unique card values into one 64 bit field
    // 'bits' assembled as 4x16 bit fields, one for each suit
    //      used bits: b60-b48, b44-b32, b28-b16, b12-b0 ==> single bit in 1 of 4 "suits"
    //      'bits' will eventually have only 7 set bits representing the 7 cards' suits & values
    // 'popS' accumulates counts of each suit present in the hand
    //      max possible cnt for any one suit is all seven cards in same suit. ie: 7
    //      popS uses each 4x4 bit field to sum values in range of 0 to 7 (3 bits)
    // 'popV' accumulates counts of each value present in the hand
    //      max possible cnt for any one value is 4 (eg: 4 Jacks)
    //      popV uses each 13x4 bit field to sum values in range of 0 to 4 (3 bits)
    for( size_t i = 0; i < nCard; i++ ) {
        bits |= big1 << h[ i ]; // as single set bit
        popS += big1 << (4*(h[ i ] >> 4)); // cnt 'n' in each suit
        popV += big1 << (4*(h[ i ] & 0xF)); // cnt 'n' of this face value
    }

    // destroy 'bits' (right shift)
    //      if a 'flush' is found, determine "royal", "straight" or "ordinary"
    //      otherwise, accumulate bits to determine a (mixed) straight soon
    for( ; bits; bits >>= oneSuit, popS >>= 4 ) { // finish search asap!
        if( (popS & 0xF) >= aFlush )
            return (bits & 0x1E01) == 0x1E01 ? royalFl : isSTR8( bits ) ? str8Fl : flush;
        str8 |= bits;
    }

    if( isSTR8( str8 ) ) return straight; // should be obvious

    // determine highest and 2nd highest tallies of card face values
    int hi1 = 0, hi2 = 0;
    for( ; popV; popV >>= 4 ) { // finish search asap!
        int pop = (int)(popV & 0xF);
        if( hi1 < pop ) { hi2 = hi1; hi1 = pop; }
        else if( hi2 < pop ) hi2 = pop;
    }

    switch( hi1 ) { // dispatch...
        case 4: return fourOfKind;
        case 3: return hi2 >= 2 ? fullhouse : threeOfKind;
        case 2: return hi2 == 2 ? twoPair : onePair;
        default: return highCard;
    }
}

int *show( int *h ) { // called by test()
    for( int i = 0; i < nCard; i++ )
        printf( "%c%c ", "hcds"[h[i]/oneSuit], "A23456789XJQK"[h[i]%oneSuit] );
    return h;
}

void test( void ) {
    // 4 suits of 13 cards each ('X' == 10).
    // Note range for each suit changes with each Ace
    enum {
        hA = 0x00, h2, h3, h4, h5, h6, h7, h8, h9, hX, hJ, hQ, hK, // hearts
        cA = 0x10, c2, c3, c4, c5, c6, c7, c8, c9, cX, cJ, cQ, cK, // clubs
        dA = 0x20, d2, d3, d4, d5, d6, d7, d8, d9, dX, dJ, dQ, dK, // diamonds
        sA = 0x30, s2, s3, s4, s5, s6, s7, s8, s9, sX, sJ, sQ, sK  // spades
    };
    // 10 composed samples to test assess(). Left-to-right order is not special
    int i, hands[][ nCard ] = {
        { h4, cJ, d9, d5, s3, h7, sA }, // high card
        { h4, c3, d9, d5, s3, h7, sA }, // one pair
        { h9, c3, d9, d5, s3, h7, sA }, // two pair
        { h9, c3, d9, d5, s9, h7, sA }, // three of a kind
        { d5, c6, sA, h8, s5, c7, d4 }, // straight
        { d5, dJ, dX, dQ, s5, c7, d6 }, // flush
        { d8, h8, s8, hQ, c7, sK, s7 }, // full house
        { h9, c9, d9, d5, s9, h7, sA }, // four of a kind
        { s5, s7, s6, s8, d5, c7, s4 }, // straight flush
        { dA, dJ, dX, dQ, s5, c7, dK }, // royal flush
    };

    for( i = 0; i < sizeof hands/sizeof hands[0]; i++ )
        printf( "... %s\n", name[ assess( show( hands[ i ] ) ) ] );
}

int *deal( int *p ) { // called by run()
    // not interested in true randomness and fairness
    // sufficient to compose array of 7 unique values (cards) between 0 and 63
    // encoding values rejects values 13, 14, 15 in any suit
    for( int x, i = 0; i < nCard; ) {
        p[i] = rand() % 64;
        if( ( p[i] & 0xF ) <= 12 ) { // face is "Ace to King" (0 to 12)?
            for( x = 0; x < i && p[x] != p[i]; ) x++; // no duplicates!
            i += x == i;
        }
    }
    return p;
}

void run( int nLoop ) {
    srand( time( NULL ) );

    int i, cnt[ nTallies ] = { 0 }; // simple 'histogram' accumulator for 10 types
    int hand[ nCard ];

    for( i = 0; i < nLoop; i++ )
        ++cnt[ assess( deal( hand ) ) ]; // deal, assess, tabulate, repeat

    for( i = 0; i < nTallies; i++ )
        printf( "%.6f - %s\n", cnt[i]*1. / nLoop, name[ i ] ); // report
}

int main( void ) {
    // Activate one or other... or both.
    test();
    run( 10 * 1000 ); // # of trials
    return 0;
}

Results of one run with both test() and run() active:

h4 cJ d9 d5 s3 h7 sA ... 0 High Card
h4 c3 d9 d5 s3 h7 sA ... 1 One Pair
h9 c3 d9 d5 s3 h7 sA ... 2 Two Pair
h9 c3 d9 d5 s9 h7 sA ... 3 Three of a kind
d5 c6 sA h8 s5 c7 d4 ... 4 Straight
d5 dJ dX dQ s5 c7 d6 ... 5 Flush
d8 h8 s8 hQ c7 sK s7 ... 6 Full House
h9 c9 d9 d5 s9 h7 sA ... 7 Four of a kind
s5 s7 s6 s8 d5 c7 s4 ... 8 Straight Flush
dA dJ dX dQ s5 c7 dK ... 9 Royal Flush
0.165100 - 0 High Card
0.446500 - 1 One Pair
0.244800 - 2 Two Pair
0.048300 - 3 Three of a kind
0.042600 - 4 Straight
0.028600 - 5 Flush
0.023000 - 6 Full House
0.000800 - 7 Four of a kind
0.000200 - 8 Straight Flush
0.000100 - 9 Royal Flush

---

EDIT:
What's the mantra? "Always consider edge cases!"

Thanks to @TobySpeight for finding a deficiency in the code above. It fails to find a "royal straight" composed of Ace, King, Queen, Jack, 10 of diverse suits... Doh!

A quick fix would be to change:

    if( isSTR8( str8 ) ) return straight; // should be obvious

to

    if( ((str8 & 0x1E01) == 0x1E01) || isSTR8( str8 ) ) return straight;

testing for this non-contiguous but valid pattern.

Only 52! - 45! possibilities of hands to test this code... Now, a few less. Thanks again for Toby's sharp eyes.

Answer 1

In general, I believe it's a good idea to always use braced blocks for conditionals and loops, rather than bare statements. It makes code easier to modify in future and costs us nothing.

This definition looks good so far:

enum {
    highCard, onePair, twoPair, threeOfKind, straight,
    flush, fullhouse, fourOfKind, str8Fl, royalFl,

But then we have:

nTallies,
nCard = 7, // # of cards in one hand
aFlush = 5, // # of cards in a flush, royal or otherwise
oneSuit = 0x10, // # "suits" contain cards represented by 0 to 0xC of 0 to 0xF (4 bits)
b43210 = 0x1F // bits 4 to bit 0 (five contiguous set bits)

These look like totally unrelated things stuffed into the same enumeration. That's very strange and confusing - I think these things ought to be individual constants of appropriate types. At least some of them can be reduced in scope, too.

Good use of enums can be advantageous - for one thing, a decent compiler will warn when we have a switch that doesn't have cases for all the members.

I don't like the inconsistency in the names - we have camel-case for onePair, but all lower-case for fullhouse. And I find the cutesy str8Fl much harder to read than straightFlush.

char *name[] = { // for outout

Be aware that it's undefined behaviour to modify a string literal. Safer to declare as char const *name[]. And I guess outout is a type for output?

int isSTR8( uint64_t x ) {

Be careful that you fully understand the identifiers that are reserved for future library extension. This one is okay, because S is not a lower-case letter, but many authors are unaware of the exact rules.

uint64_t is not defined, because we never included <stdint.h>. In any case, I don't think we need exactly 64 bits, and this code should be able to function on platforms that can't provide uint64_t - I suggest using uint_fast64_t instead. And I'd probably give the type a name that expresses what we're using it for, to distinguish from other values of the same type:

typedef uint_fast64_t card_bit_vector;

For this particular function, given that the first thing we do is mask x down to 13 bits, we could be using a narrower type for the arithmetic.

#include <stdbool.h>
#include <stdint.h>

static bool isStraight(card_bit_vector cards)
{
    static const uint_fast16_t low_five_bits = 0x1f;
    /* determine whether low order 13 bits contain a straight - five consecutive 1s */
    for (uint_fast16_t x = cards & 0x1FFF;  x >= low_five_bits;  x >>= 1) {
        if ((x & low_five_bits) == low_five_bits) { return 1; }
    }
    /* not a straight */
    return 0;
}

The serious bug in this function, due to a missing test case, is that in poker, an ace may be either high or low, but we always use it as its low value here. We need to duplicate the ace into bit 13 and consider it there as well:

    uint_fast16_t x = cards & 0x1FFF;
    /* Duplicate the ace so it's both high and low */
    x |= (x & 1) << 13;

Now we get to the big function, assess(). I see no reason for it to be modifying the members of the hand argument, so we should make that an array-of-const - and return a strongly-typed enum rather than int:

enum hand {
    highCard, onePair, twoPair, threeOfKind, straight,
    flush, fullHouse, fourOfKind, straightFlush, royalFlush,
};

enum hand assess(const int h[])

Modern C doesn't require us to declare all variables before the first statement in the scope as we had to in the 1990s and before. It's better for the reader's cognition to minimise what's in their heads at any time.

Also, big1 must not be modified, so make that const.

The population counts of values and suits shouldn't be packed into single integers like that. It will be more time-efficient to represent them as arrays. If space were at a premium, we could pack all 17 counts into a single 64-bit quantity, but here we're in a function, and stack space for a couple of small arrays is not unreasonable.

If we had portable access to an efficient "population count" function, we would be able to get those population counts directly by masking the cards bit-vector. That's something to consider as a future enhancement for compilers that provide such a function.

Be careful in the comments with abbreviations. In particular cnt appears to me as a more offensive word than you intended - count would be much better.

Now, let's move on to the tests.

As I mentioned earlier, there are some missing tests. We should be testing the lowest straight (A2345) and the highest straight (XJQKA) as well as (or instead of) the medium straight. And we should also be testing some hands that match both flush and straight, but where the cards in the straight are not all the same suit:

        { d5, c3, sA, h2, s5, cA, d4 }, // bottom straight
        { dK, cJ, sA, hQ, sX, cA, dX }, // top straight
        { d4, d8, dX, dQ, s5, cX, d6 }, // flush beats straight

I think the enumeration of all the cards and their corresponding bit numbers is valuable enough to be part of the program, not just confined to the tests. And we should use its type for passing cards around.

When we deal randomly, I think it would be clearer to select one of 52 values, and convert that to a valid card, rather than doing rejection and resampling:

    for (int i = 0;  i < nCard;  ++i) {
        int x = rand() % 52;
        /* modify x to skip the non-card values */
        p[i] = x + x / 13 * 3;
    }

Instead of seeding the random number generator from the current time, consider allowing the user to specify seed, so we can have reproducible tests.

Six decimal places of precision in the histogram is misleading if we only examine 10,000 hands.

---

Modified code

Here's a version that I think is clearer and more maintainable. And it fixes the bug.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 4 suits of 13 cards each ('X' == 10).
// Note range for each suit changes with each Ace
enum card {
    hA = 0x00, h2, h3, h4, h5, h6, h7, h8, h9, hX, hJ, hQ, hK, // hearts
    cA = 0x10, c2, c3, c4, c5, c6, c7, c8, c9, cX, cJ, cQ, cK, // clubs
    dA = 0x20, d2, d3, d4, d5, d6, d7, d8, d9, dX, dJ, dQ, dK, // diamonds
    sA = 0x30, s2, s3, s4, s5, s6, s7, s8, s9, sX, sJ, sQ, sK  // spades
};

// Representation of a hand of cards - a bit is set for each card in
// hand, or unset if not in hand.
typedef uint_fast64_t card_bit_vector;

enum hand {
    highCard, onePair, twoPair, threeOfKind, straight,
    flush, fullHouse, fourOfKind, straightFlush, royalFlush,
};

enum {
    /* misc compile-time constants */
    nCard = 7, // number of cards available for hand
    oneSuit = 0x10, // offset from one suit to next in enum card
};

static unsigned suit_of(enum card c)
{
    return c / oneSuit;
}

static unsigned value_of(enum card c)
{
    return c % oneSuit;
}

static bool is_top_straight(card_bit_vector cards)
{
    return (cards & 0x1E01) == 0x1E01;
}

static bool is_straight(card_bit_vector cards)
{
    if (is_top_straight(cards)) {
        return true;
    }
    static const uint_fast16_t low_five_bits = 0x1f;
    /* determine whether low order 13 bits contain five consecutive 1s */
    for (uint_fast16_t x = cards & 0x1FFF;  x >= low_five_bits;  x >>= 1) {
        if ((x & low_five_bits) == low_five_bits) {
            /* found one */
            return true;
        }
    }
    /* not a straight */
    return false;
}

enum hand assess(const enum card h[])
{
    // Assess the hand into one of the ten categories.

    card_bit_vector bits = 0;
    int suit_count[4] = { 0 };
    int value_count[13] = { 0 };
    // Convert 7 unique card values into a bit-vector.
    // Also accumulate totals for each suit and rank
    static const card_bit_vector big1 = 1;
    for (size_t i = 0;  i < nCard;  ++i) {
        bits |= big1 << h[i]; // as single set bit
        ++suit_count[suit_of(h[i])];
        ++value_count[value_of(h[i])];
    }

    // destroy 'bits' (right shift)
    //      If a flush is found, determine whether it contains a straight.
    //      Otherwise, accumulate bits to determine a(mixed) straight soon.
    static const int aFlush = 5; // no. of cards in a flush, royal or otherwise
    card_bit_vector straight_bits = 0;
    for (int *n_suit = suit_count;  bits;  bits >>= oneSuit, ++n_suit) {
        if (*n_suit >= aFlush) {
            return is_top_straight(bits) ? royalFlush
                :  is_straight(bits) ? straightFlush
                :  flush;
        }
        straight_bits |= bits;
    }

    if (is_straight(straight_bits)) {
        return straight;
    }

    /* Now consider cards of matching rank (pairs, triples, etc) */
    int same_value[5] = { 0 }; /* count of absents, singletons, pairs, ..., quads */
    for (int *n_value = value_count;  n_value < value_count + 13;  ++n_value) {
        ++same_value[*n_value];
    }

    return same_value[4] > 0 ? fourOfKind
        :  same_value[3] > 1 ? fullHouse
        :  same_value[3] > 0 && same_value[2] > 0 ? fullHouse
        :  same_value[3] > 0 ? threeOfKind
        :  same_value[2] > 1 ? twoPair
        :  same_value[2] > 0 ? onePair
        :  highCard;
}


/// Test code

static char const *name(enum hand h)
{
    switch (h) {
    case highCard: return "0 High Card";
    case onePair: return "1 One Pair";
    case twoPair: return "2 Two Pair";
    case threeOfKind: return "3 Three of a kind";
    case straight: return "4 Straight";
    case flush: return "5 Flush";
    case fullHouse: return "6 Full House";
    case fourOfKind: return "7 Four of a kind";
    case straightFlush: return "8 Straight Flush";
    case royalFlush: return "9 Royal Flush";
    }
    /* invalid; can't happen */
    return "???";
}

static void show(const enum card h[nCard]) {
    for (int i = 0;  i < nCard;  ++i) {
        printf("%c%c ",
               "hcds"[suit_of(h[i])],
               "A23456789XJQK"[value_of(h[i])]);
    }
}

static void test(void) {
    // 10 composed samples to test assess(). Left-to-right order is not special
    const enum card hands[][nCard] = {
        { h4, cJ, d9, d5, s3, h7, sA }, // high card
        { h4, c3, d9, d5, s3, h7, sA }, // one pair
        { h9, c3, d9, d5, s3, h7, sA }, // two pair
        { h9, c3, d9, d5, s9, h7, sA }, // three of a kind
        { d5, c6, sA, h8, s5, c7, d4 }, // straight
        { d5, c3, sA, h2, s5, cA, d4 }, // bottom straight
        { dK, cJ, sA, hQ, sX, cA, dX }, // top straight
        { d5, dJ, dX, dQ, s5, c7, d6 }, // flush
        { d4, d8, dX, dQ, s5, cX, d6 }, // flush beats straight
        { d8, h8, s8, hQ, c7, sK, s7 }, // full house
        { h9, c9, d9, d5, s9, h7, sA }, // four of a kind
        { s5, s7, s6, s8, d5, c7, s4 }, // straight flush
        { dA, dJ, dX, dQ, s5, c7, dK }, // royal flush
    };

    for (unsigned i = 0; i < sizeof hands/sizeof hands[0]; i++) {
        show(hands[i]);
        printf("... %s\n", name(assess(hands[i])));
    }
}

static enum card *deal(enum card p[nCard])
{
    // We don't need strict uniformity or strong randomness for this
    // test.
    for (int i = 0;  i < nCard;  ++i) {
        int x = rand() % 52;
        /* modify x to skip the non-card values */
        p[i] = x + x / 13 * 3;
    }
    return p;
}

static void run(unsigned nLoop)
{
    const char *seed_string = getenv("TEST_SEED");
    if (!seed_string) { seed_string = "0"; }
    int seed = atoi(seed_string); /* 0 if it fails - fall back to time-based seed */
    if (!seed) {
        seed = (int)time(NULL);
    }
    srand((unsigned)seed);

    unsigned count[royalFlush + 1] = { 0 }; // simple histogram accumulator for 10 types
    enum card hand[nCard];
    for (unsigned i = 0;  i < nLoop;  ++i) {
        ++count[assess(deal(hand))];
    }

    /* Determine a suitable precision for output, according to number of samples */
    int precision = 1;
    for (unsigned x = 100;  x <= nLoop && precision < 10;  x *= 10) {
        ++precision;
    }
    for (unsigned i = highCard;  i <= royalFlush;  ++i) {
        printf("%.*f - %s\n", precision,
               count[i] * 1. / nLoop,
               name(i));
    }
}

int main(void)
{
    test();
    run(100000);
}

Note that this still only classifies the hands. It doesn't provide the information needed to determine which hand wins amongst those in the same group.