AlphaZero Algorithm

The planning algorithm at AlphaZero's core. MCTS builds a search tree by iteratively performing four phases:

• Selection: Traverses the tree from the root to a leaf using the Upper Confidence Bound for Trees (UCT) formula.
• Expansion: Adds one or more child nodes to the selected leaf.
• Simulation (Rollout): Plays the game to termination using a fast policy (in AlphaZero, this is replaced by the neural network's value estimate).
• Backpropagation: Updates node statistics (visit count, cumulative value) along the traversed path with the simulation result. This process allows AlphaZero to evaluate millions of potential future positions from the current game state.

A single, unified convolutional neural network (CNN) with a ResNet architecture that performs two critical functions:

• Policy Head (p): Outputs a probability distribution over all possible moves from the current board position. This acts as a learned prior, guiding the MCTS search toward promising actions.
• Value Head (v): Outputs a scalar estimate of the expected game outcome (win/loss/draw) from the current position, replacing the need for a full random rollout during MCTS simulation. The network is trained via self-play data, learning to approximate the optimal value function and policy.

The training mechanism where the algorithm improves autonomously:

1. The current best network plays thousands of games against a previous version of itself.
2. Moves are selected by running an MCTS guided by the network's predictions; the move played is proportional to the root node's visit count.
3. Game outcomes become training labels.
4. The network is updated via gradient descent to minimize the error between its predictions (policy and value) and the improved targets from MCTS (visit distribution) and the final game result. This creates a closed loop of continuous improvement without human data.

The mathematical formula governing the exploration-exploitation trade-off during the MCTS selection phase. For a given node, the algorithm selects the child i that maximizes:

Q_i + c_puct * P_i * (√N_parent / (1 + N_i))

• Q_i: The average value (win rate) of that child node.
• P_i: The prior probability from the neural network's policy head.
• N_i: The visit count of the child node.
• N_parent: The visit count of the parent node.
• c_puct: A constant controlling exploration level. This balances exploiting moves with high average value (Q) and exploring moves with high prior probability (P) but low visit count (N).

A random perturbation added at the start of each self-play game to ensure diverse exploration. At the root node (the initial game state), a small amount of Dirichlet noise is added to the prior probabilities (P) output by the neural network's policy head. For example, in chess, noise sampled from Dirichlet(0.3) is mixed with the priors. This technique prevents the early games of self-play from being deterministic, encouraging the agent to try a wider variety of opening strategies and discover novel lines of play that might be superior.

The parallelized computational architecture that enables efficient scaling. AlphaZero runs multiple processes concurrently:

• Self-Play Actors: Hundreds or thousands of processes play games using the latest network parameters, generating training data (position, MCTS visit distribution, game result).
• Training Learner: A single process continuously samples batches from a replay buffer of recent self-play games and updates the neural network weights via gradient descent.
• Parameter Server: Holds the current network weights, which are periodically fetched by the self-play actors. This decoupled design allows for massive parallel data generation and continuous, stable learning.

Monte Carlo Tree Search (MCTS) is the core planning algorithm used by AlphaZero. It is a heuristic search algorithm for optimal decision-making in sequential problems. Unlike minimax search, MCTS does not require a full evaluation function. Instead, it builds a search tree by iteratively performing four phases:

• Selection: Traversing the tree from the root to a leaf node using a tree policy (like UCT).
• Expansion: Adding one or more child nodes to the selected leaf.
• Simulation (Rollout): Playing out the game from the new node to a terminal state using a fast policy.
• Backpropagation: Updating the statistics (visit count, cumulative reward) of all nodes along the traversed path with the simulation result. This process allows AlphaZero to focus its computational budget on the most promising lines of play.

Upper Confidence Bound for Trees (UCT) is the canonical selection policy used during the Selection phase of Monte Carlo Tree Search in AlphaZero. It formalizes the exploration-exploitation tradeoff. For a given node, the child node to select is chosen by maximizing a score: UCT = Q(s, a) + c * sqrt( ln(N(s)) / N(s, a) ) Where:

• Q(s, a) is the estimated action value (exploitation term).
• N(s) is the parent node's visit count.
• N(s, a) is the child node's visit count.
• c is an exploration constant. This formula, derived from the multi-armed bandit problem, ensures that promising nodes are exploited while less-visited nodes are periodically explored to avoid missing superior options.

AlphaZero uses a deep residual neural network (ResNet) as its unified evaluation and policy function. This network takes the raw board state as input and outputs two vectors:

• Policy Vector (p): A probability distribution over all possible moves, providing a prior for the MCTS search.
• Value Scalar (v): An estimate of the expected game outcome (win/loss/draw) from the current position, ranging from -1 to 1. The residual connections within the network architecture enable the training of very deep networks (dozens of layers) by mitigating the vanishing gradient problem. This deep representation is crucial for evaluating complex positional nuances in games like chess and Go without handcrafted features.

Self-play reinforcement learning is the training paradigm used by AlphaZero. The system learns exclusively by playing games against itself, starting from random play with no opening book or endgame tablebases.

1. The current best neural network plays many games against a previous version of itself.
2. Each move is selected by running an MCTS search guided by the network's predictions.
3. Games are played to completion, generating tuples of (state, MCTS policy, game result).
4. These tuples form the training dataset to update the neural network via gradient descent, minimizing the error between its predictions and the MCTS-improved policy and final outcome. This creates a positive feedback loop: a better network improves the MCTS policy, which generates better training data, leading to an even better network.

MuZero is the direct successor to AlphaZero, developed by DeepMind. While AlphaZero requires knowledge of the game's rules (the dynamics function) to simulate future states during MCTS, MuZero learns a latent dynamics model. This model, implemented by a recurrent neural network, predicts:

• The immediate reward.
• The next latent state.
• The policy and value (like AlphaZero's network). This allows MuZero to perform model-based planning with MCTS in environments where the rules are unknown, such as video games (e.g., Atari) and even real-world systems. It represents a shift from given rules to learned rules for planning.

Dirichlet noise is a critical exploration technique applied in AlphaZero's self-play games. At the beginning of each self-play game, a small amount of Dirichlet noise is added to the prior probabilities (p) output by the neural network at the root node of the MCTS tree.

• Purpose: To ensure sufficient exploration of opening moves throughout training. Without it, the first few moves of self-play games could become deterministic too quickly, limiting the diversity of training data.
• Mechanism: The noise is sampled from a Dirichlet distribution (parameterized by alpha, often 0.03 for Go, 0.3 for chess). It is interpolated with the network's prior: p' = (1 - ε) * p + ε * η, where η is the noise sample and ε is a mixing constant (e.g., 0.25). This simple addition prevents early-game overfitting and fosters robust policy development.