Transposition tables in the turn-level search

Why Catan transposes so much

A turn is a sequence of actions, and most sequences commute: a road then a city and a city then a road end in the same position. Dice that produce nothing for anyone, or produce only for opponents whose hands the player cannot see, leave the player's information unchanged, so several outcomes of one roll are the same position from that seat's point of view. The opponents' round under common random scenarios brings the player back to positions that differ only in what it could not observe. The tree-structure measurement counted the share of own-turn positions already seen at 21% at depth 1, 12% at depth 2, 7% at depth 3, and 5% at depth 4 with the original per-decision memo; in traced games of the learned-leaf search at depth 2, a contested decision expanded about 1,680 own nodes and hit the memo 270 times.

What changed

The key. A position is identified by everything the seat's observation would show: board and roads, its own hand and cards, bank and deck count, robber, awards, phase, turn, and the other seats' public counts. Hidden hands, the deck's composition, and the random cursor never enter it. Each field's identity and value pass through a 64-bit mixing finalizer and the results combine by exclusive or, in two independently salted words; the first indexes the table and the second verifies the hit, so a collision cannot return another position's value. The old key hashed the same fields through SipHash field by field.

Grouping order. Indistinguishable positions are merged at every branching point: dice outcomes, purchases, thefts, sampled hands, and the arrivals after the opponents' round. They were merged in key order, which made the order of every floating-point sum, and so the value bits, depend on the hash function; they are now merged in first-appearance order. This is the one change that is not bit-identical to games recorded before it: near-ties can resolve the other way, so the earlier cohorts stand as recorded with their binary digests and are not replayable move for move by the new binary.

Three tables, three lifetimes. The turn plans (the static best line of a position, independent of depth), the lookahead values (keyed by position, level, and depth cap, since a value depends on how many more turns are planned below it), and the arrival positions of an opponents' round (keyed by position and level). With cache: none they are rebuilt for every depth pass, as before. With decision they are shared across the passes of one decision, so iterative deepening replans a turn and replays a round once. With turn they persist across the decisions of a turn, so after a move the next decision starts inside a subtree the previous one explored.

What is and is not identical. Shared tables within a decision reproduce the fresh search bit for bit whenever no node or time budget binds; a test walks forty decisions of a game and checks every candidate's value bits. Under a binding budget the cached search completes more of the tree. The turn-persistent tables reuse values computed under the earlier decisions' sampled hands, an equally valid estimate but not the same bits, which is why their comparison is a strength cohort rather than an identity check.

The registered comparisons

Equal nodes: identity and speed

Runs a278a790 (fresh tables) and e02cf22e (shared tables) played the same lineup, the learned-leaf search at depth 3 with no time budget and a node budget that never binds beside an ETA, a fast, and an ETA builder, on seeds 668 to 699 in every rotation. All 128 games are identical in winner, turns, points, and action count (comparison record). The shared tables decided in 654 ms against 741 ms per decision, 11.7% less, with 16% fewer transitions (79,813 against 94,781 per decision). The registered rule asked for identity and at least 15% less time: identity is supported, the speed part is not met. At depth 3 the passes that can be reused, the depth-1 turn plans and the depth-2 opponents' round, are a small share of the depth-3 pass, which plans a whole second turn under every scenario; the saving is real but bounded by that share.

Equal time: do turn tables buy strength?

Run 392cc1bc seated the learned-leaf search at depth 3 under 1.5 s with tables kept across the decisions of a turn in slot 0 and the same search with fresh tables in slot 1, with an ETA and a fast builder, on seeds 700 to 763: 107 wins to 115, a contrast of −0.031 (95% interval −0.145 to +0.082), inconclusive. The turn tables decided in 368 ms against 434 ms (15% less) with 19% fewer transitions per decision (47,068 against 58,170), and both seats completed the same depth on average (2.23 against 2.20) and aborted the same share of attempts (9% against 10%). The saved time did not turn into depth, because deepening past a completed depth 3 has nowhere to go under a cap of 3, and the time rule already stopped most attempts at the fourth pass; it turned into faster decisions of the same quality.

The protocol cohort

ntuple-leaf-tt against ntuple-leaf with the two builders through the authoritative server on seeds 764 to 783 (77be5dcd, run bd18246c, all 80 games valid, no timeout moves): 27 wins to 36, contrast −0.113 (95% interval −0.265 to +0.040). The interval crosses zero, so the registered rule leaves the baseline at ntuple-leaf. Twenty seeds cannot separate a small loss from none; the engine cohort on 64 seeds saw no difference either way.

What this settles

The transpositions the game offers are real and the search now catches them correctly and verifiably, with less work: the same decisions from about 12% less time at equal nodes, and the same completed depth from about 15% less time under a clock. What the tables do not do, in this search, is convert saved time into strength. The depth-3 pass plans a whole second turn under every scenario and dominates the cost, and iterative deepening under the 30% time rule rarely has a fourth pass to spend the saving on. The cheaper key and the per-turn tables are kept as defaults for training, where the state is fully known and the reuse is exact; for seated play the mode stays a configuration choice, and the baseline configuration is unchanged.

The remaining cost lever is inside the depth-3 pass: the opponents' round simulates every scenario from every afterstate of the chosen line, and its arrivals are now cached per afterstate, so the next step is sharing arrivals across afterstates that differ only in the player's own hand, which the builders never read.