How nn-chess thinks: PUCT-style MCTS, sims/move, and cPuct

← back to play

Every time the nn-chess opponent picks a move, it runs a small Monte Carlo Tree Search (MCTS) rooted at the current position. The specific variant is called PUCT — "Predictor + UCT," a bandit-style action-selection rule we'll define carefully in §2. The two knobs the main page exposes, sims/move and cPuct, are both parameters of that rule. This page is a math-first walk-through of what the search does, why it does it that way, and what those two knobs actually control; the end of the page is an interactive mate-in-2 that uses your own trained networks to drive each MCTS call.

1. The shape of the search

Classical full-width minimax explores every legal move to a fixed depth and is hopeless for chess: with a branching factor around 35 and a value network costing real wall-clock time per evaluation, even depth-6 minimax dwarfs the per-move budget we have in the browser. MCTS gives up exhaustive coverage in exchange for a budget we can dial: it spends $n$ simulations exploring the tree, and the tree it builds is highly asymmetric — deep along promising lines, shallow elsewhere.

Concretely, MCTS treats the game as a tree. A node is a board position. An edge is a legal move leading from one node to another; we'll usually write an edge as a pair $(s, a)$ — "the action $a$ available at state $s$." The root is the position we're choosing a move for. A leaf is a node we haven't yet expanded — either because it's terminal (game over) or because the search hasn't spent a simulation on it yet. One "simulation" or "playout" is a single walk from root to leaf plus an evaluation and a bookkeeping pass back up the path.

The flavour of MCTS we use is the PUCT variant from AlphaGo Zero^[1] and AlphaZero^[2]. A single neural network ("the net" — one set of weights, two output heads) supplies:

• a prior policy $P(s, a)$ — a probability distribution over legal moves from $s$, produced by the policy head and normalised with softmax;
• a value $V(s) \in [-1, 1]$ — the value head's estimate of how good $s$ is for whichever side is to move at $s$.

The only terminal-reward signal the search ever sees is fixed: $+1$ if the side that just moved delivered checkmate, $-1$ if it got checkmated, $0$ for any draw. That is the only chess heuristic baked in. Everything else — piece values, tactics, positional understanding — has to come out of the network from games.

One simulation has four phases, run repeatedly for the search budget:

1. Selection. Starting at the root, descend through the tree by repeatedly picking the edge with the highest PUCT score (defined in §2) until you reach a node that's either unexpanded (we've never asked the net about it) or terminal.
2. Expansion. If the leaf is non-terminal, ask the net for $P(\cdot \mid s)$ and $V(s)$. Mask $P$ to the legal moves at $s$ and renormalise. Create one child edge per legal move and store its prior.
3. Evaluation. Use $V(s)$ as the value to back up. If the leaf is terminal, use the terminal reward instead. Classical MCTS does an actual rollout^[3] here — it plays a random or weakly-policy-driven game from the leaf to the end, and backs up the win/loss. AlphaZero showed that once you have a competent value head, the value head replaces what the rollout used to estimate; no random play is needed at all.
4. Backup. Walk back up the path you descended, incrementing visit counts and accumulating value along each edge. Because chess is zero-sum and turn-alternating, the value flips sign at every step — a position worth $+0.4$ to me is worth $-0.4$ to my opponent, who is to move one ply earlier. §3 makes this precise.

After all simulations finish, the move chosen at the root is the one with the most visits. The visit-count distribution also doubles as a policy target when the net is being trained: during AlphaZero-style self-play the policy head is regressed toward $\pi(a) \propto N(s, a)$, on the theory that the search produces an improvement over the raw prior. We're not training on this page — everything below is inference — but the same machinery feeds the training step on the main page.

2. The PUCT formula in detail

Each edge $(s, a)$ in the search tree carries four numbers we update as the search runs:

• $P(s, a)$ — the prior from the net's policy head, fixed at expansion time and not touched afterwards.
• $N(s, a)$ — visit count: the number of simulations that have descended through this edge so far.
• $W(s, a)$ — total backed-up value through this edge (the sum of the values each of those $N(s, a)$ simulations contributed on their way up).
• $Q(s, a) = W(s, a) / N(s, a)$ — the running average value of this edge. Defined to be $0$ for edges that have never been visited.

Selection at $s$ picks the legal action $a$ that maximises:

$$ \mathrm{PUCT}(s, a) \;=\; \underbrace{Q(s, a)}_{\text{exploit}} \;+\; \underbrace{c_{\text{puct}} \cdot P(s, a) \cdot \dfrac{\sqrt{N(s)}}{1 + N(s, a)}}_{\text{explore } U(s,a)} $$

where $N(s) = \sum_{a'} N(s, a')$ is the total visit count at the parent node $s$ (the sum of $N$ over all the edges leaving it). Both terms in the PUCT sum are interpretable:

• Exploit. $Q(s, a)$ is the running average outcome from this edge so far, in $[-1, 1]$ from the perspective of the side to move at $s$. If the network keeps producing side-to-move-wins signals through some edge, its $Q$ stays positive and the search gravitates there.
• Explore. $U(s, a)$ is large when (a) the prior is high — the policy head likes this move — and (b) we haven't visited it much yet. As $N(s, a) \to \infty$ for one edge, its $U$ decays as $1 / N(s, a)$ while $Q$ stays bounded; the exploration bonus eventually vanishes and selection is dominated by exploitation.

Why $\sqrt{N(s)}$ in the explore bonus? It's a heuristic choice from the AlphaGo Zero paper, loosely inspired by UCB1^[4] — the canonical exploration bonus for stochastic multi-armed bandit problems. UCB1's bonus is $\sqrt{\log N(s) / N(s, a)}$, derived from a Chernoff-style confidence bound on the empirical mean of an arm; PUCT swaps the $\log$ for a plain $\sqrt{N(s)}$ and multiplies the whole thing by the policy prior $P(s, a)$ so high-prior moves get the bulk of early exploration. The net effect: visits distribute roughly in proportion to $\sqrt{N(s)} \cdot P(s, a)$ early on (when $N(s, a)$ is small and $Q$ is noisy), then concentrate on whichever edges develop a high $Q$.

All ties on $Q + U$ are broken deterministically (high prior first, then lexicographic UCI). Search is otherwise purely deterministic once the network weights and rng seed are fixed — see the determinism test in core/mcts/mcts.test.ts.

3. The backup, with sign-flipping

During backup, the value $v$ produced at the leaf travels back up the descent path. Because chess is zero-sum and turn-alternating, adjacent plies belong to opposite players: if the leaf is worth $+0.7$ to the side to move there, the same outcome is worth $-0.7$ to its parent's mover, $+0.7$ to the grandparent's mover, and so on. So at each step up the path we negate $v$ before crediting it to the edge:

$$ v \;\leftarrow\; -v, \quad N(s, a) \mathrel{+}= 1, \quad W(s, a) \mathrel{+}= v $$

This convention keeps every $Q(s, a)$ in the tree measured from the side-to-move's perspective at $s$, which is exactly what selection needs to compare candidate moves consistently.

Terminal leaves get the same flip in disguise. If the leaf is a checkmate, the side that just moved won — so $+1$ for them, $-1$ for the side to move at the leaf (the side that's mated). Our backup convention measures everything from the side-to-move's perspective, so the value we want to push up is the second of those two — $-1$ at the leaf. The helper terminalValueForMover in core/mcts/index.ts answers from the just-moved side's perspective (because that's the convenient one for the rules module), so the search code negates it once before sending it up the path.

4. What sims/move actually controls

The sims/move slider on the main page caps the number of PUCT simulations the search runs before picking a move. A few quantitative things follow from increasing it:

• Visit distribution sharpens. In the limit $n \to \infty$, MCTS's visit-count distribution $\pi_n(a) = N(s, a) / n$ concentrates on the action that maximises the average backed-up $Q$ — the best move according to the value head as currently trained, not the move that is best in some game-theoretic ground-truth sense. (At training time, AlphaZero sampled training moves with a temperature, $\pi_T(a) \propto N(s, a)^{1/T}$, to keep the data generator exploring; we play greedy at inference, so $T = 0$ and we just take the argmax visit count.^[5])
• Forced mates become discoverable. A mate-in-$k$ from the side to move requires the search to reach a terminal mating leaf along at least one defensive subtree at every intermediate ply. With branching factor $b$ and uniform (cold- start) priors, PUCT spreads visits roughly $b$-ways at each ply, so reaching one specific terminal leaf $k$ plies down takes on the order of $b^k$ simulations before the $+1$ first propagates back to the root.^[6] In practice the search is much more efficient than this bound because PUCT clusters visits on a small subset of moves at each ply, and $Q$ shapes that clustering as soon as the first terminal leaves are touched; but the exponential is why doubling sims/move has such an outsized effect on tactical strength.
• Cost is linear in sims. Each simulation costs one forward pass of the network (in the worst case — repeated states within a single search hit an in-memory cache keyed on repetitionKey) plus a few arithmetic ops per node on the descent path. The descent path's length is bounded by however deep PUCT decides to go, which in our cold-start regime rarely passes a few plies before hitting an unexpanded leaf, so the per-simulation cost is dominated by the forward pass. Doubling sims/move therefore doubles wall-clock per move.
• Diminishing returns once the search is informed. Once the policy net has $Q$ that already orders moves well, extra sims mostly reinforce the same top edge. The interesting regime for nn-chess is the cold-start one, where doubling sims/move actually lets the terminal $+1$ from a mating line reach the root that it couldn't reach before.

5. What cPuct actually controls

$c_{\text{puct}}$ is a single scalar that determines how much weight selection puts on $U$ relative to $Q$. The two boundary cases are instructive:

• $c_{\text{puct}} \to 0$: the explore term vanishes and selection becomes "pick the edge with the highest $Q$, breaking ties on $N$, then on prior, then lexicographically." With $Q$ initialised to $0$ everywhere, every edge ties at the root on the first pass; the prior-based tiebreak picks the highest-prior move first. Once that one edge has been visited, its child's $V$ flows up and gives it a nonzero $Q$, which then beats every other edge's $Q = 0$ forever — so the search locks onto a single line and never reconsiders. Useful only after the search has already converged via a nonzero $c_{\text{puct}}$.
• $c_{\text{puct}} \to \infty$: $Q$ becomes negligible and selection picks $a = \mathrm{argmax}_a P(s, a) / (1 + N(s, a))$. This sweeps through moves roughly in prior order without ever exploiting the backed-up values. Search behaves like pure rollout-budget apportionment by the prior and never converges on the best move.

AlphaZero used $c_{\text{puct}} = 1.5$ for chess; that's the nn-chess default. The right value depends on (a) the value-head scale (ours is $\tanh$, so $Q \in [-1, 1]$) and (b) how peaked the prior is. A near-uniform prior — what you get from a cold-start net — calls for a smaller $c_{\text{puct}}$, because $U$ is then much flatter and adding more of it just spreads visits across edges $Q$ has already ranked. A very peaked prior calls for a larger $c_{\text{puct}}$ to overcome the policy's confidence when it's wrong.

Concretely on the demo below: with the cold-start nets nn-chess ships with, a value of $c_{\text{puct}}$ around $1$–$1.5$ is enough that the terminal signal from Qd7+ Kf8 Qf7# can propagate back through MCTS. Push it up to $4$ and you'll see visits scatter across many root moves and the mate becomes harder to land at low sim counts. Push it down to $0.25$ and you'll see the search lock onto whichever queen move happened to get the first above-zero $Q$.

6. Dirichlet noise (briefly)

The MCTS module supports root-only Dirichlet noise: $\tilde P(s_0, a) = (1 - \varepsilon) P(s_0, a) + \varepsilon \eta_a$ where $\eta \sim \mathrm{Dir}(\alpha)$. This is how AlphaZero forces a bit of exploration during self-play (it keeps the data generator from collapsing onto a single line). We use it in self-play games against the imitator with the standard chess values $\alpha = 0.3$, $\varepsilon = 0.25$^[7]; we do not use it during play against the user — at inference time we want the best move, not an exploration-noised one. See SELFPLAY_SEARCH in nn-chess/ui/opponent-config.ts for where this is wired in. The demo below also leaves Dirichlet noise off so the visit counts you see are pure PUCT.

7. Interactive demo: a mate-in-2 against your own nets

The walkthrough below loads your stored opponent and imitator networks from this browser's IndexedDB (the same ones the main page plays against and trains). At each position it runs MCTS with the sims-per-move and cPuct you set, and lists the top candidate moves with their $N$, $Q$, $P$, and the $U = c_{\text{puct}} \cdot P \cdot \sqrt{N(s)} / (1 + N(s, a))$ that the next simulation would add. Click any candidate row to play that move and see MCTS think about the resulting position; the demo goes up to four half-moves deep so you can walk the full forced sequence and one extra ply of slack for offline exploration.

White (the winning side) uses the opponent network; black (the defender) uses the imitator. Both have to have been initialised — if you've never visited the main page, click over there once first so the random-init weights get persisted.

A few things worth poking at:

• Crank sims/move up. At very low sims the search may not reach the mate; the visit count on d1d7 (Qd7+) may be no larger than other queen moves. Increase sims/move and watch the visit count concentrate.
• Play a non-mating move and look at the resulting $Q$. The new position should produce $Q$ values close to $0$ across candidates — the opponent's untrained value head doesn't know either side is materially ahead — but the leftover decisive lines still bias visits.
• Sweep cPuct. At $c_{\text{puct}} = 0.25$ you'll see the search lock onto one edge; at $c_{\text{puct}} = 4$ you'll see visits spread across many moves with $Q$ values barely moving from the prior order.

8. Where this lives in the code

• nn-chess/core/mcts/index.ts — the entire search. SearchResult exposes visitCounts, priorPolicy, and edgeValues ($Q$ for each root edge); the table above is rendered from those.
• nn-chess/core/opponent/index.ts — policyFromNet adapts a ChessNet to the Policy interface MCTS consumes; selectMove runs the search and applies the temperature sampler.
• nn-chess/ui/opponent-config.ts — where the production defaults for sims/move, cPuct, and Dirichlet noise live.

Footnotes & further reading

1. Silver et al., Mastering the game of Go without human knowledge, Nature 550, 354–359 (2017). Nature; the paper that introduced AlphaGo Zero and the PUCT formula we use here. ↩
2. Silver et al., A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, Science 362, 1140–1144 (2018); arXiv:1712.01815. The AlphaZero paper, which carries the same PUCT machinery over to chess (and is where the $c_{\text{puct}} = 1.5$ default comes from). ↩
3. The original MCTS line of work — Coulom (2006), Kocsis & Szepesvári (2006), and the broader UCT family — relies on these random rollouts and works without a learned value head at all. See Browne et al., A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games (2012), DOI: 10.1109/TCIAIG.2012.2186810, for the pre-AlphaGo state of the art. The Wikipedia page on MCTS walks through the rollout-based version step by step. ↩
4. Auer, Cesa-Bianchi & Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning 47, 235–256 (2002), Springer. The paper that derives UCB1. For PUCT specifically, the relevant precursor is Rosin's Multi-armed bandits with episode context (2011), Springer, which introduces the prior-weighted variant the AlphaGo Zero paper builds on. ↩
5. AlphaZero used $T = 1$ for the first $30$ plies of each self-play game (so the data generator could see varied openings) and then $T \to 0$ for the rest of the game. The SELFPLAY_TEMPERATURE_PLIES constant in nn-chess/ui/opponent-config.ts follows the same convention. nn-chess's self-play uses $T = 1$ during that opening window and greedy after; the human-play opponent is always greedy. ↩
6. This is a very loose worst-case bound. With a uniform prior and no value-head signal, a fresh search has nothing to push visits one way or the other, so all $b^k$ leaves $k$ plies down are roughly equally likely to be reached first. As soon as a few terminal leaves are reached, the resulting $+1$/$-1$ values flow up through $Q$ and bias selection sharply, which is why the empirical sims-to-mate is much smaller than $b^k$ in practice. ↩
7. Dirichlet noise is applied only at the root and never inside the tree. Adding it deeper would corrupt the recursive structure of $Q$ — child evaluations would no longer be reusable for selection at the same state in a future simulation, because the priors that determined their visit counts would have been different. Restricting noise to the root keeps the per-state tree consistent while still letting the data generator wander across distinct opening choices. ↩