Yet another poker hand evaluator

A poker hand evaluator is a function that takes some representation of a poker hand as input, and outputs information about its strength: its category (high card, pair, two pairs, full house, etc) and enough additional information to break ties within that category. Poker hand evaluators are considered as a crucial component of poker AI, and have therefore received a lot of attention. A remarkable article by James Devlin provides an excellent overview.

Actually, I am not sure at all that exhaustive evaluations that provide probabilities to the sixth decimal are really important for poker strategy. I believe psychology is a lot more relevant, as well as more difficult to model in AI. But devising efficient evaluators is an interesting exercise, and I wondered how fast one could do it in javascript.

This page is an expansion on a Usenet discussion on comp.lang.javascript. Thanks to contributors, particularly Lasse Reichstein Nielsen, for helpful remarks.

Demo

This is a simple demo of a Texas Hold 'em evaluator. The seven cards on the top represent cards at showdown: the two hole cards of a given player and the five community cards. When all those cards have been chosen (either manually or randomly by clicking on "Fill" or a combination of both), the best set of five cards is determined and described in terms human poker players can understand. The machine encoding that was translated is shown under the human description as six hexadecimal digits.

Pick cards by clicking on them below, or Clear Fill Clear and fill

Output format

A poker hand evaluator typically returns an integer such that the higher integer represents the stronger hand: hand A beats hand B iff eval(A) > eval(B). (Which implies that hand B beats hand A iff eval(A) < eval(B), and that hand A and hand B tie iff eval(A) == eval(B).)

A remarkable fact, discovered by Kevin Suffecool ("Cactus Kev"), is that while there are C(52, 5) or 2 598 960 possible 5 card poker hands, they fall into only 7 462 distinct equivalence classes in which each hand has the same value.

The reduction is even more dramatic for 7 card hands: the C(52, 7) = 133 784 560 possible hands collapse to just 4 824 distinct values if you pick the five best cards. (There is no way the worst hands with only five cards, say 7♣ 6♠ 5♠ 4♣ 2♠, can occur if you have more cards that may enter in the combination. They are bound to make a straight, or a pair, or be higher than a 7.)

Given that fact and the requirement that evaluators return a value that always determines the winner or a tie, that value is therefore equivalent to a number between 0 and 4 823 in the case of Texas Hold'em. Some evaluators code an extra, theoretically superfluous information: the category (straight flush, four of a kind, ..., high card), but apart from that, they often simply give the number of the relevant Cactus Kev equivalence class.

That is all right for machines, but it makes comprehension by a human user very difficult. I propose a coding that works just as well for machines, but also allows an easy translation into human terms, as demonstrated above: six hexadecimal digits.

The first encodes the category, with the following code: 0 (0x0) => high card, 1 (0x1) => one pair, 2 (0x2) => two pairs, 3 (0x3) => three of a kind a.k.a. trip, 4 (0x4) => straight, 5 (0x5)  => flush, 6 (0x6) => full house, 7 (0x7) => four of a kind a.k.a. quad, 8 (0x8) => straight flush. ("Royal flush" is just a fancy name for a straight flush whose high card is an ace. There is no reason to turn it into a separate category.)

The remaining five hexadecimal digits represent the ranks of the 5 most significant cards, from 0 (0x0) => deuce to 12 (0xc) => ace.

E.g.:

• 0x27744a means Two pairs (0x2), nines (0x77) and sixes (0x44), fifth card a queen (0xa).
• 0x6999cc means Full house (0x6), jacks (0x999) full of aces (0xcc).
• 0x4a9876 means Straight (0x4); top card: queen (0xa)
• 0x166953 means Pair (0x1) of eights (0x66) followed by jack, seven and five (0x953)

Etc - hopefully, the hexadecimal digits in the demo have become clearer now.

Card encoding

There are many ways to encode a card as a small integer. I submit that the most sensible way by far is to order the deck by rank first, and by suit within each rank. Each card is represented as an integer in the range [0, 51], its zero-based index in that order of the deck. This allows to find the suit simply by taking the two least significant bits, and its rank by shifting down two places.

The order of the suits doesn't usually matter in poker, and there is therefore no agreement in the encodings. For the sake of consistency, I suggest the alphabetical order used in bridge: clubs (lowest), followed by diamonds, hearts, and spades (highest).

Thus:

2♣	2♦	2♥	2♠	3♣	3♦	3♥	3♠	4♣	4♦	4♥	4♠	5♣	5♦	5♥	5♠	6♣	6♦	6♥	6♠	7♣	7♦	7♥	7♠	8♣	8♦
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
8♥	8♠	9♣	9♦	9♥	9♠	T♣	T♦	T♥	T♠	J♣	J♦	J♥	J♠	Q♣	Q♦	Q♥	Q♠	K♣	K♦	K♥	K♠	A♣	A♦	A♥	A♠
26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51

A naive evaluator

The evaluator (NaiveHandEval) used in the demo is written in javascript and runs at about 250 000 evaluations per second on my 2008 laptop, using a good javascript engine like V8 used in Chromium or Google Chrome. Less efficient javascript implementations may be much slower, but not enough to cause any noticeable delay in applications where a single evaluation is submitted to a human user. It is good enough for its intended use.

It attempts to be clever, too. It does not sort the hand, it counts cards per suit and rank instead. That could be smart, because those counts are the essence of what is needed to determine the strength of the hand. The only case something else is needed is when a suit has five cards or more, that is, if we have a flush or a straight flush. (With five cards or more out of seven in the same suit there are at most two cards of a different suit, therefore we cannot have a full house or a quad, and we have at least a flush, anything less is irrelevant.)

This first version of the evaluator is however much too slow for the typical uses in poker AI, where one needs to evaluate several millions of potential hands. Despite its ingenuity, it is still what James Devlin calls a naive evaluator. Counting cards per rank may be good, but using the counts in a lengthy cascade of tests is bad.

Counting ranks

Let us show the demo again with some additional information.

Pick cards by clicking on them below, or Clear Fill Clear and fill
													0
													0
													0
													0
0	0	0	0	0	0	0	0	0	0	0	0	0

The value of the hand is uniquely determined by what appears in the bottom row of the demo: what I call the signature of the hand. (It also appears under the evaluation of the hand.)

In most cases, it is simply the number of cards per rank. If there are five consecutive ranks ("consecutive" meaning possibly A-2-3-4-5) with non-zero counts, it is a straight, if there are four cards of the same rank, it is a quad, etc. The kickers can be found by going from left to right among the unused non-zero counts until five cards have been used.

The exception is when one of the numbers in the right column in the demo (the numbers of cards per suit) is 5 or higher. The rank counts no longer matter, what we need to know is the ranks of the cards in the flush suit. If there are five consecutive ranks in that suit ("consecutive" meaning possibly A-2-3-4-5), we have a straight flush. Otherwise we have a flush, and the five highest ranks provide the kickers.

The demo reflects that: when a suit has five cards or more, the digits at the bottom become 2 in the columns where the flush suit has a card and 0 elsewhere. The only information that matters is still what appears in the bottom row of the demo. The difference between the two cases is reflected in the sum of the digits: always 7 when no suit has more than four cards, at least 10 if a suit has five cards or more.

The signature is encoded by considering the counts as digits in base 5, aces having the highest rank. The highest possible signature is 4300000000000₅, that is, 1123046875₁₀ or 0x42f055db. The signature always fits in 31 bits.

A better evaluator

Let us try a better use of the signature: as a key into a hash table, or possibly a sparse array, that provides the value.

Implementations in languages like javascript or Python or Perl or Ruby may rely on built-in support that is presumably close to optimal - associating a value with an arbitrary key (e.g., an identifier) is one of the most crucial operations in interpreted languages; their developers have surely treated the problem with utmost care. An implementation in C will have to device its own solution, e.g., a perfect minimal hash, or possibly a non-perfect non-minimal hash with better overall performance, which provides an interesting case study. Implementations in C++ or Java fall somewhere in between: implementors can choose between using standard solutions or coming up with something better for the particular case.

But first: is the approach viable? How big would that lookup table be?

Size of the lookup table

Consider the case of no flush. Each of the 13 columns could have a value between O and 4. But they couldn't all have a value of 4, nor all a value of 0. There are actually quite severe constraints. The sum of the counts must be 7, and no column may have more than four.

It is equivalent to the question of how many ways we can accommodate 7 overnight guests in 13 rooms with four beds in each, a special case of the more general problem that is solved by the following javascript function:

function accommodations(nGuests, nRooms, maxCapacity, treatment) {
  var count = 0;
  var guestsPerRoom = [];            // guestsPerRoom[i] is the number
                                     // of guests in room number i
  for (var i = 0; i < nRooms; i++) {
    guestsPerRoom.push(0);           // initialise to 0 in all rooms
  }
 
  function accommodate(remainingGuests, room, maxCapacity, guestsPerRoom, treatment) {
    if (remainingGuests == 0) {
      if (typeof treatment == 'function') {
        treatment(guestsPerRoom);
      }
      count++;
      return;
    }
 
    for (var i = room; i < nRooms ; i++) {
      if (guestsPerRoom[i] < maxCapacity) {
        guestsPerRoom[i]++;
        accommodate(remainingGuests - 1, i, maxCapacity, guestsPerRoom, treatment);
        guestsPerRoom[i]--;
      }
    }
  }
 
  accommodate(nGuests, 0, maxCapacity, guestsPerRoom, treatment);
  return count;
}

The argument treatment, if defined, is a function that takes the Array guestsPerRoom as argument. We shall use it soon to actually compute the lookup table. But for now, we only want to determine the size of the table, so we leave that argument out.

First, the non-flushes: accommodations(7, 13, 4) returns 49205.

Next, the flushes. They come in three flavours: with 7, 6 and 5 cards in the flush suit; accommodations(7, 13, 1) returns 1716, accommodations(6, 13, 1) also returns 1716, and accommodations(5, 13, 1) returns 1287.

Altogether, 49205 + 1716 + 1716 + 1287 = 53924 entries. Less than 2¹⁶: the size of the table should pose no problem on most platforms. (But it is more than 2¹⁵, which may cause Java implementers to deplore the absence of unsigned shorts.)

Computing the signature

To compute the signature, we first need to determine whether we have a flush, that is, whether one of the suits has five cards or more.

This is an efficient way to do that (remember that card & 3 provides the suit of the card):

    var suitCounts = 0x3333; // four 4-bit counters, one for each suit
                             // with an offset of 3 to set the high bit
                             // on counts of 5 or more.
 
    suitCounts += 1 << ((card0 & 3) << 2);
    suitCounts += 1 << ((card1 & 3) << 2);
    suitCounts += 1 << ((card2 & 3) << 2);
    suitCounts += 1 << ((card3 & 3) << 2);
    suitCounts += 1 << ((card4 & 3) << 2);
    suitCounts += 1 << ((card5 & 3) << 2);
    suitCounts += 1 << ((card6 & 3) << 2);
 
    if (suitCounts & 0x8888) { 
      // there is a flush
    } else {
      // there is no flush
    }

The trick of setting the high bit iff the count is five or more also serves to determine the suit that has the flush:

    if (suitCounts & 0x8888) { // there is a flush
      var flushSuit;  // suit of the flush
      if (suitCounts & 0x88) {
        if (suitCounts & 0x8) {
          flushSuit = 0;
        } else {
          flushSuit = 1;
        }
      } else {
        if (suitCounts & 0x800) {
          flushSuit = 2;
        } else {
          flushSuit = 3;
        }
      }
    }

In each of the two cases, flush and no flush, we count ranks and encode them as powers of five. (In the case of flushes, we double the result at the end.) The straightforward way is like this: signature += Math.pow(5, card >> 2). But that is slow. It is better to compute a lookup table of 52 entries, one per card. This table is global, to avoid creating and destroying it at each call - but its reference is copied to a local variable to avoid accessing a global.

The resulting evaluator:

  var handValues = computeHandValues(); // lookup table
 
  // table lookup is faster than Math.pow(5, n)
  var signatureDigits = [
    1, 1, 1, 1, 5, 5, 5, 5, 25, 25, 25, 25, 125, 125, 125, 125,
    625, 625, 625, 625, 3125, 3125, 3125, 3125, 15625, 15625,
    15625, 15625, 78125, 78125, 78125, 78125, 390625, 390625,
    390625, 390625, 1953125, 1953125, 1953125, 1953125, 9765625,
    9765625, 9765625, 9765625, 48828125, 48828125, 48828125,
    48828125, 244140625, 244140625, 244140625, 244140625
  ];
 
  function fastHandEval(card0, card1, card2, card3, card4, card5, card6) {
 
  /*
  Now, the fast version. Like the naive one, it checks whether any suit
  has 5 cards or more, but after that, the pass through the rank counts
  and all the decisions at the end are replaced by the computation of
  a key enabling a single lookup in handValues.
 
  Since error checking takes time, it has been omitted. Users beware: make
  sure that the arguments are 7 *different* integers between O and 51.
  */
 
    var sD = signatureDigits;  // local variables are faster than globals
                               // in many implementations
 
    var suitCounts = 0x3333; // four 4-bit counters, one for each suit
                             // all initialised to 3
 
    var signature; // a 13-digit number in base 5 to serve as lookup key.
             // If there is no flush, its digits simply indicate the count
             // of cards per rank. The sum of these digits will always be 7.
 
             // If a flush is present, a digit of 2 indicates the presence
             // of a card of the relevant suit at that rank, otherwise the
             // digit is 0. The sum of those digits will always be >= 10.
 
    suitCounts += 1 << ((card0 & 3) << 2);
    suitCounts += 1 << ((card1 & 3) << 2);
    suitCounts += 1 << ((card2 & 3) << 2);
    suitCounts += 1 << ((card3 & 3) << 2);
    suitCounts += 1 << ((card4 & 3) << 2);
    suitCounts += 1 << ((card5 & 3) << 2);
    suitCounts += 1 << ((card6 & 3) << 2);
 
    if (suitCounts & 0x8888) { // there is a flush
      var flushSuit;  // suit of the flush
 
      if (suitCounts & 0x88) {
        if (suitCounts & 0x8) {
          flushSuit = 0;
        } else {
          flushSuit = 1;
        }
      } else {
        if (suitCounts & 0x800) {
          flushSuit = 2;
        } else {
          flushSuit = 3;
        }
      }
 
      signature = (card0 & 3) == flushSuit ? sD[card0] : 0;
      if ((card1 & 3) == flushSuit) signature += sD[card1];
      if ((card2 & 3) == flushSuit) signature += sD[card2];
      if ((card3 & 3) == flushSuit) signature += sD[card3];
      if ((card4 & 3) == flushSuit) signature += sD[card4];
      if ((card5 & 3) == flushSuit) signature += sD[card5];
      if ((card6 & 3) == flushSuit) signature += sD[card6];
 
      return handValues[signature << 1];
    }
 
    // no flush
    signature  = sD[card0];
    signature += sD[card1];
    signature += sD[card2];
    signature += sD[card3];
    signature += sD[card4];
    signature += sD[card5];
    signature += sD[card6];
 
    return handValues[signature];
  } // end of function fastHandEval

Creating the lookup table

To create the lookup table, we apply the naive evaluator inside the accommodations function we used before:

function computeHandValues() {
  var table = [];
 
  function treatNonFlushes() {
    var cards = [];
    var signature = rankCounts.join('');
    var suit = 0;
    for (var i = 0; i < 13; i++) {
      for (var j = 0; j < rankCounts[i]; j++) {
        cards.push(4 * i + suit++ %4);
      }
    }
    table[parseInt(signature, 5)] = naiveHandEval(cards[0], cards[1], cards[2],
      cards[3], cards[4], cards[5], cards[6]);
  }
 
  function treatFlushes() {
    var cards = [];
    var signature = rankCounts.join('').replace(/1/g, '2');
    for (var i = 0; i < 13; i++) {
      if (rankCounts[i]) {
        cards.push(4 * i);
      }
    }
    if (cards.length < 7) {
      cards.push(1); // anything with % 4 != 0 goes
    }
    if (cards.length < 7) {
      cards.push(2);
    }
    table[parseInt(signature, 5)] = naiveHandEval(cards[0], cards[1], cards[2],
      cards[3], cards[4], cards[5], cards[6]);
  }
 
  accommodations(7, 13, 4, treatNonFlushes);
  accommodations(7, 13, 1, treatFlushes);
  accommodations(6, 13, 1, treatFlushes);
  accommodations(5, 13, 1, treatFlushes);
 
  return table;
} // end of function computeHandValues

Conclusion

Using V8, the new evaluator runs about sixty times faster than the naive version. On my 2008 laptop, where a full test of the 133 784 560 possible hands took nine minutes, it now takes nine seconds, at about 15 million hands per second. (And of course, more recent or more powerful computers may do much better.)