12,999,845 members (51,397 online)
alternative version

#### Stats

28.2K views
16 bookmarked
Posted 24 Apr 2011

# Poker In Four Hours

, 25 Apr 2011
 Rate this:
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

## 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

## 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

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

#### Part 2

• 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
};
};```

## You may also be interested in...

 View All Threads First Prev Next
 Using a bunch of Bit Hacks, you can achieve the same thing subskybox9-Nov-12 10:15 subskybox 9-Nov-12 10:15
 Re: Using a bunch of Bit Hacks, you can achieve the same thing Ilka Guigova20-Dec-12 18:06 Ilka Guigova 20-Dec-12 18:06
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Jun-17 19:30 Refresh 1

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

Web02 | 2.8.170624.1 | Last Updated 25 Apr 2011
Article Copyright 2011 by Ilka Guigova