Monte Carlo Tree Search There are a few basic terms you should be clear about. This works the same way as a classic tree search. The only difference is we intelligently choose which branches to expand. Node represents a game state. Root node would be the current state of the game we're in now. Leaf node is a terminal state or a completely unexplored state that we haven't recorded any data on. You edge represents a possible action leading to another node. This could also be called a branch. Each node has a potential branch for every legal move possible in that state. The Monte Carlo tree search algorithm consists of four distinct phases first select a path a sequence of moves from the root node to the leaf node that seems promising step 2 expand the search tree by exploring one more move step 3 backup and update all edges traverse with the statistics gaming step 4 play after repeating above 1,600 times choose the best move. There are four statistics that we will store for each action/edge. Note, these are all functions of the state we're in and the action being considered: - **n** represents the number of times action a has been explored from state s. This is incremented for each node in the path every time we perform a backup. - **W** the total value of the next state. Every time we hit a leaf node, we query the neural network and look up the value of that state. On backup, we then add the leaf node's value to the W of each node on the path back to root. - **Q** the mean value of the next state. This is simply W divided by n. It is the exact same concept we learned in Q-learning. - **P** the prior probability of selecting action a. This is queried from the neural network policy head every time we hit a leaf node. Now that we know the basics, let's have an in-depth look at how to execute the Monte Carlo tree search algorithm. Our starting point is a root node, which represents the current game state. Step 1: Choose the action that maximizes Q + U. Q is the mean value of the next state, and U is a function of P and n that increases if an action hasn't been explored much relative to the other actions or if the prior probability of the action is high. Let's have a look at the equation for U. I will try to read the whole thing, but I'll go over the important parts. Recall, n is the number of times a particular state has been explored. P(s, a) is the probability of taking a particular action returned by the neural network. C_picked is a hyperparameter that controls exploration versus exploitation. This term is taken straight from the AlphaGo Zero paper, and the standard value is 1.0. Inside the square root, on top, we're summing the n across all possible branches/actions from the given state, and in the denominator is 1 + the n for the action being considered. Step 2: Continue until a leaf node is reached. The game state of the leaf node is passed into the neural network, which predicts two things: - **P**: A probability distribution for the likelihood of taking each possible move. - **V**: The value of the state for the current player. The probabilities for each possible action are attached to new edges branching from the leaf node. Step 3: Backup previous edges all the way back to the root node. Each edge that was traversed to get to the leaf node is updated as follows: - We increment **n**. - Then we add the value of the state of the leaf node to **W**. - **Q** is the total of all the values found, divided by the number of times we visited the state. In other words, the average value of the state for every single move in the game. We repeat the above 1,600 times. Then it's time for step four: **Select a move**. Now, if we're playing in a competitive match or running the evaluation phase, then choosing a move is simple. For competitive play, we want to choose deterministically—simply choose the action from the current state with the greatest **n**. However, during training, we want to add some intelligent randomness in order to encourage exploration. To make a stochastic move, we calculate the probabilities using this equation. **Tau** is a temperature parameter that controls the level of exploration, initialized to 1 at the beginning of the game and an extremely small value after a fixed number of moves. We can also add some **Dirichlet noise** to encourage further exploration. The **Dirichlet distribution** has a property that all its elements sum to one, so we can average these two Monte Carlo tree search probabilities, and they will still sum to one. Finally, after selecting the move, the new state after the selected move becomes a new root node. Retain all leaves in the search tree that stem from the chosen move, discard the rest, and continue repeating all of the above until the game is over.