Search under uncertainty

What should expectimax average over, and where does opponent choice enter?

The decision at the table

Dice introduce chance. Other players introduce strategic responses. Averaging possible dice rolls does not tell you whether a rival accepts your trade, blocks your road, or targets you with the robber.

The mechanism to test

Separate legal candidate generation, chance outcomes, hidden-state beliefs, opponent response policy, and leaf evaluation. Compare expectimax with belief rollouts and information-set tree search at the same decision budget. Preserve one action choice across states the player cannot distinguish; otherwise search can plan with information it will never receive.

What has been built

expectimax-v2 in the server's expectimax crate plans the current turn as a small tree: every first action, then the best few continuations by static value, with purchases, thefts and the player's own roll branching exactly over their outcomes. A first action is credited with the best line it enables. The afterstates of that line are followed through the other seats' turns, played by a fixed builder under common random dice scenarios so every candidate is judged on the same dice, and then through the player's next turn as a greedy line. Iterative deepening adds one planned turn at a time under a wall-clock budget and a depth cap, and the deepest completed depth is played. The leaf prices points, cards, production and build targets in one card-value currency, with tunable weights and five inclination sliders. The development report records the first cohorts, which ran with a turn-planning defect, the corrected search report records the paired cohorts after the fix, and the protocol confirmation records the corrected candidate winning 47 of 80 authoritative games.

Proposed experiment

First compare the fixed expectimax reference with a response-aware evaluator at equal time and candidate budgets. Then compare search families with shared beliefs and leaf values. Hypothesis: modelling responses matters more than simply adding depth in trade-rich positions.

Plot win-rate intervals against decision latency and compute cost, with budget exhaustion and fallback rates visible. Retain candidate IDs, values, observation version, and the unchanged reference. The current web reference uses additive heuristic points, not calibrated win probabilities.

First ablation

Removing the lookahead (depth 1) changed the contrast by -0.324 wins per game (95% interval -0.413 to -0.235), and two dice scenarios instead of eight by -0.410 wins per game (95% interval -0.489 to -0.331): the two decisive results of the ablation program. Details and every run ID are in the ablation report; this is a development-tier result on one lineup.

Third round

The same settings were re-measured under the learned n-tuple leaf as seating-corrected swapped pairs against the tables baseline, 54 cohorts on development, fresh, and population boards (report). The stronger leaf makes the search's information inputs worth more, not less: scenarios 4 costs −0.392 wins per game, samples 1 costs −0.109, counts-only beliefs −0.143, and turning proposals off −0.172, each with an interval excluding zero; the reciprocity scaling is refuted at −0.073. Eight sampled worlds gain a confirmed +0.045 against builders for 1.8 times the decision cost and nothing against a table of searches; sixteen scenarios and the leaf-guided opponent model buy nothing measurable for 2.7 and 1.8 times the cost. inner_scenarios cannot bind at depth 2 at all. No switch earns a place in the browser build; the defaults stand.

What could disprove it

A stronger leaf model, larger candidate set, or larger time budget can masquerade as a search improvement. Hidden-state samples can also cause strategy fusion: choosing different actions using information unavailable to the actual player.

All approaches · Player’s guide · Experiment program

Tracked investigations