Optimal Pass the Pigs Strategy (Part Two)

Still migrating old posts due to travel. Next post will be fresh content!

In a previous post, we learned that if you want to maximize your score on any individual turn of a game of "Pass the Pigs," you should always roll when there's less than 22.5 points in your hand, and hold when there's more than 22.5 points in your hand. (If you've never heard of "Pass the Pigs," the rules are explained in the prior post.)

However, we also concluded that that's not an effective strategy for winning the game as a whole. If you have a score of 0 and your opponent has a score of 99, for example, it would be really silly to stop rolling at 23 points just because the "22.5 rule" says to. So what's a person to do? How do you play effectively? Today, we'll generate a strategy that can help you make an optimal move in any situation. (Hint: you'll need to do a lot of math.)

Modeling the Game

Let's start with coming up with a basic model for a game of Pass the Pigs. There are really only 3 variables in the game... there's Player 1's score, Player 2's score, and the amount of points that the current player has in their hand. All of these variables can take on any value from 0 to 99, because if any one of them is 100 or higher, the game is over and somebody has won. There are therefore exactly 1,000,000 possible states of a 2-person game of Pass the Pigs - 100 possible states of Player 1's points times 100 possible states of Player 2's points times 100 possible states of the current player's hand. To a human, 1,000,000 is a lot of potential game states, but for a computer program, it's really not that much to keep track of.

The crucial question of the game is "Do I hold or do I roll." So, we need to answer that question for each of the million possible game states. If Player 1 has 72 points, Player 2 has 81 points, and Player 1 has 25 points in his hand... does Player 1 roll or does Player 1 hold? If we can answer this question accurately for every single game state, then we can play a perfect game!

Answering the "hold or roll" question for any given game state is fairly easy once you realize that the probability of winning from every game state is dependent on the probability of winning from all of the game states you could get to if you hold or roll. Remember from last time that every time you roll the pigs, the probabilities of getting a certain number of points on any given roll are as follows:

Pig Out! 21.080%
1 21.301%
5 40.622%
10 7.848%
15 2.783%
20 6.229%
25 0.042%
40 0.090%
60 0.005%

Let's start with rolling. Let's imagine Player 1 has 10 points, Player 2 has 10 points, and Player 1 has 10 points in his hand currently. If Player 1 rolls, there's a 21% chance that Player 1 will gain 1 point and move the game to a new state - 10 points for P1, 10 points for P2, 11 points in P1's hand. There's a 41% chance of getting to a different state - 10 points for P1, 10 points for P2, 15 points in P1's hand. You can finish the logic of adding all the rest of those probabilities in...

But there's also a chance that Player 1 will pig out if he rolls. If that happens, his probability of winning is just 100% minus the probability that his opponent wins given the game state that would result if it became his opponent's turn.

So, Player 1's probability of winning if he chooses to roll from any given game state is given by an easy formula:

Win Probability (Roll) =
.21 * (1 - Win Probability (P2, P1, 0))
+.21 * Win Probability (P1, P2, Hand+1)
+.41 * Win Probability (P1, P2, Hand+5)
+.08 * Win Probability (P1, P2, Hand+10)
+.00005 * Win Probability (P1, P2, Hand+60)

OK... but what if Player 1 chooses to hold? Well, that's even easier. It works the same way as pigging out, except he gets to add what's in his hand to his score. Like so:

Win Probability (Hold) = 1 - Win Probability (P2, P1 + Hand, 0)

Obviously, with these formulas in hand, we can make some easy decisions. If the probability of winning is greater for rolling then holding, you should roll. Easy peasy. And the probability of winning from any given state is simply the greater of the win probabilities for rolling or holding, since a rational person would always choose the better odds.

But how do we know what all those probabilities are? If all of the probabilities are based on each other and we don't know what any of them are, how in the world can we figure all of this out?

Solving the System

It's actually not quite true that we don't know any of the probabilities. We do know some probabilities - if Player 1 has a score of 80 and 23 points in his hand, we actually know his probability of winning is 100% - he has already won! Because the probabilities of winning are known for the states where a person has already won, an iterative estimation process on the system of probabilities will eventually converge, as helpfully pointed out by this paper on a very similar dice game. "Iterative? Convergence?," you say. "What does all of that mean?"

Essentially, this means that we can start a process of calculating the probabilities of winning from each state. For states where the player has already won, we'll start out by calling their win probabilities 100%. For everything else, we'll just pick arbitrary values - say, 50%. If we keep running our calculations over and over, using the output of the last calculations as the input for the new calculations, eventually our probabilities will "converge" - they'll get closer and closer to the real values until they're so close that it's practically meaningless to keep doing the calculations. Once the values aren't changing very much, there's no need to keep doing the calculations. The answers are "close enough."

Here's a pretty simple Vanilla JS implementation of this idea. It creates a 3-dimensional array to track game states, initializes the win probability of every game state to 50%, then loops through and keeps calculating win percentages over and over again until they're no longer changing by more than 1/10th of 1%. Doesn't take too long to find the answers!

How to Win

OK, so now we have all of the data necessary to actually play a perfect game of Pass the Pigs. What do we do with it? Well, I've created a simple online game that allows users to play against a perfect AI. In the interest of not being contacted by lawyers, I've stopped short of making this game fun to play... it illustrates the concept, but it's not exactly pretty. You can check it out (code and all) on JS Fiddle.

Of course, that's not very helpful for people sitting around playing with a friend. I suppose there's several solutions for those people... you could do all of the calculations ahead of time, print them out, and bring them with you in a massive reference book every time you played Pass the Pigs. But that might be a little annoying. You could make a simple app to let you look them up on your smart phone.

Or, perhaps, with a little bit of help from statistics, you could generate a "back of the envelope" formula that would tell you whether to hold or roll in a given situation. I haven't perfected that one yet, but early results are promising... As the GRETL results below show, a brutally simple binary logistic regression that models whether you should hold or roll based on your score, your opponent's score, and the number of points in your hand can suggest the right choice in nearly 90% of cases. With a little work, I'm sure somebody could generate a heuristic that could be applied in your head and that could drastically improve your chances of winning. If you've got any ideas, leave a comment!

Model 9: Logit, using observations 1-1000000
Dependent variable: Roll
Standard errors based on Hessian

             coefficient   std. error      z      p-value
  const       3.38377      0.0120981      279.7   0.0000  ***
  Opp         0.0482387    0.000153057    315.2   0.0000  ***
  Hand       −0.109485     0.000240778   −454.7   0.0000  ***
  You        −0.0505809    0.000155820   −324.6   0.0000  ***

Mean dependent var   0.316284   S.D. dependent var   0.465025
McFadden R-squared   0.582682   Adjusted R-squared   0.582675
Log-likelihood      −260422.0   Akaike criterion     520852.0
Schwarz criterion    520899.2   Hannan-Quinn         520865.0

Number of cases 'correctly predicted' = 878774 (87.9%)
f(beta'x) at mean of independent vars = 0.093
Likelihood ratio test: Chi-square(3) = 727229 [0.0000]

                 0        1
  Actual 0  628189    55527
         1   65699   250585

3 Responses

  1. Josh Brown Kramer March 19, 2016 / 8:46 pm

    I played Pass The Pigs with my son this morning and was thinking about doing almost exactly this same thing. I’ll point out that you can do the probability calculation using dynamic programming by setting the entries where the sum of i and k is >= 100 to 1, and then doing the loops backward. I don’t know how many iterations you need to get convergence, but you get to eliminate the while loop.

    As far as keeping track of the optimal strategy, I kind of figured it would almost always be to hold on 23 or more with some wrinkle near the endgame. If we could make a data structure that keeps track of the optimal threshold in each case, that would be elightening. It’s a 100 x 100 matrix. It might be small enough to visualize effectively.

  2. Josh Brown Kramer March 20, 2016 / 12:46 pm

    A followup on yesterday’s note:

    1) The dynamic programming solution I suggested doesn’t work, primarily because of the term j,i,0 term, which thwarts all my attempts at doing a clever order that ensures that all of the terms have already been computed. I sort of hoped that you could use some symmetry, or reduce to the case i == j, but none of that seems to work out. Oh well, you have a solution.

    2) I created a a table which tells you the smallest score in hand you should stay on in every score combination. It is at http://brownkramer.com/pp.html. Some things really struck me about this : 1) the strategy is NOT to stop at 23, even when both players have 0 (in that case it’s 24). 2) The strategy does not seem to be easy to memorize. The level curves (sets of scores where the threshold is a fixed constant) have more complex shapes than I would have expected (they look like parabolas or hyperbolas). 3) The threshold is not monotonic. For instance, if you have 42 and your opponent has 0, you should stop if you have 18 points in hand. On the other hand, if you have 43 point, you should wait until you have 20 points before stopping! This non-monotonicity made me worried that the threshold concept isn’t even right. That is, maybe there is a score (i,j) where if you get k points you should stop, but if you get some score, l > k you should keep going. I checked, and indeed there are situations like that. For instance, if you have 0 points and your opponent has 54, you want to stop if you hit 98 points, but not if you hit 99!

    From these observations, there are a couple ideas I have for making an easy-to-remember approximation of the optimal algorithm. I think that you want to keep yourself on pace to beat your opponent assuming they are chugging along at 23 points per turn. I also think that if you put yourself within easy striking distance of winning (and maybe more generally, if you are in easy striking distance of reducing your likely number of rolls to win), you have incentive to hold out a little longer.

    • daynebatten March 21, 2016 / 3:02 pm

      Thanks for the thoughts. It’s especially interesting that the threshold isn’t monotonic (that hadn’t even occurred to me, but it makes perfect sense)…

      Let me know if you find a good mental model for getting an edge on strategy! I don’t really play Pass the Pigs much, but it would be interesting to see how much being able to play relatively close to perfectly would impact your odds of winning against the average player.

      Incidentally, as I’ve tried to play the perfect computer player I built (linked above), I’ve found that I still win a reasonably good portion of the time, implying that the game is mostly driven by chance.

Leave a Reply

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