Optimal Play of the Dice Game Pig

摘要

The simple game of Pig gives rise to a complex optimal policy. A first look at the problem from a betting perspective yields a simple "hold at 20" policy, but this policy maximizes expected points per turn rather than the probability of winning. The optimal policy is instead derived by solving for the probability of winning for every possible game state. This amounts to finding the intersection of folded hyperplanes within a hypercube; the method of value iteration converges and provides a solution. The interested reader may play an optimal computer opponent, view visualizations of the optimal policy, and learn more about Pig at http://cs.gettysburg.edu/proj ects/pig. Surprising in its topographical beauty, this optimal policy is approximated well by the "hold at 20" policy only when both players have low scores. In the race to 100 points, optimal play deviates significantly from this policy and is far from intuitive in its details. Seeing the "landscape" of this policy is like seeing the surface of a distant planet sharply for the first time having previously seen only fuzzy images. If intuition is like seeing a distant planet with the naked eye, and a simplistic, approximate analysis is like seeing it with a telescope, then applying the tools of mathematics is like landing on the planet and sending pictures home. We will forever be surprised by what we see!