Concepts

Test-time search by update equivalence

Search under this much hidden information had been considered so hard that DeepNash did without it. Ataraxos makes it simple by treating search as one more damped self-play update, computed for the current position only: the same objective as training, the same two reverse KL penalties, but with values estimated from a thousand rollouts instead of one trajectory. The paper calls this update equivalence.

Sampled hidden configurations fan out into rollouts for each candidate move, their values are averaged, and a tabular regularised update picks the move.

The procedure

Sample about configurations of the opponent's hidden pieces from the belief network.
Run 1,000 rollouts of depth 40, at least one for every pair of legal move and sampled configuration. The first move is forced; the remaining 39 are played by the move network for both sides.
For each legal move, average the move network's value predictions at the positions the rollouts reach: .
Play a move sampled from

with the magnet policy, the move network's own distribution, and . The closed form is a step of magnetic mirror descent.

The update can be far more aggressive than a training step for two reasons: it is tabular, so it cannot disturb the policy at any other position, and its advantage estimate is far more accurate than a single trajectory's.

What the coefficients do

The paper's Table 17 is the clearest evidence about the method. With the values used in the series (40 ply, 1,000 rollouts) the search adds about 120 Elo over the raw network, at 1.26 seconds per move on one H100, faster than human play. Shallower or fewer rollouts give less. Setting the network KL coefficient to zero is catastrophic: Elo falls to 1733, well below the network's own 2095, because the search then overfits to quirks of the move network's rollouts that do not generalise to other opponents. Dropping the magnet term costs about 40 Elo; raising to 0.05 costs about 60.

Elo of test-time search settings against a fixed reference

Elo of test-time search settings against a fixed reference
Row	Value	Low	High
network alone (no search) (0.004 s/move)	2095	2091	2100
40 ply, 1000 rollouts (series setting) (1.26 s/move)	2218	2177	2266
10 ply, 1000 rollouts (0.46 s/move)	2189	2165	2215
40 ply, 200 rollouts (0.5 s/move)	2189	2164	2216
10 ply, 200 rollouts (0.26 s/move)	2169	2153	2186
40 ply, 1000 rollouts, no magnet KL (1.26 s/move)	2174	2138	2215
40 ply, 1000 rollouts, network KL 0.05 (1.26 s/move)	2160	2124	2201
40 ply, 1000 rollouts, no network KL (1.26 s/move)	1733	1701	1761

Transcribed from Table 17 of the Ataraxos paper (95% intervals; seconds per move on one H100 in the labels), not measured here.

Why the values are opponent-independent

The rollouts are played by the move network for both sides from positions drawn from a belief trained on the same network's self-play, and the leaf values are that network's outcome predictions. So estimates the self-play action value: what the move is worth if the opponent continues to play like the self-play policy. That estimate does not change when the actual opponent is a human or a weaker bot, and the update toward it never assumes anything about that opponent. The cost of this safety is that the search cannot exploit a weak opponent's habits; the benefit is that it cannot be baited into a line that is only good against itself.

Limits

The improvement is bounded because the search mimics a single update step; more compute past the thousand rollouts does not keep paying. The authors point at knowledge-limited subgame solving as the way to a search that can use arbitrary compute. In this program the search step is implemented in the training package against the Python game class, with the counting prior standing in for the belief network until one is trained; the rollout player in the Rust search crate is the same shape with random rollouts and no networks, which is where the ladder measures the value of the belief and move networks separately.