# Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics
## 3 Monte Carlo Tree Search Algorithm
Therefore, we add another counter, this way we have one for saving P1 results and the other for P2 results. When calculating the UCB value for each node, we took the difference between both counters and change the sign, being positive if it is a good option and negative if it is a bad option depending on the current player turn. If it is the turn of Player 1, we do not touch that value, but if it is the turn of Player 2, we place the opposite sign. \[\widehat{X}_{j}=\ \frac{abs(counter_{P1}-counter_{P2})}{n_{j}} \tag{3}\]

Also, if there are several nodes with the same greatest value the system takes a list with all of them and picks one randomly. ### Artificial Neural Network Configuration

One of the objectives of this study is the generalization of the problem. So, we are generating our own data sets to train the artificial neural network by making the system play against itself. This MCTS implementation is configured with an important number of iterations to get good games minimizing incoherent moves. To balance response time and good results, we considered experimentally 100,000 iterations. That number is big enough to reduce meaningless moves and small enough to let us generate games in a reasonable time. The ANN trains over the moves of the Dots and Boxes board obtained with the previous methodology. The boards are parsed into an array of 85 doubles distinguishing between free and occupied positions (we do not differentiate between moves done by P1 or P2 because the resolution of the game does not depend on who does which move but on the closing of boxes), boxes closed by P1, boxes closed by P2 and free boxes. Table 2 represents all values involved in board, their meaning in the game, their value on the board and their normalized value in the input array of the ANN. 115,000 games are used to train this ANN. Artificial neural network configuration is described in Figure 6. It is composed by three layers with 85, 100 and 3 neurons, respectively. Number of neurons of first layer must be the same as the input array size. According to our experiments 100 neurons on layer 2 are effective. Sigmoid activation function (AF) has been proved to be effective in layers 2 and 3. The output is a set of the probabilities of P1 and P2 winning the game and ending on draw. This ANN is applied in simulation phase in MCTS as shown in Figure 7 and Algorithm 5. Before starting that step, the ANN is called over the node to be simulated, if it returns a probability over a threshold to be determined, it jumps to backpropagation with this win, draw or defeat value, else continues with the random simulation. ``` functionsimulation(node) while node state is not final do  probability = ANN(node state) if probability >= threshold then return node state endif  get next node random  node = next node endwhilereturn node state endfunction \begin{table}
\begin{tabular}{c c c} \hline \hline
**Meaning** & **Board** & **Array** \\ \hline P1 move & 1 & 0.25 \\ \hline P2 move & 2 & 0.25 \\ \hline Free position & 0 & 0.0 \\ \hline Box closed by P1 & 3 & 0.5 \\ \hline Box closed by P2 & 4 & 0.75 \\ \hline Free box & 5 & 1.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Mapped values from board to neural network. Figure 6: Artificial neural network configuration.