Quick 7-card Poker Ranking in Java

• Download source code from Github

Introduction

While working on my poker bot, I came across various people asking for a 7-card poker evaluator. After learning that quick evaluators are not freely available, I decided to write one myself. Currently, it evaluates 50 million 7-card poker hands per second.

Background

When given 7 poker cards, there are 21 possibilities of 5 cards. The best one counts as "your hand". I assume you're familiar with Texas Holdem poker or at least with poker.

The passion required for this project was initiated by the following piece of JavaScript code I found:

function rankPokerHand(cs,ss) {
 
  var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
  for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
  v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
  v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);

Believe it or not, those four lines are enough to discriminate the combinations of all 5-card hands. The article is brilliant and you should check it out.

The above code does not break ties, it tells only what combination you have (straight, full house, etc.)

While I was translating that to Java, I found my second resource. It is from 2006 and does the same as the above, except that it's in C and does break ties. He also mentions that he has sold a closed-source 7-card evaluator, but the company he sold it to does no longer seem to exist.

I guess the JavaScript guy got a lot of his ideas from that second link, but the most brilliant part, the modulus 15 (%15), is his idea. While I was translating it, I found that part of the work that the JavaScript guy did was working around JavaScript limitations. I needed to reverse(-engineer) those workarounds to get optimal performing Java code.

One of the C guy's brilliant ideas was to use prime numbers to represent cards. Each number, from 2 to 14 (=ace) but not including the suits, is represented by the next prime number. The issue he was facing was: He wanted to construct a single number representing a 5-card hand (without the suits). But when you swap cards in the input, the constructed number should be the same. Also, the constructed number should be different from any other constructed number if any card is different. These are all characteristics of multiplying primes. The maximum number you can construct for a 5 card hand is for AAAK, which is 41x41x41x41x37 = 104,553,157 and that fits in an int.

While I was thinking that through, I realized that he needs to lookup the prime and a lot of numbers below that 104,553,157 are unused this way. In fact, only numbers with exactly 5 prime factors smaller than 42 are used. If you multiply the above big number by two more kings (37x37) for a seven-card hand, it doesn't fit in an int anymore. I found a more efficient method, a certain recurrence relation. Unfortunately, it's inefficient to solve that recurrence relation so I need to do a lookup as well, but I can do additions where he does multiplications (saving clockcycles) and each 7-card hand does then fit in an int (excluding the suits).

The 5-card Version

First, let's look at the five-card version translated from the JavaScript guy. For me, it was not only useful for learning, but I also use this function to populate my lookup tables in 0.1s for the 7-card version. The rank() is an int between 0 and 11 indicating the strength of the hand. I won't go into too much detail, but the returned int value will be similar to that of the 7-card version later:

• Just before the "break ties" part that I added, value contains the rank between 0 and 11. This is shift 26 places to the left, so that this is always the most important part when comparing two hands (int results from the function).
• If we know we have full house, we need a row of bits where only something remains if there are 3 bits in a row, so that AA333 will lose from 44455 (which is correct). Since the A-bit is more to the left, the second hand would lose if we didn't do that.
• Finally, we add the set at the least significant bits. These are the kickers.

You can call it like:

int value = rankPokerHand5(new int[]{10, J, A, K, Q}, new int[]{1, 1, 1, 1, 1  });

If you want to know the rank of your hand (what kind of hand it is), you simply call:

int rank = value >> 26

private final static int[] hands={Combination.FOUR_OF_A_KIND.rank(),
    Combination.STRAIGHT_FLUSH.rank(), Combination.STRAIGHT.rank(),
    Combination.FLUSH.rank(), Combination.HIGH_CARD.rank(), Combination.PAIR.rank(),
    Combination.TWO_PAIR.rank(), Combination.ROYAL_FLUSH.rank(),
    Combination.THREE_OF_A_KIND.rank(), Combination.FULL_HOUSE.rank()};

// each suit should be 1, 2, 4, or 8!
public static int rankPokerHand5(int[] nr, int[] suit) {
    long v = 0L;
    int set = 0;
    for (int i=0; i<5; i++) {
        v += (v&(15L<<(nr[i]*4))) + (1L<<(nr[i]*4));
        set |= 1 << (nr[i]-2);
    }
    int value = (int) (v % 15L - ((hasStraight(set)) || (set == 0x403c/4) ? 3L : 1L));
    value -= (suit[0] == (suit[1]|suit[2]|suit[3]|suit[4]) ? 1 : 0) * ((set == 0x7c00/4) ? -5 : 1);
    value = hands[value];

    // break ties
    value = value << 26;
    value |= value == Combination.FULL_HOUSE.rank()<<26 ?
        64-Long.numberOfLeadingZeros(v & (v<<1) & (v<<2)) << 20
            : set == 0x403c/4 ? 0
            : (64-Long.numberOfLeadingZeros(v & (v<<1)) << 20) |
                  (Long.numberOfTrailingZeros(v & (v<<1)) << 14);
    value |= set;

    return value;
}

Unfortunately, I didn't find a way to avoid the cast from long to int.

The 7-card Version

As you can see, while calculating v, we don't need the suit. What we can do is calculate for each 7-combination of numbers a unique value (key), and fill an int[] array with a precomputed v for each such number. It doesn't matter what the calculated key is, as long as it's easy to compute, is small enough such that we can create an array of its size, and is different when the cards are different. Precomputing v has another advantage: it also works for 7-cards. For the precomputation, we simply take every possible 7 card hand (without the suits! Otherwise, the precomputation would be much more expensive) and from those 7 cards, we regard all 21 offsuited 5-card hands. We pick the one with the highest outcome. We store its v in an array that's keyed by the magical number we were talking about. But how do we calculate that number?

The Recurrence Relation

We want to find a number representing a 7-card hand that is easy to calculate and does not grow too large. We need to start somewhere, so let's start with int key = 0. We look at the first card, we see it's a 2. Let's map that to 1 and add it to key. So key = 1. If we encounter another 2, we map that to 1 again and add it to key. So if key is 2, it means we've seen two 2's. This way, the key can grow up to 4. (since there are only four 2's) So we can map 3 to 5: If we encounter a 3, we add 5, So T(2) = 1 and T(3) = 5. The maximum number that we can get now using only 3's and 2's is 4 T(3) + 3 T(2) = 4*5 + 3*1 = 23. So we can use 24 to map 5 on. The maximum number at any point is 4 times the previous plus 3 times the value before that (as we have 4 cards of each number and 7 cards in total).

T(2) = 1
T(3) = 5
T(n) = 4 T(n-1) + 3 T(n-2) +1

When we have a card x, in the code we want to find T(x). For this, you need to solve the recurrence relation, but unfortunately, it's no use as the solution will have an exponent and you will need float, which makes it more efficient to use a precomputed lookup table (an int[] array of length 13). While precomputing it, I found another optimization: we can actually map 2 to 0. (T(2) = 0). For the ace, we get T(A) = 24,342,288, which I think is a 25 bit number. To calculate the key for a hand, we simply add those values together. When we want to lookup v for a hand, we add the values again and use that as key to our int array.

The Code

There are still some difficulties: We stored the best hand for each offsuit case, but this may not be the best hand in the suited case. But this is only applicable for straight flushes and flushes. Therefore, we store some extra information in other lookup tables. You need to look at the full code if you want to wholly understand this, as variables out the scope are used (see link at the bottom).

/*
 * Get an int that is bigger as the hand is bigger, breaking ties and keeping actual (real) ties.
 * Apply >>26 to the returned value afterwards, to get the rank of the Combination (0..11)
 *
 * Ideas were gotten from:
 * http://www.codeproject.com/Articles/569271/A-Poker-hand-analyzer-in-JavaScript-using-bit-math
 * http://suffe.cool/poker/evaluator.html
 *
 * nr is an array of length 7, where each number should be 2..14.
 * suit is an array of length 7, where each number
 * should be 0,1,2 or 3. This is different from rankPokerHand5
 */
public static int rankPokerHand7(int[] nr, int[] suit) {
    int[] cards = new int[4];
    int index=0;
    for (int i=0; i<7; i++) {
        int n = nr[i] - 2;

        cards[suit[i]] |= 1 << n;

        index += recurrence[n];
    }
    int value = lookup[index];
    int fl = 0;
    for (int i=0; i<4; i++) {
        fl |= flush[cards[i]];
    }
    int str = straight[index];

    int straightFl = fl==0 ? 0 :
        (straightFlush[str&cards[0]] | straightFlush[str&cards[1]] |
         straightFlush[str&cards[2]] | straightFlush[str&cards[3]]);

    straightFl = Integer.highestOneBit(straightFl);

    return straightFl == 1 << 12 ? (Combination.ROYAL_FLUSH.rank() << 26)
        : straightFl != 0 ? (Combination.STRAIGHT_FLUSH.rank() << 26) | straightFl
        : value >> 26 == Combination.FULL_HOUSE.rank() ? value
        : fl != 0 ? (Combination.FLUSH.rank() << 26) | fl
        : value;
}

Improvements

There's still much room for improvement and that's of course on the optimization part. The lookup tables are huge. Somehow Java doesn't like a nested array lookup (it's slow) cards[suit[i]]. I'm also working on a way to lookup the entire hand using a whole different method, but I didn't describe that here as for some reason that has worse performance.

Source code: github

Edits After Publication

The recurrence relation can be massively improved, see the comments at: math.stackexchange. The current status is 50 million hands per second on my i7 processor.