Pig

Two players race to be the first to reach 100 points, taking turns with a single six-sided die. On your turn you roll as many times as you dare: each face from 2 to 6 adds to a running turn total, but rolling a 1 busts — the turn ends immediately and the whole turn total is lost. At any point you may instead hold, banking the turn total into your score and passing the dice. The first player to reach 100 wins, and banking is checked the instant it would win.

The tension is entirely in that one repeated decision: every extra roll risks the points already accumulated this turn, so Pig is the textbook example of a jeopardy, or push-your-luck, game.

The game is modelled as a two-player turn-based stochastic game — equivalently a Markov decision process (MDP), a state machine whose moves have known probabilities — on the state (myScore, oppScore, turnTotal) for the player to move, with the two actions {roll, hold}. Those three numbers are a sufficient statistic: nothing else in the history affects future play. Because exactly one player wins and both face identical rules, the game is zero-sum and symmetric, so a single value function V(i, j, k) — the probability the player to move eventually wins under optimal play by both — captures the whole game, with the handover encoded as 1 − V.

“Who wins under optimal play?” is then a probabilistic reachability question — the probability of eventually reaching a winning state — written in temporal logic as P=? [F win] and evaluated from the initial state (0, 0, 0). It is solved by value iteration: repeatedly applying the Bellman optimality backup (take the better of rolling and holding, weighting each die face at 1/6) until the values stop changing — exactly how probabilistic model checkers such as PRISM and Storm compute MDP reachability values. There is no discount factor, so convergence is not automatic; it holds because every state cedes the turn with positive probability (a bust, or the always-available hold), which makes the fresh-turn values over the finite 100×100 grid a finite monotone Bellman system with a unique fixpoint in [0,1].

The converged value is then certified, not just reported: recomputing the Bellman residual — the largest change any state would see under one more backup — yields exactly 0, the formal-methods analogue of a probabilistic model checker’s fixpoint check. A Monte-Carlo run agrees within sampling error, as a cross-check rather than the certificate.

Under optimal play by both players the first player has a real edge: a win probability of 0.530593 (the second player’s is 0.469407), an exact value-iteration fixpoint rather than a simulation estimate, reproducing the Neller–Presser (2004) optimal-play solution exactly. Value iteration over the ~100×100×100 state space converges in ~150 sweeps.

The optimal policy is not a flat threshold. The folk heuristic “hold at 20” is close at the start — the optimal threshold at 0–0 is 21 — but wrong in general: the boundary rises when you are behind (30 at 70–70), collapses to all-in when the opponent is one good turn from winning (at opponent 90, never hold short of the target), and drops early when you are close (at 90–0, bank small totals to lock the win). A truly-optimal player beats a hold-at-20 player head-to-head from both seats:

One subtlety: optimal self-play (0.5306 for the first player) is slightly below hold-at-20 self-play (0.5347) — these are different games. Optimality is defined against an optimal opponent; against a fixed hold-at-20 opponent the optimal best-responder is strictly favoured from both seats, which is the meaningful comparison.

Browse the other verified board games.