Algorithm to give a value to a 5 card Poker hand

问题:

I am developing a poker game as college project and our current assignment is to write an algorithm to score a hand of 5 cards, so that the scores of two hands can be compared to each other to determine which is the better hand. The score of a hand has nothing to do with the probability of what hands could be made upon the draw being dealt with random cards, etc. - The score of a hand is based solely on the 5 cards in the hand, and no other cards in the deck.

The example solution we were given was to give a default score for each type of Poker hand, with the score reflecting how good the hand is - like this for instance:

//HAND TYPES:
ROYAL_FLUSH = 900000
STRAIGHT_FLUSH = 800000
...
TWO_PAIR = 200000
ONE_PAR = 100000

Then if two hands of the same type are compared, the values of the cards in the hands should be factored into the hand's score.

So for example, the following formula could be used to score a hand:

HAND_TYPE + (each card value in the hand)^(the number of occurences of that value)

So, for a Full House of three Queens and two 7s, the score would be:

600000 + 12^3 + 7^2

This formula works for the most part, but I have determined that in some instances, two similar hands can return the exact same score, when one should actually beat the other. An example of this is:

hand1 = 4C, 6C, 6H, JS, KC
hand2 = 3H, 4H, 7C, 7D, 8H

These two hands both have one pair, so their respective scores are:

100000 + 4^1 + 6^2 + 11^1 + 13^1 = 100064
100000 + 3^1 + 4^1 + 7^2 + 8^1 = 100064

This results in a draw, when clearly a pair of 7s trumps a pair of 6s.

How can I improve this formula, or even, what is a better formula I can use?

By the way, in my code, hands are stored in an array of each card's value in ascending order, for example:

[2H, 6D, 10C, KS, AS]

---

EDIT:

Here is my final solution thanks to the answers below:

    /**
     * Sorts cards by putting the "most important" cards first, and the rest in decreasing order.
     * e.g. High Hand:  KS, 9S, 8C, 4D, 2H
     *      One Pair:   3S, 3D, AH, 7S, 2C
     *      Full House: 6D, 6C, 6S, JC, JH
     *      Flush:      KH, 9H, 7H, 6H, 3H
     */
    private void sort() {
        Arrays.sort(hand, Collections.reverseOrder());      // Initially sorts cards in descending order of game value
        if (isFourOfAKind()) {                              // Then adjusts for hands where the "most important" cards
            sortFourOfAKind();                              // must come first
        } else if (isFullHouse()) {
            sortFullHouse();
        } else if (isThreeOfAKind()) {
            sortThreeOfAKind();
        } else if (isTwoPair()) {
            sortTwoPair();
        } else if (isOnePair()){
            sortOnePair();
        }
    }

    private void sortFourOfAKind() {
        if (hand[0].getGameValue() != hand[HAND_SIZE - 4].getGameValue()) {     // If the four of a kind are the last four cards
            swapCardsByIndex(0, HAND_SIZE - 1);                                 // swap the first and last cards
        }                                                                       // e.g. AS, 9D, 9H, 9S, 9C => 9C, 9D, 9H, 9S, AS
    }

    private void sortFullHouse() {
        if (hand[0].getGameValue() != hand[HAND_SIZE - 3].getGameValue()) {     // If the 3 of a kind cards are the last three
            swapCardsByIndex(0, HAND_SIZE - 2);                                 // swap cards 1 and 4, 2 and 5
            swapCardsByIndex(HAND_SIZE - 4, HAND_SIZE - 1);                     // e.g. 10D, 10C, 6H, 6S, 6D => 6S, 6D, 6H, 10D, 10C
        }
    }

    private void sortThreeOfAKind() {                                                                                                                               // If the 3 of a kind cards are the middle 3 cards
        if (hand[0].getGameValue() != hand[HAND_SIZE - 3].getGameValue() && hand[HAND_SIZE - 1].getGameValue() != hand[HAND_SIZE - 3].getGameValue()) {             // swap cards 1 and 4
            swapCardsByIndex(0, HAND_SIZE - 2);                                                                                                                     // e.g. AH, 8D, 8S, 8C, 7D => 8C, 8D, 8S, AH, 7D
        } else if (hand[0].getGameValue() != hand[HAND_SIZE - 3].getGameValue() && hand[HAND_SIZE - 4].getGameValue() != hand[HAND_SIZE - 3].getGameValue()) {
            Arrays.sort(hand);                                                                                                                                      // If the 3 of a kind cards are the last 3,
            swapCardsByIndex(HAND_SIZE - 1, HAND_SIZE - 2);                                                                                                         // reverse the order (smallest game value to largest)
        }                                                                                                                                                           // then swap the last two cards (maintain the large to small ordering)
    }                                                                                                                                                               // e.g. KS, 9D, 3C, 3S, 3H => 3H, 3S, 3C, 9D, KS => 3H, 3S, 3C, KS, 9D

    private void sortTwoPair() {                                                                                                                                    
        if (hand[0].getGameValue() != hand[HAND_SIZE - 4].getGameValue()) {                                                                                         // If the two pairs are the last 4 cards
            for (int i = 0; i < HAND_SIZE - 1; i++) {                                                                                                               // "bubble" the first card to the end
                swapCardsByIndex(i, i + 1);                                                                                                                         // e.g. AH, 7D, 7S, 6H, 6C => 7D, 7S, 6H, 6C, AH
            }
        } else if (hand[0].getGameValue() == hand[HAND_SIZE - 4].getGameValue() && hand[HAND_SIZE - 2].getGameValue() == hand[HAND_SIZE - 1].getGameValue()) {      // If the two pairs are the first and last two cards
            swapCardsByIndex(HAND_SIZE - 3, HAND_SIZE - 1);                                                                                                         // swap the middle and last card
        }                                                                                                                                                           // e.g. JS, JC, 8D, 4H, 4S => JS, JC, 4S, 4H, 8D
    }

    private void sortOnePair() {                                                                    // If the pair are cards 2 and 3, swap cards 1 and 3
        if (hand[HAND_SIZE - 4].getGameValue() == hand[HAND_SIZE - 3].getGameValue()) {             // e.g QD, 8H, 8C, 6S, 4J => 8C, 8H, QD, 6S, 4J
            swapCardsByIndex(0, HAND_SIZE - 3);
        } else if (hand[HAND_SIZE - 3].getGameValue() == hand[HAND_SIZE - 2].getGameValue()) {      // If the pair are cards 3 and 4, swap 1 and 3, 2 and 4 
            swapCardsByIndex(0, HAND_SIZE - 3);                                                     // e.g. 10S, 8D, 4C, 4H, 2H => 4C, 4H, 10S, 8D, 2H
            swapCardsByIndex(HAND_SIZE - 4, HAND_SIZE - 2);
        } else if (hand[HAND_SIZE - 2].getGameValue() == hand[HAND_SIZE - 1].getGameValue()) {      // If the pair are the last 2 cards, reverse the order
            Arrays.sort(hand);                                                                      // and then swap cards 3 and 5
            swapCardsByIndex(HAND_SIZE - 3, HAND_SIZE - 1);                                         // e.g. 9H, 7D, 6C, 3D, 3S => 3S, 3D, 6C, 7D, 9H => 3S, 3D, 9H, 7D, 6C 
        }
    }

    /**
     * Swaps the two cards of the hand at the indexes taken as parameters
     * @param index1
     * @param index2
     */
    private void swapCardsByIndex(int index1, int index2) {
        PlayingCard temp = hand[index1];
        hand[index1] = hand[index2];
        hand[index2] = temp;
    }

    /**
     * Gives a unique value of any hand, based firstly on the type of hand, and then on the cards it contains
     * @return The Game Value of this hand
     * 
     * Firstly, a 24 bit binary string is created where the most significant 4 bits represent the value of the type of hand
     * (defined as constants private to this class), the last 20 bits represent the values of the 5 cards in the hand, where
     * the "most important" cards are at greater significant places. Finally, the binary string is converter to an integer.
     */
    public int getGameValue() {
        String handValue = addPaddingToBinaryString(Integer.toBinaryString(getHandValue()));

        for (int i = 0; i < HAND_SIZE; i++) {
            handValue += addPaddingToBinaryString(Integer.toBinaryString(getCardValue(hand[i])));
        }

        return Integer.parseInt(handValue, 2);
    }

    /**
     * @param binary
     * @return the same binary string padded to 4 bits long
     */
    private String addPaddingToBinaryString(String binary) {
        switch (binary.length()) {
        case 1: return "000" + binary;
        case 2: return "00" + binary;
        case 3: return "0" + binary;
        default: return binary;
        }
    }

    /**
     * @return Default value for the type of hand
     */
    private int getHandValue() {
        if (isRoyalFlush())     { return ROYAL_FLUSH_VALUE; }       
        if (isStraightFlush())  { return STRAIGHT_FLUSH_VALUE; }
        if (isFourOfAKind())    { return FOUR_OF_A_KIND_VALUE; }
        if (isFullHouse())      { return FULL_HOUSE_VALUE; }
        if (isFlush())          { return FLUSH_VALUE; }     
        if (isStraight())       { return STRAIGHT_VALUE; }      
        if (isThreeOfAKind())   { return THREE_OF_A_KIND_VALUE; }
        if (isTwoPair())        { return TWO_PAIR_VALUE; }
        if (isOnePair())        { return ONE_PAIR_VALUE; }
        return 0;
    }

    /**
     * @param card
     * @return the value for a given card type, used to calculate the Hand's Game Value
     * 2H = 0, 3D = 1, 4S = 2, ... , KC = 11, AH = 12
     */
    private int getCardValue(PlayingCard card) {
        return card.getGameValue() - 2;
    }

回答1:

There are 10 recognized poker hands:

9 - Royal flush
8 - Straight flush (special case of royal flush, really)
7 - Four of a kind
6 - Full house
5 - Flush
4 - Straight
3 - Three of a kind
2 - Two pair
1 - Pair
0 - High card

If you don't count suit, there are only 13 possible card values. The card values are:

2 - 0
3 - 1
4 - 2
5 - 3
6 - 4
7 - 5
8 - 6
9 - 7
10 - 8
J - 9
Q - 10
K - 11
A - 12

It takes 4 bits to code the hand, and 4 bits each to code the cards. You can code an entire hand in 24 bits.

A royal flush would be 1001 1100 1011 1010 1001 1000 (0x9CBA98)

A 7-high straight would be 0100 0101 0100 0011 0010 0001 (0x454321)

Two pair, 10s and 5s (and an ace) would be 0010 1000 1000 0011 0011 1100 (0x28833C)

I assume you have logic that will figure out what hand you have. In that, you've probably written code to arrange the cards in left-to-right order. So a royal flush would be arranged as [A,K,Q,J,10]. You can then construct the number that represents the hand using the following logic:

int handValue = HandType; (i.e. 0 for high card, 7 for Four of a kind, etc.)
for each card
    handValue = (handValue << 4) + cardValue  (i.e. 0 for 2, 9 for Jack, etc.)

The result will be a unique value for each hand, and you're sure that a Flush will always beat a Straight and a king-high Full House will beat a 7-high Full House, etc.

Normalizing the hand

The above algorithm depends on the poker hand being normalized, with the most important cards first. So, for example, the hand [K,A,10,J,Q] (all of the same suit) is a royal flush. It's normalized to [A,K,Q,J,10]. If you're given the hand [10,Q,K,A,J], it also would be normalized to [A,K,Q,J,10]. The hand [7,4,3,2,4] is a pair of 4's. It will be normalized to [4,4,7,3,2].

Without normalization, it's very difficult to create a unique integer value for every hand and guarantee that a pair of 4's will always beat a pair of 3's.

Fortunately, sorting the hand is part of figuring out what the hand is. You could do that without sorting, but sorting five items takes a trivial amount of time and it makes lots of things much easier. Not only does it make determining straights easier, it groups common cards together, which makes finding pairs, triples, and quadruples easier.

For straights, flushes, and high card hands, all you need to do is sort. For the others, you have to do a second ordering pass that orders by grouping. For example a full house would be xxxyy, a pair would be xxabc, (with a, b, and c in order), etc. That work is mostly done for you anyway, by the sort. All you have to do is move the stragglers to the end.

回答2:

As you have found, if you add together the values of the cards in the way you have proposed then you can get ambiguities.

100000 + 4^1 + 6^2 + 11^1 + 13^1 = 100064
100000 + 3^1 + 4^1 + 7^2 + 8^1 = 100064

However, addition is not quite the right tool here. You are already using ^ which means you're partway there. Use multiplication instead and you can avoid ambiguities. Consider:

100000 + (4^1 * 6^2 * 11^1 * 13^1)
100000 + (3^1 * 4^1 * 7^2 * 8^1)

This is nearly correct, but there are still ambiguities (for example 2^4 = 4^2). So, reassign new (prime!) values to each card:

Ace => 2
3 => 3
4 => 5
5 => 7
6 => 11
...

Then, you can multiply the special prime values of each card together to produce a unique value for every possible hand. Add in your value for type of hand (pair, full house, flush, etc) and use that. You may need to increase the magnitude of your hand type values so they stay out of the way of the card value composite.

回答3:

The highest value for a card will be 14, assuming you let non-face cards keep their value (2..10), then J=11, QK, A=14.

The purpose of the scoring would be to differentiate between hands in a tie-breaking scenario. That is, "pair" vs. "pair." If you detect a different hand configuration ("two pair"), that puts the scores into separate groups.

You should carefully consult your requirements. I suspect that at least for some hands, the participating cards are more important than non-participating cards. For example, does a pair of 4's with a 7-high beat a pair of 3's with a queen-high? (Is 4,4,7,3,2 > 3,3,Q,6,5?) The answer to this should determine an ordering for the cards in the hand.

Given you have 5 cards, and the values are < 16, convert each card to a hexadecimal digit: 2..10,JQKA => 2..ABCDE. Put the cards in order, as determined above. For example, 4,4,7,3,2 will probably become 4,4,7,3,2. Map those values to hex, and then to an integer value: "0x44732" -> 0x44732.

Let your combo scores be multiples of 0x100000, to ensure that no card configuration can promote a hand into a higher class, then add them up.