Building an Optimal Yahtzee Player with Go and Raspberry Pi: Part 2
Part 1 turned solitaire Yahtzee into a dynamic program: work backwards from completed score sheets, take expectations over rolls, and choose the best available action. This post is about making that idea run fast enough to be useful.
The complete implementation is available at github.com/timpalpant/yahtzee and can be played interactively at yahtzee.palpant.us. It has a Go game library and optimizer, a small HTTP API and browser client, and the Raspberry Pi player described in Part 3.
The shape of the program
The code separates the rules of Yahtzee from the thing being optimized. The core package knows how to represent a roll, score it in a box, and transition to the next game state. The optimization package knows how to work backwards through those states. A strategy table then serves multiple clients: the browser can ask for advice, while the robot can ask for the next button press.
That separation matters because the same game tree supports several objectives: ordinary expected score, the probability of meeting a score target, and the expected number of rolls required when starting over is allowed.
Small representations, large savings
An unscored GameState fits in 20 bits:
filled-category mask | Yahtzee-bonus flag | upper subtotal (capped at 63)
The 13-category mask says which boxes are no longer available. A single bit records whether later Yahtzees can collect their bonus. The current total is added only for the score-targeted restart calculation, where it genuinely changes the answer.
The upper subtotal is capped at 63 because 63 is the bonus threshold. A game sitting at 63 and one sitting at 70 have identical futures: both have already secured the 35-point upper-section bonus, and no later play can take it away or add to it. The subtotal is tracked only to answer the question “will the bonus be paid?”, and above the threshold that question is settled, so every value at or above 63 can share one state.
The representation is compact, but it is not merely a packing trick. It gives a fast key for every lookup table and makes the state equivalences explicit. The enumerator finds 536,448 reachable score-independent states, rather than wasting time on impossible bit patterns.
Rolls are histograms, not lists
The physical game displays five dice in five positions, but the solver only needs to know how many ones, twos, and so on are present. A Roll stores six three-bit counters in one unsigned integer:
// Each three-bit field is the count of one face value.
type Roll uint
This makes a roll an unordered histogram. There are 252 valid five-die histograms, rather than 7,776 ordered rolls, and both their probabilities and their possible holds can be precomputed at startup. A held pair of fives is one choice, not ten different ways to point at two equal dice.
Three possible value functions
The optimizer is generic over a GameResult. It asks the result type to provide a terminal value, add a probability-weighted successor, choose the better of two actions, and shift a result after points are added to the score sheet. That small interface is enough to reuse the same traversal for several goals.
| Objective | Value stored at a state | Is current total needed? |
|---|---|---|
| Maximize expected score | One float32 expected remaining score | No |
| Meet a high score | A tail distribution of remaining scores | No |
| Minimize rolls until a target is met | One expected-work value for one target | Yes |
For the distribution objective, entry s is the probability of earning at least s more points. Scoring a box shifts that vector by the points just earned; averaging rolls adds vectors; choosing an action takes their element-wise maximum. The same table can therefore answer a probability question for any target score without recalculating the game tree.
Expected work takes the opposite trade-off. It stores only one target score at a time, but it can include the running total and the cost of pressing New Game. That keeps the restart policy tractable despite its much larger state space.
Working backwards through a turn
The outer loop groups game states by the number of filled boxes and processes them from turn 13 back to turn 0. By the time a final-roll decision is evaluated, every resulting next-turn state already has a value in the table.
Within a turn, the recurrence is evaluated in the opposite direction from how a human experiences it:
- For a completed third roll, choose the best open scoring box.
- For each second-roll hold, average the values of all possible third rolls.
- Choose the best hold after the second roll.
- Repeat for the first roll, then average all possible opening rolls.
The inner expectation is memoized by the multiset currently held. If the solver has already calculated the expected value of holding [5, 5], every path that reaches that hold reuses the answer. When a score-independent objective crosses into the next turn, the implementation strips the total score from the state and shifts the result by the points just earned. That avoids duplicating equivalent future work.
Where the time went
The expected-score table is pleasantly small. Probability distributions are not: each state carries a vector indexed by possible score, and the generated table in this project was about 1.8 GB on disk (versus about 5.7 MB for expected value). Profiling made it clear that the hot path could not afford a fresh slice allocation for every hold and roll.
The performance-oriented version of the code therefore:
- precomputes rolls, holds, probabilities, and available boxes;
- reuses per-turn memoization caches;
- gives each worker a private arena of result objects instead of allocating in the inner loop;
- divides each turn’s states among CPU workers, then merges their results after the whole turn is complete; and
- stores distributions as
float32values and updates them in place, using SIMD kernels.
Three operations on a vector of scores
The expected-value solver stores one number per state. The distribution solvers store 1,500 — one float32 for every reachable final score, 6 KB per state, which is where that 1.8 GB comes from. It also changes what the inner loop is doing.
Every result type implements the same small interface, and it has only three interesting operations:
- Max — combine two alternatives, keeping the better one.
- Add — accumulate a child result, weighted by the probability of the roll that leads to it.
- Shift — slide a distribution along by the points just scored.
For the scalar objective those are a comparison, a multiply-add, and an addition. For the vector-valued objectives, each one is a loop over 1,500 floats, and it runs for every hold, of every roll, of every state, of every turn. That loop is essentially the entire program.
There is a pleasing inversion buried in it. For a score distribution, “keep the better alternative” is an elementwise max, because more probability is better. For expected work — the restart policy from Part 1 — it is an elementwise min, because less work is better. Same interface method, opposite kernel:
// ScoreDistribution
func (sd ScoreDistribution) Max(other ScoreDistribution) { f32.Max(sd, other) }
// ExpectedWork
func (ew ExpectedWork) Max(other ExpectedWork) { f32.Min(ew.Values, other.Values) }
So the whole solver rests on three vector primitives: elementwise max, elementwise min, and AXPY (dst += alpha * src).
Writing Go assembly
Go doesn’t have SIMD intrinsics, but it does allow you to link assembly, a descendant of Plan 9 assembly. I adapted AxpyUnitaryTo from Gonum (BSD) to create the Max and Min kernels.
// func Max(dst, s []float32)
TEXT ·Max(SB), NOSPLIT, $0
MOVQ dst_base+0(FP), DI // DI = &dst
MOVQ dst_len+8(FP), CX // CX = len(dst)
MOVQ s_base+24(FP), SI // SI = &s
CMPQ s_len+32(FP), CX // CX = min( CX, len(s) )
CMOVQLE s_len+32(FP), CX
The kernel is the four-lane SSE instruction MAXPS, which computes four single-precision maxima at once, and the loop is unrolled sixteen wide across four XMM registers:
max_loop: // Loop unrolled 16x do {
MOVUPS (SI)(AX*4), X0 // X_i = x[i:i+1]
MOVUPS 16(SI)(AX*4), X1
MOVUPS 32(SI)(AX*4), X2
MOVUPS 48(SI)(AX*4), X3
MAXPS (DI)(AX*4), X0
MAXPS 16(DI)(AX*4), X1
MAXPS 32(DI)(AX*4), X2
MAXPS 48(DI)(AX*4), X3
MOVUPS X0, (DI)(AX*4)
MOVUPS X1, 16(DI)(AX*4)
MOVUPS X2, 32(DI)(AX*4)
MOVUPS X3, 48(DI)(AX*4)
ADDQ $16, AX
DECQ CX
JNZ max_loop // } while --CX > 0
The rest of the function is bookkeeping, and it is most of the code: a prologue that handles elements one at a time until the destination pointer is 16-byte aligned, then the 16-wide loop, then a 4-wide loop for the remainder, then a 1-wide loop for the last three or fewer elements. A vector of 1,500 floats divides as 93 iterations of the main loop, three of the 4-wide tail, and none of the last. This shape — align, unroll, drain — is the universal skeleton of every hand-written SIMD kernel, and it is why they are all four times longer than you expect.
Turning tables into advice
Once you’ve computed the optimal strategy tables, yahtzee_server loads them and exposes a JSON endpoint. A request includes the filled boxes, the relevant bonus state, the current dice, and whether it is after the first, second, or third roll. The response supplies either the dice to hold or the box to fill, plus the value associated with that choice. For a score target it can also recommend a restart.
The browser client uses the same endpoint to show move advice and compare the possible outcomes of holds and scoring choices. More importantly for this project, the HTTP boundary lets a memory-constrained Raspberry Pi ask a larger machine for a policy decision instead of trying to load multi-gigabyte tables itself.
In Part 3, that request/response loop leaves the browser behind: a camera reads the handheld’s LCD, GPIO-controlled relays press its buttons, and the strategy becomes a physical player.
The same JSON endpoint, answering to a camera and a bank of relays instead of a browser: the dice on the LCD change, the strategy service is asked what to do, and the holds and scoring choices come back as button presses.
