Backpropagation (MCTS Phase)

The visit count is a fundamental statistic incremented for each node along the backpropagation path. It represents the total number of times a node has been traversed during the selection phase.

• Purpose: Directly influences the exploration term in the UCT formula. Nodes with lower visit counts are incentivized for future exploration.
• Update Rule: For each node in the path, N(s, a) ← N(s, a) + 1, where s is the state and a is the action taken to reach the child node.
• Significance: A high visit count indicates a node is frequently considered promising, while a low count suggests it is under-explored.

The total action value (or cumulative reward) Q(s, a) is updated by adding the simulation's outcome (e.g., win=1, loss=0, or a scalar reward) to a running sum.

• Purpose: Provides an empirical estimate of the expected reward for taking action a from state s.
• Update Rule: Q(s, a) ← Q(s, a) + v, where v is the result (reward) propagated from the terminal state of the simulation.
• Derived Metric: The mean action value Q(s, a) / N(s, a) is the primary metric for exploitation, representing the average success rate of that action.

While not stored directly, the mean action value is the critical derived statistic calculated as Q(s, a) / N(s, a). It represents the average reward obtained from all simulations that passed through that node.

• Role in UCT: Serves as the exploitation component. The UCT formula Q/N + c * sqrt(ln(N(parent)) / N) balances this known value against the exploration bonus.
• Interpretation: In a win/loss game, a mean value of 0.75 suggests a 75% win rate from that state-action pair based on current search knowledge.

Virtual loss is a temporary statistic used in tree-parallel MCTS to manage contention between threads exploring the same tree.

• Mechanism: When a thread selects a node for expansion/simulation, it immediately adds a virtual loss (e.g., +1 to visit count, -1 to total value) to that node's statistics.
• Purpose: This artificially makes the node look less attractive to other threads, encouraging them to explore different branches and parallelize the search efficiently.
• Reversal: The virtual loss is subtracted from the statistics during the subsequent backpropagation phase, leaving only the real result from the simulation.

Rapid Action Value Estimation (RAVE) maintains a separate set of statistics that are updated more aggressively during backpropagation to accelerate learning.

• Core Idea: For a given action a, RAVE updates the value Q_RAVE(a) in every node encountered during backpropagation where action a was taken anywhere in the subsequent subtree, not just on the specific path.
• Update Rule: If action a appears in the simulation, its RAVE visit count N_RAVE(a) and total value Q_RAVE(a) are updated in all ancestor nodes.
• Benefit: Provides a faster, coarser value estimate, especially valuable in the early search when standard Q statistics are sparse.

In neural MCTS architectures like AlphaZero, each node stores a prior probability P(s, a) predicted by a policy network. This statistic is not updated during standard backpropagation.

• Source: Set once during the expansion phase when a new node is created, based on the neural network's output.
• Role in UCT: The prior is used in a modified selection formula: Q/N + U(s, a), where U(s, a) ∝ P(s, a) * sqrt(N(parent)) / (1 + N(s, a)). It guides exploration towards moves the network deems promising.
• Key Distinction: Unlike Q and N, the prior P is static for the duration of the search tree's lifetime for a given state.

The visit count is a core statistic stored in each node of an MCTS tree, incrementing each time the node is traversed during the selection phase. It serves two critical functions:

• Exploration Guide: In policies like UCT, the visit count inversely weights the exploration term, directing the search toward less-sampled parts of the tree.
• Action Selection: After the search concludes, the child node of the root with the highest visit count is typically chosen as the best action, as it represents the most thoroughly evaluated option. During backpropagation, the visit count for every node on the traversed path is incremented by one, solidifying its exploration history.

Upper Confidence Bound for Trees (UCT) is the canonical tree policy used during the selection phase to navigate from the root to a leaf node. It formalizes the exploration-exploitation tradeoff by calculating a score for each child node: UCT = Q(s,a) + c * sqrt( ln(N(s)) / N(s,a) )

• Q(s,a): The average reward (exploitation term).
• c: A tunable exploration constant.
• N(s): The parent node's visit count.
• N(s,a): The child node's visit count (exploration term). Backpropagation is what makes UCT work; it updates the Q(s,a) value (the cumulative/average reward) and the N(s,a) count for each node, allowing the policy to make increasingly informed selections in future iterations.

Selection is the first phase of an MCTS iteration, where the algorithm traverses the existing tree from the root node to a leaf node. This traversal is governed by a tree policy, most commonly UCT.

• The path taken during selection is the exact path that will later be updated during backpropagation.
• The process continues until a node is reached that is not fully expanded (i.e., has untried actions) or is a terminal state. This phase is fundamentally linked to backpropagation; the statistics of every node selected in this descent are the ones that will be revised with the simulation's result.

Neural Monte Carlo Tree Search is a hybrid architecture that integrates deep neural networks into the classic MCTS loop, as pioneered by AlphaGo and AlphaZero. The neural networks provide learned, high-quality guidance:

• A policy network suggests promising actions during the expansion phase, replacing uniform random expansion.
• A value network estimates the game outcome from a given state, providing an alternative to a full random simulation. In this framework, backpropagation updates node statistics with a combined value from the neural network evaluation and the result of any subsequent rollout, blending learned intuition with empirical simulation results.

Virtual loss is a parallelization technique for MCTS used when multiple threads share a single, global search tree (tree parallelization). To prevent threads from redundantly exploring the same path simultaneously, a temporary penalty is applied.

• When a thread selects a node during the selection phase, it immediately adds a virtual loss (e.g., +1 to the visit count, -1 to the total reward) to that node's statistics.
• This artificially makes the node look less attractive to other threads, encouraging them to explore different branches.
• During backpropagation, the thread removes the virtual loss and applies the actual result of its simulation. This synchronization mechanism is managed entirely within the backpropagation logic.

The principal variation (PV) is the sequence of moves considered optimal for both players from the current root state. In MCTS, it is not pre-calculated but emerges from the search statistics.

• After MCTS concludes, the PV is extracted by starting at the root and repeatedly selecting the child node with the highest visit count or the highest average reward.
• Backpropagation is what creates the data to identify the PV. By updating visit counts and cumulative rewards, it highlights which paths yielded the most favorable outcomes over many simulations.
• The PV represents the "best line" of play found by the search and is a key output for analysis and move selection.