Yahtzee

This solver computes optimal dice-keeping decisions using dynamic programming with precomputed expected values. The approach models Yahtzee as a Markov Decision Process and achieves an expected score of ~229.64 points per game.

Game State

The game state tracks which of the 13 scoring categories have been filled, represented as a 13-bit integer. This gives $2^{13} = 8192$ possible game states. For each state, we precompute the expected value of optimal play from that point forward using backward induction.

Dice Representation

A dice configuration is represented as a count vector $c = (c_1, c_2, c_3, c_4, c_5, c_6)$ where $c_i$ is the number of dice showing face $i$. This order-invariant representation reduces the state space from $6^5 = 7776$ permutations to just $C(n + k - 1) = C(10, 5) = 252$ multisets.

The Bellman Equation

Let $V(s)$ be the expected value of game state $s$ (which categories remain). For a single turn with dice $c$ and $r$ rolls remaining:

Base case (no rolls left):

Recursive case:

The key insight is that when choosing which category to score, we consider not just the immediate points but the future expected value of the resulting game state.

Precomputation

Expected values for all 8,192 game states are precomputed offline via backward induction, starting from terminal states (all categories filled) and working backward. This table is loaded at runtime, making real-time optimal play computationally feasible.

Simplifications

To keep the state space tractable, we do not track progress toward the 35-point upper section bonus. Tracking this would multiply states by ~64x (for each possible upper score from 0-63). The precomputed values still achieve near-optimal play in practice.

Single Roll Probabilities

Three-Roll Probabilities (Optimal Play)

Starting from a random roll and playing optimally: