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:
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] Predicted 0 1 Actual 0 628189 55527 1 65699 250585