Neural Monte Carlo Tree Search

The dynamically constructed tree where each node represents a state and stores statistics informed by neural network evaluations. Key stored data includes:

• Visit Count (N): The number of times the node has been traversed.
• Total Action Value (W): The sum of backpropagated value network estimates or simulation results for this node.
• Mean Value (Q): Calculated as Q = W / N.
• Prior Probability (P): The policy network's prediction for the action leading to this node, stored upon expansion. The tree is not a perfect replica of the state space but a biased, growing representation focused on high-value regions as guided by the neural networks.

The Upper Confidence Bound for Trees (UCT) formula is augmented with neural network priors to guide the selection phase. The algorithm chooses the child node a that maximizes: Q(s, a) + c * P(s, a) * (sqrt(N(s)) / (1 + N(s, a))) Where:

• Q(s, a) is the mean value from previous searches (exploitation).
• P(s, a) is the prior from the policy network.
• N(s) and N(s, a) are visit counts for the parent and child.
• c is an exploration constant. This Predictor + UCT formula balances between nodes with high empirical value (Q) and nodes deemed promising by the policy network (P) but less visited.

The end-to-end learning loop that creates the policy and value networks. It is a cornerstone of systems like AlphaZero. The cycle consists of:

1. Self-Play Games: The current agent plays thousands of games against itself using Neural MCTS for decision-making.
2. Data Generation: Each move's state, the MCTS visit distribution (used as improved policy targets), and the final game result are recorded.
3. Network Training: The policy and value networks are updated via gradient descent to predict the visit distribution (policy loss) and game outcome (value loss) from the generated data.
4. Iteration: A new, improved agent is created, and the cycle repeats. This creates a virtuous cycle where better networks improve search, which generates better training data.

A technique introduced in AlphaZero to ensure robust exploration during the early moves of self-play games. It works as follows:

• Noise Injection: Before the first search from a root node (e.g., at the start of a game), Dirichlet noise η is added to the prior probabilities P(s, a) output by the policy network for the root's actions.
• Formula: The modified prior is P'(s, a) = (1 - ε) * P(s, a) + ε * η, where η ~ Dir(α) and ε is a small constant (e.g., 0.25).
• Purpose: This stochastic perturbation ensures that even moves with a near-zero initial prior probability have a chance of being explored during the first few searches, preventing the agent from prematurely locking into a narrow, suboptimal line of play.

The canonical tree policy used during the selection phase of MCTS to balance exploration and exploitation. It is the foundation upon which neural guidance is added.

• Formula: UCT(node, child) = Q(child) / N(child) + c * sqrt(ln(N(node)) / N(child)) where Q is total reward, N is visit count, and c is an exploration constant.
• Neural Integration: In Neural MCTS (e.g., AlphaZero), the UCT formula is modified to include a prior probability P(s, a) from the neural network: Q/N + c * P(s, a) * sqrt(N(parent)) / (1 + N(child)).
• Role: Ensures the tree is built efficiently by statistically prioritizing promising but under-sampled paths.

The two deep neural networks (sometimes unified) that provide the intelligent guidance replacing random rollouts in classic MCTS.

• Policy Network: P(s, a). Maps a game state s to a probability distribution over possible actions a. Provides priors to bias the MCTS tree search toward promising moves.
• Value Network: V(s). Estimates the expected outcome (win probability) from a given state s. Replaces the need for lengthy random simulations by providing a fast, learned evaluation.
• Synergy: During MCTS, the policy network guides expansion, while the value network provides an estimate during backpropagation.

A random perturbation added to the prior probabilities at the root node of the search tree during training to encourage exploration of diverse strategies.

• Purpose: Prevents early-game play from becoming deterministic and stuck in a narrow subset of openings.
• Mechanism: A small amount of noise sampled from a Dirichlet distribution (parameterized by alpha) is mixed with the policy network's prior probabilities: P(s, a) = (1 - ε) * p_a + ε * η_a, where η_a ~ Dir(α).
• Effect: Ensures that even moves with a low initial neural prior have a non-zero chance of being explored during self-play, leading to more robust policy discovery.

A parallelization technique for MCTS that temporarily penalizes a node's statistics when it is selected by a thread, reducing search overhead in multi-threaded implementations.

• Problem: In tree parallelization, multiple threads share one global tree. Without coordination, threads can waste compute by simultaneously exploring the same promising path.
• Solution: When a thread picks a node for expansion/simulation, it adds a virtual loss (e.g., +1 to visit count, -1 to total reward). This makes the node appear less attractive to other threads temporarily.
• Resolution: After the thread completes its simulation and backpropagates the real result, it removes the virtual loss. This simple mechanism dramatically improves parallel scaling for Neural MCTS.