Gumbel AlphaZero search design

Status: implemented in crates/dl-manaka-core/src/search/.

DLManaka uses Gumbel AlphaZero MCTS both to choose moves and to produce improved policy targets for self-play training.

Why Gumbel

Plain policy argmax has no lookahead, while ordinary PUCT usually needs a large visit budget before visit counts become a useful training target. Gumbel AlphaZero is designed to produce a policy-improvement target even at small simulation counts.

The implementation follows Danihelka et al., Policy Improvement by Planning with Gumbel (ICLR 2022), cross-checked against DeepMind's mctx.

Core quantities

A search node stores policy logits, network value and edge statistics. Values are always from an explicitly defined player perspective; backup flips sign once per traversed edge.

Search results are mixed into policy logits with

sigma(q) = (c_visit + max_b N(b)) * c_scale * q

using c_visit = 50, c_scale = 1.0 and no min-max rescaling.

Unvisited moves receive a completed Q estimate based on the node's raw value and the prior-weighted Q of visited moves. With zero visits it reduces to the raw network value. If the visited prior mass underflows to zero, the implementation falls back to an unweighted average rather than dividing by zero.

Root selection

Gumbel noise is drawn once per legal move at the start of the search and reused throughout that search.

The root combines:

gumbel + logit + sigma(Q)

with a Sequential Halving visit schedule. Candidate elimination is represented by visit-count eligibility rather than a second explicit survivor set.

The default configuration is historically centered on:

simulations = 32
max_considered = 16
c_visit = 50
c_scale = 1

Production/self-play configs may override these values; do not copy the defaults into measurement claims.

Below the root

Non-root selection is deterministic. It follows the improved policy implied by logit + sigma(completedQ) while favoring moves whose visits lag their target share.

Gumbel randomness is root-only.

Final move and training target

The training target is

improved_policy = softmax(logit + sigma(completedQ))

over legal moves.

It is not a softmax of visit counts. Replacing it with a conventional AlphaZero visit-count target changes the algorithm's training semantics.

The played move is selected from the maximally visited root moves using the same root score. It therefore need not equal argmax(improved_policy).

root_value is defined as the value expectation under the improved policy. root_v_hat is kept separately as the pre-search network opinion.

Batched search

batched.rs collects several descents and evaluates their leaves in one GPU call. If multiple descents reach the same leaf, that leaf is evaluated once and the result is backed up along all queued paths.

Two invariants matter:

1. batch_size = 1 must reproduce sequential search exactly.
2. Batch width must not be increased independently of the simulation budget. Wide batches can make many descents collide on queued leaves, reducing distinct nodes and PV depth even while raw inference throughput rises.

Virtual loss is used while a leaf is waiting for evaluation so later descents spread to other branches. Evaluation caching may reuse network outputs for transpositions, but tree/visit statistics remain node-local.

Exact rule handling

• Root mate-in-one: checked before MCTS; if present, return it without network inference.
• Terminal leaf: no legal moves means mate and value -1 for the side to move.
• Repetition: handled by the game loop, not inside each search node.
• Depth cap: a memory/time safety cap, not repetition detection.
• Entering-king declaration: not currently handled by the search.

USI behavior

dl-manaka-usi exposes search options such as simulations, batch size, virtual loss and policy-only mode. go depth, go nodes and go movetime can cut off game search.

Self-play teacher generation should spend the full precomputed Sequential Halving schedule; a mid-search cutoff biases the improved policy.

Evaluation games use gumbel_scale = 0. Self-play uses non-zero Gumbel noise so repeated games explore different root candidate sets.

Clock allocation from btime / wtime / byoyomi is not yet a general time-management policy, and stop is not currently an interruptible-search mechanism.

Code map

file	role
gumbel.rs	sigma, completed Q, selection rules
halving.rs	Sequential Halving schedule
tree.rs	nodes, edges, backup
sequential.rs	one-leaf-at-a-time search
batched.rs	batched descents/evaluation
result.rs	common result readout

Verification

Tests cover the failure modes that are easiest to implement incorrectly:

• sign flips through a multi-edge backup;
• hand-computed completed-Q values;
• exact root mate-in-one even when policy dislikes the move;
• numerical stability at hundreds of simulations;
• batch-1 equality with sequential search;
• regression positions where one-ply lookahead must reject a policy blunder.

For measured effects of search depth and batching, see the self-play plateau record and benchmarks.