Why is RL harder for stochastic games than for deterministic ones?

In a deterministic game like chess, the same move from the same position always gives the same result. In a stochastic game, the same move can produce many different outcomes depending on dice. The value of a move is therefore an expectation over future randomness, not a single number — and estimating expectations from samples is noisier than computing exact values.

Does randomness make backgammon strategically simpler?

No, the opposite. Randomness compresses the gap between near-best and best moves (the dice can compensate for small mistakes), but it also enlarges the space of decisions you have to handle since every position recurs in many dice contexts. World-class backgammon is a notoriously hard skill ceiling.

How do engines handle the dice in their search?

Two main approaches. Ply-0 (network-only) skips dice search and trusts the value function. Ply-2 enumerates all 21 dice combinations for the opponent, evaluates each, and averages. Deeper-ply (3+) keeps expanding both sides' dice trees but the cost grows fast (~21× per ply).

Why don't backgammon engines use Monte-Carlo Tree Search like Go?

MCTS works best when you can sample many lines without combinatorial explosion. With dice, every node has a 21-way chance branch you have to either expand or sample, which inflates the tree. Most backgammon engines stick to bounded-depth search with NN evaluation at the leaves; the gains from MCTS over network+search aren't big enough to justify the complexity.

Stochastic Games and RL: Handling Chance in Backgammon and Narde

2026-07-14

The previous article in this series introduced reinforcement learning through board games. Most of the framework — states, actions, rewards, value functions — applies to deterministic and stochastic games alike. But the addition of randomness changes the maths in important ways. This article is specifically about what happens when chance enters the picture, using backgammon and long narde as the running examples.

The chance node

Standard game-tree drawings have two kinds of internal nodes: max nodes (your turn — you pick the move that maximises your value) and min nodes (opponent’s turn — they pick the move that minimises yours). For dice games we need a third type: the chance node.

A chance node sits between a player’s decision and the next player’s decision. It represents the dice roll. The value of a chance node isn’t a max or min of its children — it’s an expectation over them, weighted by probability:

V(chance) = Σ_{dice} P(dice) × V(child(dice))

For backgammon, the dice produce 21 distinct combinations (15 mixed pairs each at probability 2/36, plus 6 doubles each at 1/36). For long narde, the same 21 combinations apply.

This single change ripples through everything. Bellman equations now have an expectation operator. Gradients flow through stochastic transitions. Sample-based estimates carry inherent variance even when the policy is fixed.

Estimating expected value from samples

The clean equation V(chance) = Σ P(dice) V(child) is fine in theory but has a practical problem: V(child) for each dice outcome is itself an expectation over future randomness. Recursively, the value of any non-terminal state is an expectation over all possible future trajectories — combinatorially infeasible to enumerate.

Reinforcement learning sidesteps this by replacing exact expectation with sample-based estimation. Roll the dice, see what happened, treat that single trajectory as one Monte-Carlo sample, average many samples. This is fine but introduces variance. The same algorithm trained twice with different random seeds can converge to slightly different value functions, especially in low-data regimes.

A few techniques reduce the variance:

Antithetic sampling. When you generate self-play games, pair each game with one where the dice rolls are inverted. The two games tend to have offsetting noise, so the combined trajectory has lower variance than two independent games.

Importance sampling. When evaluating a policy on data generated by a different policy, weight each sample by the probability ratio. Useful for off-policy learning where you reuse old data after updating the policy.

Eligibility traces (TD(λ) with λ > 0). Spread the credit-assignment over multiple steps backwards, weighted exponentially. Reduces variance compared to TD(0) at some bias cost.

TD-Gammon used TD(λ) with λ=0.7. Modern systems often use higher λ (0.9–1.0) or pure Monte-Carlo (λ=1.0) when training compute is plentiful.

The credit-assignment problem in dice games

Here’s a subtle issue: when a stochastic game ends, the agent receives a final reward (+1 or -1). To learn, it needs to attribute that reward to specific decisions earlier in the game. But in a dice game, the outcome depends partly on dice luck — you might have played a brilliant move and still lost because the opponent rolled doubles three times in a row.

Naively assigning the final reward proportionally over all moves means the agent occasionally «punishes» good moves and rewards bad ones. With enough data this washes out (the law of large numbers eventually catches up), but it slows training.

Solutions:

Equity-based feedback during the game. Instead of waiting for the terminal reward, compute equity (expected outcome from current position) at each step using a baseline policy. The agent updates toward equity differences, not raw outcomes. This is essentially what TD does — V(s) is an equity estimate, and the TD error is an equity gradient.

Bootstrapping with strong opponents. Self-play can drift; mixing in games against a fixed strong opponent (or against many sampled past versions) gives a more stable reward signal.

Long horizons → terminal rewards. Counter-intuitively, when episodes are very long, raw final rewards become less noisy because dice variance averages out. Backgammon games have ~50–80 plies; this is short enough that single-game variance is meaningful.

Search depth and the cost of ply

The deeper the search, the better the play, but every ply you add multiplies cost.

For deterministic games like chess, going from depth-1 to depth-2 multiplies search cost by the average branching factor (~35 for chess). For backgammon, the cost is multiplied by 21 (dice) × ~20 (legal moves per dice) = ~420 per ply on average. So:

ply-0: one network forward pass per candidate move. Sub-millisecond on GPU.
ply-2: enumerate opponent’s 21 dice and their best response. ~50–200ms per position.
ply-3: another player’s dice + best move. Hundreds of ms.
ply-4+: rarely used; cost approaches seconds and the equity gain is small relative to the latency cost.

Modern engines pick depth based on use case. For a real-time UI showing best moves during play, ply-0 or ply-2 is the practical ceiling. For deep analysis or rollouts (Monte-Carlo simulation of many games from a given position), ply-3 or rollout depths of 1296 (=6⁴) are common.

Rollouts: the gold standard for evaluation

A rollout from a position means: simulate K games starting from that position, with both sides using the engine to choose moves, and average the outcomes. This gives a high-quality estimate of the true equity of the position.

Rollouts are expensive — K is typically 1296 or higher, each game is 50–80 plies, each ply requires network evaluation. For a single position, a 1296-game rollout can take seconds to minutes depending on hardware.

But rollouts are extraordinarily useful:

They are the gold-standard reference for tuning lower-depth evaluations.
They provide training labels: each rollout output becomes the «ground truth» for the position, used to retrain the network.
They expose long-term consequences of structural decisions that one-ply evaluation may miss.

In our pipeline, rollouts are how we generate training data: random + self-play + expert positions are all evaluated by rollout, and the rollout outcome becomes the supervised target for the next training cycle. The cycle is rollout → train → tournament → promote → reclassify, repeated indefinitely on a single GPU.

Stochastic games and the dice as exploration

There’s a positive side-effect of stochasticity for RL: the dice provide free exploration.

In deterministic games, an agent that always picks the highest-value action will rarely encounter unusual states. To learn about them, you have to add explicit exploration noise — ε-greedy, dirichlet noise, etc. This can be tricky to tune; too much noise wastes capacity, too little leaves the agent stuck in narrow strategies.

In dice games, the same starting position produces wildly different game states by move 5 simply because the dice differ. An agent never sees the same trajectory twice. Exploration is built into the environment.

This is part of why TD-Gammon worked with such modest exploration — the dice were doing the exploration work that explicit ε-greedy would have to do in chess.

Long narde and stochasticity

Long narde shares all of backgammon’s stochastic structure (same dice, same chance nodes, same expectation-based equity). It adds two complications:

Phase-dependent value functions. The position can be in blocking, race, X-escaped, or O-escaped phase. The value function differs sharply across phases — race positions are dominated by pip count, blocking positions by structural priorities. A single network can learn this, but at the cost of capacity. We use phase-segmented networks: one network per phase, dispatched in O(1) by checker-counts at evaluation time.

Three-tier prize system. Mars and koks are different states, not just multiplied final rewards. The network has to learn to push for or avoid these states beyond the simple +1/-1 outcome. Our network outputs are nested-ordinal probabilities (P(win), P(win ≥ mars), P(win ≥ koks)) — equity is computed from this richer distribution.

These design choices fall out of the stochastic-games framework — they’re not additions but specific instantiations.

Where this fits

Stochasticity is the structural feature that distinguishes board games like backgammon and narde from chess and Go. The RL framework adapts cleanly — chance nodes, expectation over dice, sample-based estimation, depth-vs-ply trade-offs — but in practice every algorithmic decision has to consider the variance budget.

The next article in this series, TD-Gammon to modern AI, traces the historical arc of how the field handled these trade-offs over 30+ years.

If you want to skip to the code: the training pipeline article covers our actual rollout-train-tournament-promote loop, with concrete numbers on depth tiers and rollout sizes.