# Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics
## 3 Monte Carlo Tree Search Algorithm  
Monte Carlo Tree Search algorithm consists of four phases which are iterated for a determined number of times: selection, expansion, simulation and backpropagation. The higher number of iterations, the more the tree grows and the easier is for the results to converge to a meaningful one. A root node must be provided for starting the iterations. The number of iterations will be an important variable in our experiments. * Selection phase. First, the root node goes through selection phase (Figure 2 and Algorithm 1), where a node is selected based on the biggest Upper Confidence Bounds (UCB) formula value [14]. UCB formula tries to balance exploitation and exploration of the tree thanks to its constant \(C\). This value, according to [PERSON] et al. [14], accomplishes that balance. The way of managing the analysis of a node is characterized by exploitation and exploration. Exploitation of the tree nodes refers to grow the tree in depth from a promising node, while exploration refers to grow the tree in width checking unvisited nodes. UCB formula is composed by two terms which influence the trend of MCTS about exploring or exploiting nodes. We can control and balance it with constant \(C\) (the bigger, the more expanded nodes) considering the needed information and computational cost. The adjusted value of \(C\) is 1.41 [28]. Figure 1: Dots and Boxes game between two players. Figure 2: Selection phase in MCTS. ```
functionselection(node) while node has children do  node = child of node with biggest UCB endwhilereturn node endfunction
```  
**Algorithm 1** Selection phase  
```
``` functionexpansion(node) if is node visited then  generate children of node endif endfunction
```

**Algorithm 2** Expansion phase

Simulation phase. In simulation phase (Figure 4 and Algorithm 3) if selected node is expanded, a random child is taken, else the selected node is taken itself. Then, next states are randomly chosen until it reaches a terminal state. Besides the random technique, it can be used with improved systems. This will be studied in Section 3.1. Figure 3: Expansion phase in MCTS. * Backpropagation phase. In backpropagation phase (Figure 5 and Algorithm 4), the value obtained at simulation phase is propagated from leaves to root of the tree updating the values of the nodes: visits and victories. Figure 4: Simulation phase in MCTS. Figure 5: Backpropagation phase in MCTS. ### MCTS and Neural Networks

MCTS simulation phase is characterized by randomness that is optimized focusing on converging the simulations using approaches based on artificial intelligence. AlphaGo is one of the most successful systems that implement this technique, according to [PERSON] et al. [18] it integrates two neural networks in simulation phase:

* Policy network is used to predict if a move corresponds to an expert human move. It was trained with human moves data sets and considers the previous state and the final state after the move. Its output is a probability of belonging to the mentioned data set. * Value network is used to predict the probability of winning given a certain state. It was trained with game states result of playing again itself, choosing each move with the help of the policy network. According to [PERSON] et al. [18], policy network is applied after the expansion of a node \(N_{0}\) over every new node \(N_{i}\). Predicting the probability of move \(N_{0}\to N_{i}\) of being an expert human move. That probability is stored on that node, which will be used on selection phase combined with UCB value to select next node. Value network is applied to the node to be simulated and its prediction is combined with the result of the random simulation giving a final value used to update the tree in backpropagation. [PERSON] [2] suggests a simpler way to use value network: to predict the winner at the beginning of simulation phase, if the result is consistent enough, take that value and jump to backpropagation phase, else perform random simulation. We implement this approximation to build our system.