Three Card Poker Combinations

On the occasion where I wind up at a casino with some folks, Three Card Poker is a game we usually play. Crazy Four Poker is the favorite, of course, but there are usually only one or two tables. Three Card is a reasonable substitute because the house edge is about the same and the feel of the game is similar.

I often refer to Wizard of Odds for analysis on strategy, house edge, and practice programs. Their page on Three Card Poker has a rundown on the probabilities of each hand. When I looked at their analysis, I had assumed that they were assuming the odds were for the situation where it was one player vs the dealer. The question I had for myself was whether being in seat 2 would affect the second player's odds in any way. I was pretty sure it didn't (and it doesn't) but I wanted to try to answer the question for myself and replicate some of their analyses.

At first I thought I would buy the home version of Matlab for this project. A quick search of matlab speed vs c++ convinced me to stick with c++.

Analyzing the Ante bet

The brute force approach to this is pretty simple to implement. The first step is to generate all player hand combinations. There are \binom{52}{3} = 22100 combinations of three-card hands. For each of those hands, there are \binom{49}{3} = 18424 possible hands for the dealer. I generated these lists in the simplest way possible, just using three nested for loops. The loops iterate over cards in the deck by the index of their rank in the game. Cards 0-3 are the Aces of Spades, Diamonds, Clubs, and Hearts. Cards 48-51 are the deuces of the same suits. All parts of the analysis algorithms assume that all cards in a hand are sorted in increasing index and, thus, decreasing rank order.

Comparing hands can be done with a simple int16 comparison. A player can have one of the following hands, in order of increasing value: High Card, Pair, Flush, Straight, Set (aka Three of a Kind), Straight Flush. Some versions of Three Card Poker have a Mini Royal hand but I didn't take that into account here. Cards with the same class can still win or lose based on the ranks of the cards that compose the hand. Since there are 13 card ranks and 6 hand types (what I refer to as a Hand Class), we can use 4 bits for each card rank and 4 bits for the hand class. And since the cards in each hand are sorted in decreasing rank order, we can pack the ranks of cards 1, 2, 3 into bits 8-11, 4-7, and 0-3, respectively. The hand class is packed into bits 12-15. This forms a strongly-ordered series of poker hands which can be compared with the > or < operators to see which one wins or if they tie.

The payout (or loss) for any given showdown depends on three things: Whether the player wins, ties, or loses, which hand class the player got, and whether the dealer qualified or not (i.e. had a hand equal to or better than Q high). To calculate the player's overall odds, we have to determine the number of hands that fall into each showdown outcome. There are 17 total showdown outcomes. The player can lose, tie, win without dealer qualify, or win with dealer qualify. For each of those outcomes, the player can receive a bonus if they have a Straight, Set, or Straight Flush, or no bonus with a Flush or less. These two 4-element sets make 16 permutations, plus 1 for if the player folds.

To calculate house edge, we must examine every possible showdown, determine the result, and use the count of each result to find its probability and from that, its expected payout. There are \binom{52}{3}\binom{49}{3} = 407170400 showdowns to analyze.

My initial implementation took about 7.5 seconds to go through each of these showdowns. Not too bad, but that's mostly because I was using c++ on a new computer. If I was going to use this implementation to analyze the odds for seat2 I would have to do \binom{52}{3}\binom{49}{3}\binom{46}{3} = 6.1808467\cdot10^{12} iterations. This is approximately 31.6 hours, much longer than I was willing to let my computer run to find the answer. My method of optimizing this led to a mathematical exercise which ended up being the more interesting part of this project for me.

Decreasing Iteration Time

By far, the most time consuming part of the algorithm is calculating each hand class. The function that does it is an if-else sequence. There are perhaps some ways to do branchless calculation of hand class, but the better way to speed up processing is to reduce the number of times this function is called. We do have to calculate the hand class once for each of the 22,100 possible poker hands, but after that it isn't necessary to keep recalculating hand classes. Memoization would vastly increase the speed of the algorithm. The difficulty is that each player hand corresponds to a different set of 18,424 dealer hands. We have to be able to take a dealer hand and turn that into an index from 0-22,099 so we can get its pre-calculated class.

If the hands were generated in a grid this would be easy. But it's more complex than that because the hands are an ordered combination. For each iteration of the outermost for loop, the number of inner combinations decreases:

void ThreeCard_GeneratePlayerCombos (ThreeCardHand * destArray) {

    ThreeCardHand * ptr = destArray;
    for (int a = 0; a < 50; ++a) {
        for (int b = a + 1; b < 51; ++b) {
            for (int c = b + 1; c < 52; ++c) {
                *(ptr++) = ThreeCardHand(a, b, c);
            }
        }
    }

}

To find the combination index of a given ordered combination \langle a, b, c \rangle, we have to calculate how many iterations it took to get to a, then given a, how many iterations it took to get to b, and likewise for c. We'll call these N_{a}, N_{b}, N_{c}. This means doing summations. Whee.

For a given value of a, the number of iterations of the inner two loops is a two-item combination of the number of iterations of the middle loop. Thus:

a_{0} = 0\\a_{1} = \binom{51}{2}\\a_{2} = \binom{50}{2}\\a_{n} = \binom{52 - n}{2}

Finding N_{a} means adding up each combination of a_{n}

N_{a}=\sum_{n=1}^{a}\binom{52-a}{2}
N_{a}=\sum_{n=1}^{a}\frac{(52-a)!}{(52-a-2)!2}
N_{a}=\sum_{n=1}^{a}\frac{(52-a)(51-a)(50-a)\cdots}{((50-a)\cdots)2!}
N_{a}=\sum_{n=1}^{a}\frac{(52-a)(51-a)}{2}
N_{a}=\sum_{n=1}^{a}\frac{1}{2}(52\cdot51 - 103a + a^2)
N_{a}=\frac{1}{2}\left(\sum_{n=1}^{a}2652 - \sum_{n=1}^{a}103a + \sum_{n=1}^{a}a^2\right)

Solving each separately:

\sum_{n=1}^{a}2652
\Rightarrow2652a

\sum_{n=1}^{a}103n
103\left(a + (a-1) + \cdots + 1\right)
103(\frac{a(a+1)}{2})
\Rightarrow103(\frac{a^2+a}{2})

\sum_{n=1}^{a}a^2
a^2 + (a-1)^2 + \cdots + 1^2
\Rightarrow\frac{a^3}{3}+\frac{a^2}{2}+\frac{a}{6}

N_{a} = \frac{1}{2}\left(2652a-103(\frac{a^2+a}{2}) + \frac{a^3}{3}+\frac{a^2}{2}+\frac{a}{6}\right)

Credit to Ken Ward's Page on helping me re-learn something I forgot from 9th grade. I had no idea how to do a summation of squares.

Now that we know N_{a} we need N_{b}. It's simpler overall but there is the nuance that the value of N_{b} changes based on the value of a. For any given value of b the number of iterations of the innermost loop is 50-(b-2)=52-b.

a = 0, b_{1} = 0, b_{2} = 50, b_{3} = 49, b_{n} = 52 - n, N_{b}=\sum_{n=2}^{b}52-n
a = 1, b_{1} = 0, b_{2} = 0, b_{3} = 49, b_{4} = 58, b_{n} = 52 - n, N_{b}=\sum_{n=3}^{b}52-n

Note that the value of each b subscript doesn't change as a changes. But it does determine at which point values become nonzero. This means a doesn't determine the value of the b subscript, but the value at which we begin our summation for N_{b}.

given 'a',b_{a+1}=0,b_{a+2}=52-(a+2),b_{a+3}=52-(a+3),b_{n}=52-n
N_{b}=\sum_{n=a+2}^{b}52-n
N_{b}=\sum_{n=a+2}^{b}52 - \sum_{n=a+2}^{b}n

Again, solve each separately.

\sum_{n=a+2}^{b}52
\Rightarrow52(b-a-1)

For the second part, we have a simple natural number sum, but it doesn't go all the way to one. We can handle this in a way I think is similar to how we handle dividing factorials, by just removing the part of the set that is eliminated. The sum of natural numbers from b down to a+2 is the full sum with the part from a+1 down removed.

\sum_{n=a+2}^{b}b
\sum_{n=1}^{b}n-\sum_{n=1}^{a+1}n
\frac{b^2+b}{2} - \frac{(a+1)(a+2)}{2}
\Rightarrow\frac{1}{2}\left(b^2+b - a^2 - 3a - 2\right)

N_{b}=52(b-a-1)-\frac{1}{2}\left(b^2+b - a^2 - 3a - 2\right)

Fortunately, N_{c} is easy. c comes from the innermost loop which is just a linear count so we really don't have to solve for anything here. c counts up starting at b+1, so

c_{n}=N_{c}=c-b-1.

Now we can put all our pieces together to get our equation for the index of an ordered hand combination!

I=N_{a}+N_{b}+N_{c}
I=\frac{1}{2}\left(2652a-103(\frac{n^2+n}{2}) + \frac{a^3}{3}+\frac{a^2}{2}+\frac{a}{6}\right)+52(b-a-1)-\frac{1}{2}\left(b^2+b - a^2 - 3a - 2\right)+\left(c-b-1\right)

After all that, we can now improve our algorithm by only generating the combination index of each of the 18,424 dealer hands we examine per player hand iteration. That index allows us to look up our pre-calculated hand class for that hand instead of having to re-calculate the hand class. After updating my algorithm the run time dropped to about 1.5 seconds. Not a bad improvement.

Concluding

At a 1.5 second time per 1-ply analysis, that meant the runtime I could expect if I wanted to do a 2-ply analysis dropped to only 6.325 hours! I could do it overnight! But, I ended up not doing that. While I was doing the other parts of the project, I reasoned myself out of believing that there was any way the odds of any player getting any hand wouldn't be the same.

For any three cards a b c, the number of dealer sets this hand doesnt appear in is the number of hands with just a, b, or c, plus the number of hands with two of those cards, plus the one hand that has all these. Mathematically, this is 3\binom{49}{2}+3\binom{49}{1}+\binom{3}{3} The combinations are of 49 because they're counting hands that only have a, b, or c exclusively, so we have to remove all three of them from the pool of 52. This quantity is 3676, which just so happens to be 22100 - 18424.

Since this equation is the same regardless of which cards a b and c represent, I figured that meant each dealer hand appeared in the same number of player hand combinations. I wrote a basic loop to brute force this calculation and it did indeed turn out that the dealer got every hand exactly 18424 times. This math would extend to the two ply scenario, so I feel like there's no reason to spend 6.5 hours brute forcing those calculations to make sure. The interesting part to me was the index calculation above, which was a totally unexpected thing to come out of this project. Maybe not a huge deal but neat nonetheless.

One other thing I could have done is do a calculation of the optimal hand on which to fold. My strategy for this, I think, would have been designating a fold hand class for each run of the algorithm, and then do a binary search through the array of 22100 possible hand classes to find the hand that maximized return. However I don't think I'll delve any further into Three Card (or any-Card) Poker stats for a while. I want to get back to some hobby game projects.

Leave a Reply

Your email address will not be published. Required fields are marked *