All Policy, No Judgement
Our first network beats two-ply search, but its own value head, searched over, loses to it 20:1.
This is a project to build a bot that wins at Catan: full rules, four players, trading included. The gap we want to close is a benchmarking one: published Catan agents report that iteration N beats iteration N−1, which shows a training loop works and says nothing about absolute strength, because no published full-rules four-player agent has been measured against an outside opponent.
Week one ran from an empty directory to a trained network with a search on top, measured on one desktop: 32 logical cores and an integrated GPU. Every result is four-player; a 2x2 seats two copies of each bot at a four-seat table, so even is 50%.
The baselines, and the ceiling over them
The engine is ours: topology derived from a bare set of hex coordinates, so base, mini and multi-island boards all go through one code path. On top of it sit two bots. greedy is one ply over a nine-term handcrafted evaluation; search2 is two plies of max^n over the same evaluation. greedy shuts out random 400/400, and search2 beats greedy 60.8%, 95% Wilson interval [55.9%, 65.4%], over 400 games.
Fitting those nine weights from the original guesses was worth a lot — 70.9% [68.9%, 72.8%] over 2,000 games — and refitting them once trading landed was worth 56.2% [54.1%, 58.4%]. Three further refits found nothing, and the interesting part of the week was finding out why. Instead of arguing about the optimiser we measured the landscape: nine values of the weight on resource production, the most load-bearing one, played against the intact weights, 2,000 games each, 18,000 in total. Only 3.0 and below — a 58% cut — can be told apart from the fitted 7.067, and everything from 3.5 to 10 is indistinguishable. Halving it costs 3 pp, and a 60-step hill climb started from that half ended at 2.291, further from the fitted 7.067 than where it started.
Win rate against itself only detects weights that are badly off. A refit that finds nothing doesn’t show the weights are optimal. We stopped hand-tuning.
Trading, which published agents switch off
Player-to-player trading is in, the mechanic every published agent disables because it explodes the action space. It is worth having: a greedy bot that proposes beats an identical bot that can only respond 66.5% [62.6%, 70.2%] over 600 games. It costs about fourfold throughput: a greedy game goes from 360 actions to 1,892 with the turn count barely moving, so nearly all of that is negotiation.
Two findings fell out of it. First, a search that reads its own component of the per-seat vector accepts any trade that improves its own hand — Pareto efficiency in an exchange economy. Catan is a race, and an offer that gains you one and the leader three is a loss. Subtracting the mean of the other seats before maximising beats plain max^n 53.6% [51.4%, 55.8%] over 2,000 games, same weights both sides. Second, the eight offers a turn the engine allows are a constant rather than a rule, and capping a bot at three is nearly free: 52.0% [49.8%, 54.2%] to the unlimited side over 2,000 games, about 0.1 victory points out of 10 on paired terminal differences, and a game cut from 2,225 actions to 950. Every 2x2 below is budget-matched at three.
A small network, shaped by a fixed overhead
The model is heterogeneous message passing over the encoder’s graph — hexes, vertices, edges and a global token, two rounds at width 64, 159,446 parameters. The policy head reads out per node, so masking illegal actions costs nothing; the value head emits one number per seat, because a four-player game needs a score for every seat.
One measurement shaped everything built on it. A forward pass costs a fixed per-call overhead (kernel launch) — 12.5 ms eager, ~1.5 ms once compiled with CUDA graphs — plus about 25 µs per position. So everything batches: a collector that steps 512 games in lockstep, a search that gathers its leaves in waves.
PPO was not supposed to work this well
The first PPO run was 200 iterations, 25,517 games, 5h 20m on the desktop’s GPU. Its in-loop evaluation against random saturated at iteration 49, so the win rate says nothing about the last 150 iterations; the training log does better. Entropy fell 1.373 → 0.620 and games went from 172 turns to 88 while rising slightly in actions, 912 to 1,000. Same work per game, half the turns: the policy converts a turn into progress about twice as often. Then it went into the arena, where the prediction on record — that a raw policy would lose to a two-ply search — turned out to be wrong.
Table
| estimate | low | high | n | |
|---|---|---|---|---|
| network vs greedy | 66.0 | 64.5 | 67.4 | 4000 |
| MCTS@256 vs MCTS@16 | 65.5 | 60.7 | 70.0 | 400 |
| network vs search2 | 56.9 | 55.5 | 58.3 | 4000 |
| MCTS@256 vs network | 56.8 | 51.9 | 61.5 | 400 |
| MCTS@64 vs network | 51.0 | 44.1 | 57.8 | 200 |
| netsearch vs search2 | 16.5 | 14.9 | 18.1 | 2000 |
| netsearch vs greedy | 15.4 | 13.9 | 17.1 | 2000 |
| netsearch vs network | 4.6 | 3.8 | 5.6 | 2000 |
95% Wilson intervals. Two seats a side, seats rotated, three offers a turn on both sides; n per row in the table.
network beats greedy 66.0% [64.5%, 67.4%] and search2 56.9% [55.5%, 58.3%], 4,000 games each. A five-hour network beating a fitted two-ply search is the kind of result a harness bug produces, so it got three controls. Four identical greedy entrants over 4,000 games split 25.3 / 25.1 / 24.4 / 25.3, a spread of 0.9 pp; the greedy 2x2 replicated at an independent seed came back at 66.0% against 66.0%; and matching the offer budget on both sides moved the search 2x2 only from 57.3% to 56.9%.
Why it wins is not settled, and this is the part I would not write up as skill. Over 40 recorded games the network accepts 0.1–0.6 trades a game where greedy accepts 21.6–27.1, while proposing just as often. Against opponents that accept freely, near-refusal is close to correct in a race — but four seats that never accept generate no signal for accepting, so the branch may simply be unvisited. Telling skill from a self-play convention (nobody accepts because nobody ever has) needs an opponent that trades well, which self-play never contained.
The value head is globally calibrated and locally blind
Put the same checkpoint’s value head where the handcrafted evaluation was, keeping depth, width and offer budget identical, and netsearch loses to search2 16.5% [14.9%, 18.1%] over 2,000 games. It loses to one-ply greedy just as badly, 15.4% [13.9%, 17.1%] — the opponent’s depth barely matters, so this is leaves being mis-scored rather than a search being out-searched. Against the policy head it shares a trunk with, it wins 4.6% [3.8%, 5.6%]: one checkpoint’s value head, searched over, losing 20:1 to the same checkpoint played straight.
The explanation written down in advance was off-policy error — PPO trains the head on its own games and a search asks it about positions it never visits. That is measurable: let a named entrant decide the moves while the network only predicts, and the gap between two such runs is the penalty. Over 256 games each, the head’s explained variance is +0.474 on its own positions, +0.453 on search2’s and +0.485 on greedy’s. There is no penalty, and it is better on greedy’s positions than on its own.
Table
| fifth of the game, opening (1) to end (5) | its own policy | search2 | greedy |
|---|---|---|---|
| 1 | 0.15 | 0.13 | 0.22 |
| 2 | 0.3 | 0.31 | 0.35 |
| 3 | 0.45 | 0.46 | 0.46 |
| 4 | 0.63 | 0.6 | 0.6 |
| 5 | 0.83 | 0.78 | 0.8 |
256 games per behaviour policy, one fixed board, seed 5; 221,407-258,397 positions each. The named entrant played; the network only predicted.
What is wrong is resolution, not domain. The head’s residual variance of 0.045 is an RMS error of about 2.1 victory points — fine for saying how a seat is doing. A search asks a different question: which of two children, one action apart, is better. Over 4,105 probed positions averaging 7.0 legal children, the spread of the head’s own values across a row of siblings averages 0.0114. Replaying 64 positions 64 times each splits its error exactly: 68.4% is irreducible outcome variance, dice not yet rolled, and the other 31.6% is bias — an RMS of 0.129, about 1.3 victory points. Bias is the part that misranks, and it is eleven times the spread it is asked to resolve.
That eleven is an upper bound, not a measurement: siblings are nearly identical positions, so their biases are probably correlated, and correlated bias cancels in a comparison. The decisive run rolls out every child and compares the head’s ordering with the true one. Until it is taken, nothing rules out misranking and nothing shows it.
The prior puts the search back together
MCTS is PUCT over the same checkpoint, leaves gathered into waves so the fixed overhead is paid once per wave. At 64 simulations against the raw policy it draws: 51.0% [44.1%, 57.8%] over 200 games. Beside the 20:1 above, that says the prior does all of the work, and that 64 simulations then buy nothing on top of the policy.
Before the budget ladder ran I wrote down that flat would mean the value head binds, and falling that it misleads. MCTS@256 beat MCTS@16 65.5% [60.7%, 70.0%] over 400 games: climbing. What a simulation mostly buys is distance from the part of the game the head cannot read: deeper trees reach exact terminal values and end at leaves where explained variance is +0.83, not +0.15.
So the head does not gate the next step. What gates it is whether a search at an affordable budget beats the policy it would distil into, and by the end of the week it does: MCTS@256 beats the raw policy 56.8% [51.9%, 61.5%] over 400 games, the first interval against that policy to clear 50%. The search is a teacher, by about 7 pp, bought at 59 ms a move and 64 games an hour in a single process.
Next, and what I expect
expert iteration is the main line now: distil the search’s visit counts into the policy, train the value head on what the search visited, repeat. Four predictions a later post can check:
- The wave size is the cheap win. The network is 64.6% of a
@256move and most of that is fixed overhead, paid about ten times a move because 151 leaves meet a wave of 16. Raising the wave should cut at least a third off the cost of a searched move. - The first distilled policy beats the current checkpoint, but by less than its teacher does. The teacher is +6.8 pp; I expect the student at +2 to +5 pp over at least 2,000 games, since distillation rarely reaches the thing it copies.
- The sibling-ranking run comes back less damning than elevenfold, because correlated bias cancels — but still too weak to use without a prior.
- The trade refusal is at least partly a self-play convention. Given an opponent that trades well, I expect acceptance to rise above one a game.
One last thing, before any table here gets quoted sideways: nothing here says how the bot would do against a person. Our notes carried a human comparison column, its provenance could not be established, and it is withdrawn. An external benchmark is still a deliverable rather than a result.