Poker In Four Hours

• Download source - 36.01 KB
• Download source code (latest version)

Table of Contents

• Introduction
• Background
• Implementation
  • Assumptions
  • Algorithm
  • Examples
  • Performance
  • Challenges
  • Code
• See Also
• History

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:

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 1^st letter identifies the rank (i.e., is in the set [1..10, J, Q, K, A]) and the 2^nd 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

• Strategy Pattern
• Cactus Kev's Poker Hand Evaluator
• Nick's Algorithm for evaluating poker hands
• Poker Stove
• Probabilities in poker
• More Texas Holdem Analysis in C#

History

• Latest revision
• 04/24/2011: First published