Reports · 2026-09-18
Belief rollouts lose 81 of 100 games to expectimax
Belief rollouts against expectimax, 100 paired games
| Row | Value | Low | High | n |
|---|---|---|---|---|
| rollout (8 worlds, 4 playouts, 24 plies) | 19 | 12.5 | 27.8 | 100 |
| expectimax (16 worlds, depth 2) | 81 | 72.2 | 87.5 | 100 |
Rollout won 10 games as Red and 9 as Blue; all 100 games ended by Flag capture and none reached a draw rule. In the Elo fit over every registered pairing, rollout lands at 1283, below greedy's 1393 and above the smoke network's 1090, with expectimax at 1535.
Why random playouts lose to a two-ply search
Both players sample worlds from the same counting belief and both score terminal positions with the same material table. The difference is what happens between the root and the leaf. Expectimax looks two plies ahead in every world and takes the minimax value; rollout plays 24 random plies and takes the average. Random play from a Stratego position is nearly uninformative: a piece that is attacked by a Marshal survives most random playouts because the random mover rarely chooses the capture, so the average hides exactly the threats that decide games. Rollout made 878 attacks in the 100 games to expectimax's 1,617, and lost 174 of them into Bombs, so it was neither more careful nor more aggressive, only less directed.
The method is the baseline the Ataraxos search improves on: the paper's test-time search also rolls out sampled worlds, but for 40 plies under the trained policy rather than at random, and treats the values as gradient signals for a regularised policy update rather than as an average. The gap between this rung and the search rung of the pipeline is the value of a learned rollout policy.
19%19/100, 13% to 28%Replays from the library: rollout as Red on seed 0 and rollout as Blue on seed 0. The value trace of each side is drawn under the board; rollout's stays flatter because averaging over random playouts compresses every estimate toward zero.
Reproduction
Registration experiments/6e83e965-97e5-4171-a761-dbbdcea3fa01.toml. Commands, from the repository root:
cd server && cargo run --release -p armies-arena --bin matchup -- --red rollout --blue 'expectimax:{"samples":16,"depth":2}' --games 100 --seed 0 --rules training --threads 32 --moves --out ../research/runs/6e83e965-97e5-4171-a761-dbbdcea3fa01/rollout-vs-expectimax.json --record-dir ../research/runs/6e83e965-97e5-4171-a761-dbbdcea3fa01/records --tag 6e83e965-97e5-4171-a761-dbbdcea3fa01
cd research && python3 scripts/paired_contrast.py runs/6e83e965-97e5-4171-a761-dbbdcea3fa01/rollout-vs-expectimax.json
cd research && python3 scripts/build_second_pass_assets.pyThe match took 4.1 seconds of wall time on 32 threads. The record carries the SHA-256 of the 3.9 MB JSON output.