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

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

- The highest ranking hand (as per the standard poker hand ranking system, [^]) is the winning hand. There is always at least one winner.
- The number of hands is a positive random integer.
- 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.
- 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.
- 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]`

) - 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**. - 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){
idx = idx || -15;
var notplayed = Math.max(input.length - 1 - 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;
var k4 = 0;
var k3 = 0;
var p2 = 0;
var p1 = 0;
var k = 0;
var sd = cards(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);
if (s && cards(14) && !cards(13))
{ k = k - 14 * Math.pow(10, sd); }
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']);
var score = function(cond, bigendian, littleendian)
{ return (cond ? 1 : 0) * (bigendian + littleendian); };
return {
player: input[0],
score: (score(s && f, 8, k)
|| score(k4, 7, k4)
|| score(p1 && k3, 6, p1 + k3 * Math.pow(10, 2))
|| score(f, 5, k)
|| score(s, 4, k)
|| score(k3, 3, k3)
|| score(p2, 2, p2 + p1 * Math.pow(10, 2))
|| score(p1, 1, p1))
+ score(hc, 0, k)
};
};

## See Also

## History