Minimax handles a future where half the branches are chosen by an adversary trying to make your outcome as bad as possible. Expectimax handles a different kind of uncertain future: one where a branch is picked by chance, not by anyone at all — a die, a shuffled deck, a random tile spawn. It reuses minimax's exact shape (a max node picks the best of its children's values) but replaces the minimizer with a third kind of node entirely: a chance node, whose value is the probability-weighted average of its children, not the best or the worst of them. No adversary is required at all — this is the same node structure real engines use for a random tile spawn in 2048, a dice roll in backgammon, or a card draw in blackjack, and this page's own demo is the last of those three.
The game is Push to 21: starting from a running total of 0, roll a
ten-sided die (faces 1–10) as many times as you like, adding each roll to
your total. At any point you can stand and bank the current total, or hit
and roll again — but go over 21 and you bust, banking nothing. The question
expectimax answers at every total is: is one more roll worth it? The table below fills in by
backward induction, from total 21 down to total 0, because the
value of hitting from any total depends on the (already-known) value of every total it could roll into —
exactly the dependency order 0/1 Knapsack and
Longest Common Subsequence fill their own
tables in, just running from the end of the game backward instead of from an empty prefix forward. Press
Step or Run. Rows where the exact answer disagrees with a common
shortcut — "keep rolling until your total is at least 17," the same fixed-threshold instinct
real blackjack's dealer rule uses — are flagged the moment they're computed.
| total | stand | hit (avg) | optimal | hit if <17 |
|---|
Every total from 21 down to 0 gets exactly one number, EV[t],
the best possible expected banked score reachable from total t with perfect decisions from
here on. EV[21] = 21 — standing is the only sane move with no room left to roll. For every
total below that, standing is worth exactly t (whatever's already banked), and hitting is
worth the average of the ten possible next totals, treating any that bust as
0: hit(t) = (Σ EV[t+d] for d in 1..10, using 0 for any t+d > 21) / 10.
EV[t] = max(stand(t), hit(t)) — the same "try both, keep the better" shape
Knapsack's skip-or-take recurrence uses, except one
of the two options here isn't a single known value, it's an average over ten already-solved
subproblems. That average is the chance node: nobody is choosing which face comes up, so the honest way
to value "roll and see" is to weight every outcome by how likely it actually is, not to assume the best
one or the worst one will happen.
function backwardInduction(target = 21, dieMin = 1, dieMax = 10) {
const faces = dieMax - dieMin + 1;
const ev = new Array(target + 1);
const action = new Array(target + 1);
for (let t = target; t >= 0; t--) {
let hitSum = 0;
for (let d = dieMin; d <= dieMax; d++) {
const next = t + d;
hitSum += next > target ? 0 : ev[next]; // bust banks nothing
}
const hitValue = hitSum / faces; // chance node: average, not min or max
const standValue = t;
ev[t] = Math.max(standValue, hitValue);
action[t] = hitValue > standValue ? 'hit' : 'stand';
}
return { ev, action };
}"Hit until at least 17" is a real, common rule of thumb — and it's measurably wrong here.
Running the recurrence above shows the optimal action flips from hit to stand at
total 14, three totals earlier than the naive threshold. At total 16 the gap is
stark: standing banks 16 outright, while hitting once more (as the naive rule insists, since
16 < 17) averages only 9.5 — five of the ten faces (6 through
10) push the total past 21 and bust. That 9.5 isn't asserted, it's
the exact figure this page's own recurrence computes at total 16, cross-checked against a
2,000,000-hand Monte Carlo simulation using this site's same seeded mulberry32 generator
(the one skip list's preload and
Monte Carlo Tree Search's playouts both use): the simulation landed
at 9.5037, well within noise. Played out over a full hand starting from total 0,
following the naive rule instead of the exact answer costs an average of 2.14 banked points
per hand (15.86 optimal vs. 13.72 naive, both figures confirmed the same way) —
three wrong stopping decisions, repeated across every hand that happens to pass through them, add up to a
real and checked amount of lost value.
A chance node isn't a min node — mistake one for the other and the whole tree collapses toward
a single pessimistic fixed point. Swap the average in hitSum / faces for a
Math.min over the same ten branches — treating every roll as if the worst face were
guaranteed, the way minimax's minimizer treats an adversary's move — and the recurrence no longer answers
the same question. Run it and EV[0] drops from the correct 15.86 to exactly
12.00, and the stand threshold moves to total 12 instead of 14 —
not a small correction in the safe direction, a collapse to a fixed point where hitting is assumed to
always roll the worst face forever. The bug never throws: it just quietly assumes an opponent is rolling
the dice against you, the same silent failure mode
Minimax's own "flip which side is maximizing" pitfall
describes, extended to a third node type this page adds.
Time: O(target · faces) for this page's linear-chain version — one
constant-time average over faces branches per total, target + 1 totals, so
22 × 10 = 220 additions total for this demo's numbers. In general, a max node with branching
factor b and a chance node with s equally-costly outcomes multiply together per
ply, giving O((b · s)^d) for a d-ply lookahead — the same shape as minimax's
O(b^d), with the chance node's outcome count folded into the per-ply branching factor. Like
0/1 Knapsack's table, this cost is
pseudo-polynomial: it scales with the numeric size of the target, not the size of its
representation — doubling the bust threshold doubles the table, even though "42" takes one more character
to write than "21." Space: O(target) for the full table, since every cell's
hit value only ever reads cells above it.
This is the site's third Game Trees entry, alongside
Minimax with Alpha-Beta Pruning and
Monte Carlo Tree Search — three different answers to the same
problem, "the future isn't fully mine to choose." Minimax assumes the worst, because an adversary is
really there. Expectimax assumes nothing and averages, because the true odds are known and nobody is
choosing against you. MCTS reaches for sampling when neither exhaustive search nor a clean probability
distribution is available — a Go board's branching factor is too large to visit every child, chance node
or not, so it estimates instead of computing exactly, the same trade this page's own
O((b·s)^d) bound explains the need for. A fourth entry,
Transposition Tables, doesn't compete with any of
these three answers — it just makes sure the same question, chance node or adversary or otherwise,
never gets answered twice. A fifth, Principal
Variation Search, only refines the first of the three — minimax's own adversarial search gets a
cheap yes/no question before every expensive one, with no equivalent trick available once a chance
node's averaged outcome replaces a real opponent's chosen one. A sixth,
Iterative Deepening, is orthogonal to the
chance-node question entirely — it's about how much of any of these three searches actually gets
run before time runs out, not about what happens at each node once the search reaches it. A seventh,
Zobrist Hashing, doesn't touch this page's own
chance-node question either — it's the incremental technique behind Transposition Tables' own cache
key, and this page's own averaging never needs a key at all, since nothing here is ever cached or
re-looked-up. See
Choosing a Game Tree Search Algorithm
for how all ten compare side by side, starting with exactly this chance-vs-adversary fork.