Neural Monte Carlo Tree Search

A deep neural network that predicts a probability distribution over possible actions from a given game or planning state. In Neural MCTS, it serves two critical functions:

• Provides Priors: During the selection and expansion phases, the policy network's output (e.g., P(s, a)) is used as a prior probability to bias the tree search towards promising moves, replacing uniform random exploration.
• Guides Simulation: In advanced implementations like AlphaZero, the policy network can also act as a fast, learned playout policy, replacing slow random rollouts with intelligent, truncated simulations. This network is typically trained via self-play reinforcement learning to approximate the optimal move in a given position.

A deep neural network that estimates the expected outcome (e.g., win probability or cumulative reward) from a given non-terminal state. Its primary role in Neural MCTS is:

• Terminal Substitute: During the simulation phase, instead of running a full rollout to a terminal state, the value network provides an immediate estimate V(s). This drastically reduces computational cost per iteration.
• Backpropagation Signal: This estimated value is backpropagated up the tree to update node statistics, just as a final game result would be. The value network is trained to regress the outcomes observed from self-play or Monte Carlo rollouts, providing a stable, low-variance learning target.

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 seminal self-play reinforcement learning system that popularized Neural MCTS. It combines a deep residual neural network (a unified policy and value network) with MCTS to achieve superhuman performance in perfect-information board games.

• Key Innovation: Learns solely through self-play, starting from random moves with no opening books or handcrafted evaluation functions.
• Training Loop: The neural network provides prior probabilities and state evaluations to guide MCTS; MCTS outcomes then train the network.
• Impact: Demonstrated that a general-purpose algorithm could outperform decades of human-crafted expertise in Chess, Shogi, and Go.

A model-based extension of AlphaZero that learns a latent dynamics model, enabling planning with MCTS in environments where the rules are unknown.

• Core Difference: Does not require a known simulator. It learns to predict rewards, actions, and state transitions in a learned latent space.
• Architecture: Employs a representation network, a dynamics network, and a prediction network (policy/value).
• Application: Mastered both classic board games and complex video environments like Atari, purely from pixel inputs.

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.