The game's object is to be the first player, rolling a die, to reach a total of 100 points. On each turn, a player rolls a die as many times as he or she wishes, totaling the score of the rolls until the player decides to end the turn and pass the die to his or her opponent.

However, if the player rolls a 1, he or she immediately loses all the points accumulated during that turn, and the die passes to the other player. The big decision at any point during a turn is whether to roll or stop (hold). In general, it doesn't pay to be greedy.

A roll is successful if any one of 2, 3, 4, 5, or 6 comes up. On average, you gain four points per roll. Your chance of rolling 1 is just one in six. So, it seems to make sense to continue rolling the die until you accumulate 20 points during a turn. If you stop then, the odds would be in your favor.

However, this isn't the full story. There are circumstances when the "hold at 20" strategy isn't optimal.

Consider the following scenario. Your opponent has a score of 99 and would likely win in the next turn. You have a score of 78, and you've just reached 20 during your turn, for a new total of 98. In this case, your probability of winning the game with one additional roll is higher than the probability of winning if you ended the turn and allowed the other player to roll.

It was such subtleties that got computer scientist Todd W. Neller to analyze the two-player game in detail and find a strategy for true optimal play. His key insight was the understanding that playing to maximize points for a single turn isn't the same thing as playing to win.

Neller wrote a computer program to compute all the relevant probabilities, using a technique known as value iteration, and colleague Clif Presser created dramatic visualizations of the results. See "The Game of Pig."

The results show that the "hold at 20" strategy comes close to representing optimal play only when both players have low scores. When either player has a high score, it's best to try to win each turn.

Amazingly, between these extremes, there's a great deal of variability in the best strategy to follow in any given situation. When the results are plotted in three dimensions, with player 1's score on one axis, player 2's score on the second axis, and the turn total on the third axis, the surface representing the roll/hold boundary has a remarkably intricate, wavy structure (below).

Indeed, the cross section representing the roll/hold boundary when your opponent has a given score is surprisingly irregular (below). For example, suppose your opponent's score is 30. If you're playing optimally and have a low score, you have to take greater risks to catch up. If you have a high score, it's better to play much more conservatively.

In general, as shown by the irregular landscape of the roll/hold boundary for Pig, details of optimal play can be far from intuitive.

Interestingly, if both players play optimally, the starting player wins 53 percent of the time. If the first player plays optimally and the second uses a "hold at 20" strategy, the optimal player wins 58.7 percent of the time. When the "hold at 20" player goes first, that player wins 47.8 percent of the time.

Pig has many variants, including versions that require two dice, somewhat different rules, or more than two players. Each one has its own peculiarities, and each is worthy of analysis. See visualizations of Neller's analyses of some of these versions.

"Seeing the 'landscape' [of optimal play] is like seeing the surface of a distant planet sharply for the first time having previously seen only fuzzy images," Neller and Presser concluded in the journal article "Optimal Play of the Dice Game Pig" describing their results. "If intuition is like seeing a distant planet with the naked eye, and a simplistic, approximate analysis is like seeing with a telescope, then applying the tools of mathematics is like landing on the planet and sending pictures home."

*Originally posted May 31, 2004*

## No comments:

Post a Comment