Click here to Skip to main content
Click here to Skip to main content

Poker In Four Hours

, 25 Apr 2011
Rate this:
Please Sign up or sign in to vote.
Assign a value to a hand of cards that reflects its strength/score according to the standard poker hand ranking system and avoid the need to sort, compare, and lookup individual hands

Table of Contents

Introduction

My only exposure to the game of poker has been a few hours in the last couple of weeks reading through the various hand ranking rules. It seems that the challenge of quickly finding the winner in a game is simple and yet elusive. Thus, the idea of producing a mapping between a poker hand and a small bounded entity, I thought, is worth some investigation. The code behind this article is a proof of concept of one such computational procedure.

Background

Originally, the code snippet was created in response to a 4 hour software developer test. It comprised the following task:

Implement

A library (in the programming language of your choice) which evaluates who are the winner(s) among several 5 card poker hands (http://en.wikipedia.org/wiki/List_of_poker_hands). Note for this project that you only need to implement a subset of the regular poker hands:

  • Flush
  • Three of a Kind
  • Two of a Kind
  • High Card

Input

Collection of players in the showdown: Player Name and 5 Cards (each specifying the number and suit of the card) - e.g.,

  • Joe, 3H, 4H, 5H, 6H, 8H
  • Bob, 3C, 3D, 3S, 8C, 10D
  • Sally, AC, 10C, 5C, 2S, 2C

Output

Collection of winning players (more than one in case of a tie) - e.g.,

  • Joe

Please state any assumptions you've made.

Implementation

Since the initial completion of the task, the implementation was extended to support the full set of standard poker hands.

JavaScript was chosen for its flexibility and ease of use.

Assumptions

  1. The highest ranking hand (as per the standard poker hand ranking system, [^]) is the winning hand. There is always at least one winner.
  2. The number of hands is a positive random integer.
  3. The number of cards in a hand is a positive random integer less than 13. The number of cards in a hand does not really matter but it makes sense that it would not exceed 13.
  4. The cards in a hand come from one deck. The process can be modified to support multiple decks but it will lose some of its transparency.
  5. Each card is represented by a 2-letter word, where the 1st letter identifies the rank (i.e., is in the set [1..10, J, Q, K, A]) and the 2nd letter identifies the suite (i.e., is in the set [D, H, C, S])
  6. The input contains, per row, the name of the player and the set of cards that form the player's hand where entities are comma-separated. Multiple rows indicated multiple players. No checks are added to verify that the players are unique, have the same number of cards, and use one deck of cards.
  7. The player name does not contain spaces; if it does, they will not be present in the output.

Algorithm

The objective is to assign a value to a hand of cards that reflects its strength/score according to the standard poker hand ranking system and avoid the need to sort, compare, and lookup individual hands. The winner of a game is the player with the highest score.

In order to compute the score, we view each hand as a two dimensional matrix. The sum across the columns gives us enough information to deduce whether we have four of a kind, full house, three of a kind, two pair, or one pair. The sum across the rows gives us enough information to deduce whether we have flush, straight, or straight flush. The last row also gives away the high card and the kickers.

For example, here is how 2H, 9D, 3S, 2C, QD looks like in such a matrix:

 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 |  | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|  |
 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 | D|  |  |  |  |  |  |  |  |  | 1|  |  | 1|  |  | 0|
 | H|  |  | 1|  |  |  |  |  |  |  |  |  |  |  |  | 0|
 | C|  |  | 1|  |  |  |  |  |  |  |  |  |  |  |  | 0| >-- col => cards of suite (flush, [0,5+])
 | S|  |  |  | 1|  |  |  |  |  |  |  |  |  |  |  | 0|
 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
 |  |  |  | 2| 1|  |  |  |  |  | 1|  |  | 1|  |  | 0| >-- row=>cards of rank(N of a kind, [1..4+])
 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                                                   ^----cell =>cards in sequence(straight, [0,5+])

In this case, we have a pair with 3 kickers (no straight, no flush).

We compute from the left to the right which guarantees us that we always use the best available cards for the score and that the algorithm works just as well for 7-card hands, for instance.

This approach frees us from sorting cards, comparing hands, or performing lookups. It uses fixed memory bound by the sparse 15 x 4 matrix. For a single hand, it runs in constant time, O(1), needed to sum across the rows and the columns. If a game contains n hands, it will take O(n) time to score them all.

The trick is in assigning a score that is 'unique'. Consider the following formulas:

 Hand Categories | Big Endian | Little Endian
 ----------------|------------+--------------------
 Straight Flush  |   s&f -> 8 | kickers
 Four Of A Kind  |    k4 -> 7 | k4
 Full House      | p1&k3 -> 6 | p1 + k3*(10^2) 
 Flush           |     f -> 5 | kickers
 Straight        |     s -> 4 | kickers
 Three Of A Kind |    k3 -> 3 | k3
 Two Pair        |    p2 -> 2 | p2 + p1*(10^2)
 One Pair        |    p1 -> 1 | p1
 High Card       |       -> 0 | kickers    

where:

  • kickers = sum(ri*(10^(-15 + i))) where ri is the rank of the i-th card with cardinality 1 which plays
  • f = number of cards of the same suite if 5 or more, 0 otherwise
  • s = number of cards in sequence if 5 or more, 0 otherwise
  • k4 = r*(10^-4) where r is the highest rank of a card with cardinality 4
  • k3 = r*(10^-4) where r is the highest rank of a card with cardinality 3
  • p2 = r*(10^-4) where r is the second highest rank of a card with cardinality 2
  • p1 = r*(10^-4) where r is the highest rank of a card with cardinality 2

then the score = (category || 0) * (category's big endian + category's little endian) + kickers.

Examples:

Here is how 2H, 9D, 3S, 2C, QD (One Pair) score is computed:

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| D|  |  |  |  |  |  |  |  |  | 1|  |  | 1|  |  | 0|
| H|  |  | 1|  |  |  |  |  |  |  |  |  |  |  |  | 0|
| C|  |  | 1|  |  |  |  |  |  |  |  |  |  |  |  | 0|
| S|  |  |  | 1|  |  |  |  |  |  |  |  |  |  |  | 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  | 2| 1|  |  |  |  |  | 1|  |  | 1|  |  | 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    
Hand Categories | Big Endian | Little Endian    | Result
----------------|------------+------------------|-------------
Straight Flush  |   s&f -> 8 | kickers          | 0  
Four Of A Kind  |    k4 -> 7 | k4               | 0
Full House      | p1&k3 -> 6 | p1 + k3*(10^2)   | 0 
Flush           |     f -> 5 | kickers          | 3*(10^-14) + 9*(10^-13) + 12*(10^-12)
Straight        |     s -> 4 | kickers          | 0
Three Of A Kind |    k3 -> 3 | k3               | 0
Two Pair        |    p2 -> 2 | p2 + p1*(10^2)   | 0
One Pair        |    p1 -> 1 | p1               | 0.0002 = 2*(10^-4)
High Card       |       -> 0 | kickers          | 1.2930000000000001e-11    
    
score = 1.0002000000129 = (p1) * (1 + 0.0002) + 1.2930000000000001e-11    

Here is how 10S, 10C, 10H, 4D, 4C (Full House) score is computed:

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| D|  |  |  |  | 1|  |  |  |  |  |  |  |  |  |  | 0|
| H|  |  |  |  |  |  |  |  |  |  | 1|  |  |  |  | 0|
| C|  |  |  |  | 1|  |  |  |  |  | 1|  |  |  |  | 0|
| S|  |  |  |  |  |  |  |  |  |  | 1|  |  |  |  | 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  | 2|  |  |  |  |  | 3|  |  |  |  | 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Hand Categories | Big Endian | Little Endian    | Result
----------------|------------+------------------|-------------
Straight Flush  |   s&f -> 8 | kickers          | 0  
Four Of A Kind  |    k4 -> 7 | k4               | 0
Full House      | p1&k3 -> 6 | p1 + k3*(10^2)   | 0.1004 = 0.0004 + 0.001(10^2)
Flush           |     f -> 5 | kickers          | 0
Straight        |     s -> 4 | kickers          | 0
Three Of A Kind |    k3 -> 3 | k3               | 0.001 = 10(10^-4)
Two Pair        |    p2 -> 2 | p2 + p1*(10^2)   | 0
One Pair        |    p1 -> 1 | p1               | 0.0004 = 4*(10^-4)
High Card       |       -> 0 | kickers          | 0    

score = 6.1004 = (p1&k3) * (6 + 0.1004) + 0    

Note that it is possible to restore the hand from the score.

Performance

In Chrome (10.0.648.205, AMD Turion, 1.6GHz, 512KB L2, 2GB DDR2), a single hand evaluation takes ~1ms.

10 ->    ~1 ms
100 ->    ~6 ms
1000 ->   ~60 ms
10000 ->  ~600 ms 
100000 -> ~6000 ms    

To run it yourself, open the attached HTML file in a browser with JavaScript enabled.

It is likely that the same implementation in another language will yield better results.

Challenges

  • Understanding and verifying the various poker hand ranking rules
  • Ensuring min/max value per category without overlap -> powers of 10, big/little endian
  • Calculation of kickers vs high card -> powers of 10, cardinality
  • Applying Ace as 1 or 14 in straights -> manual value reset

Alternative Approaches (cf. See Also)

  • Use of base 13 computations
  • Use of prime numbers where the product of two prime numbers is a 'unique' number

Part 2

  • Add a conclusion
  • Come up with a way to incorporate probabilities
  • Implement in another language (Haskell?) to see whether the overall performance is better

Code

var evalHand = function(input){
    if (!input) return;

    input = input.replace(/\s+/g, '').replace(/,[Jj]/g, ',11').replace
	(/,[Qq]/g, ',12').replace(/,[Kk]/g, ',13').replace(/,
	[Aa]/g, ',14').toUpperCase().split(',');

    var hand = {D: [], H: [], C: [], S:[]};
    for (var i = 1, len = input.length; i < len; i++)
    {
        input[i] && (hand[input[i].slice(input[i].length - 1)]
	[input[i].slice(0, input[i].length - 1)] = 1); 
    }

    var card = function(suite, rank){return hand[suite][rank] || 0};
    var cards = function(rank){ return card('D', rank) + card('H', rank) + 
	card('C', rank) + card('S', rank); };
    var kickers = function(idx){ // http://en.wikipedia.org/wiki/Kicker_(poker)        
        idx = idx || -15; 
        var notplayed = Math.max(input.length - 1/*player input*/ - 5, 0);
        return function(all, cardinality, rank) {
            return (all || 0) + (((cardinality == 1) && (notplayed-- <= 0)) ? 
		rank * Math.pow(10, ++idx) : 0);
        };
    }();
   
    var tag = function(a, b, always) {a = a || 0; b = Math.min(b || 0, 1); 
	return (b || always) ? a + b : 0};
    var reset = function(a) { return (a < 5) ? 0 : a};

    var cardsofrank = []; 
    var hc = 0;         // high card
    var k4 = 0;         // four of a kind 
    var k3 = 0;         // three of a kind
    var p2 = 0;         // two pair / two one pairs
    var p1 = 0;         // one pair / two of a kind
    var k = 0;          // kickers
    var sd = cards(14); // straight discriminant: count A as 1 or 14
    for (var i = 2; i < 15; i++)
    {
        cardsofrank[i] = cards(i);
        hc = (cardsofrank[i]) ? i * Math.pow(10, -4) : hc;
        k4 = (cardsofrank[i] === 4) ? hc : k4;
        k3 = (cardsofrank[i] === 3) ? hc : k3;
        p2 = (cardsofrank[i] === 2) ? p1 : p2;
        p1 = (cardsofrank[i] === 2) ? hc : p1; 
        k = kickers(k, cardsofrank[i], i);
        sd = tag(sd, cardsofrank[i], sd >= 5);
    };
    var s = reset(sd); // straight

    if (s && cards(14) && !cards(13)) 
	{ k = k - 14 * Math.pow(10, sd); } // adjust for A as 1 or 14

    var cardsofsuite = {D: 0, H: 0, C: 0, S: 0};
    for (var i = 2; i < 15; i++)
    {
        cardsofsuite['D'] = tag(cardsofsuite['D'], card('D', i), true);
        cardsofsuite['H'] = tag(cardsofsuite['H'], card('H', i), true);
        cardsofsuite['C'] = tag(cardsofsuite['C'], card('C', i), true);
        cardsofsuite['S'] = tag(cardsofsuite['S'], card('S', i), true);
    }
    var f = reset(cardsofsuite['D']) + reset(cardsofsuite['H']) + 
	reset(cardsofsuite['C']) + reset(cardsofsuite['S']);  // flush

    var score = function(cond, bigendian, littleendian) 
	{ return (cond ? 1 : 0) * (bigendian + littleendian); }; 

    return {
        player: input[0],  
        score: (score(s && f, 8, k)                              // straightflush
                || score(k4, 7, k4)                              // fourofakind
                || score(p1 && k3, 6, p1 + k3 * Math.pow(10, 2)) // fullhouse
                || score(f, 5, k)                                // flush
                || score(s, 4, k)                                // straight
                || score(k3, 3, k3)                              // threeofakind
                || score(p2, 2, p2 + p1 * Math.pow(10, 2))       // twopair
                || score(p1, 1, p1))                             // onepair
            + score(hc, 0, k)                                    // highcard - tie breaker
    };
};

See Also

History

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Ilka Guigova
Software Developer
Canada Canada

Comments and Discussions

 
QuestionUsing a bunch of Bit Hacks, you can achieve the same thing [modified] Pinmembersubskybox9-Nov-12 10:15 
I wrote one in JavaScript using only bit manipulations:
hands=["4 of a Kind", "Straight Flush", "Straight", "Flush", "High Card",
       "1 Pair", "2 Pair", "Royal Flush", "3 of a Kind", "Full House" ];
var A=14, K=13, Q=12, J=11, _ = { "♠":1, "♣":2, "♥":4, "♦":8 };
 
//Calculates the Rank of a 5 card Poker hand using bit manipulations.
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);
 
 document.write("Hand: "+hands[v]+((s == 0x403c)?" (Ace low)":"")+"
");
}
 
//Royal Flush   
rankPokerHand( [ 10, J, Q, K, A],  [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] );
http://jsfiddle.net/subskybox/r4mSF/[^]

modified 18-Mar-13 16:02pm.

AnswerRe: Using a bunch of Bit Hacks, you can achieve the same thing PinmemberIlka Guigova20-Dec-12 18:06 
GeneralDrops of HCG PinmemberEmilyfres guez24-Apr-11 21:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140821.2 | Last Updated 25 Apr 2011
Article Copyright 2011 by Ilka Guigova
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid