# Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics
## 3 Monte Carlo Tree Search Algorithm
## 5 Proposal

The aim of this article is to use an algorithm which implements Monte Carlo Tree Search with neural networks in an efficient way without any domain language. The algorithm will be able to solve the Dots and Boxes game (and be able to beat the current \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Their Contribution** & **Our Contribution** \\ \hline
**[PERSON]** & The authors use an intelligent & Our approach uses MCTS. \\
**and [PERSON] [30]** & rule-based agent. & \\ \hline
**[PERSON] and** & The authors use Alpha-Beta with & Our approach uses MCTS \\
**[PERSON] [31]** & domain-based heuristics & without information \\  & such as chains and symmetries & about the game \\ \hline
**[PERSON] et al. [32]** & The authors use heuristics to & \\  & represent the board and & Our approach does not use \\  & pre-classify the nodes. They & any heuristic neither \\  & also use an auxiliary & auxiliary method. \\  & greedy policy and a different & \\  & method of data generation & \\  & (see Section 6.2.2). & \\ \hline
**[PERSON] and [PERSON] [35]** & The authors use an approach & Our approach reduces the \\  & which reduces the & search space applying an \\  & MCTS search space & ANN which can be trained \\  & considering the implemented & no matter the domain. \\  & domain-based heuristics. & \\ \hline
**[PERSON] and** & The authors focus on MCTS & Our approach does not \\
**[PERSON] [36]** & parallelization. & explore MCTS parallelization. \\ \hline
**[PERSON] et al. [38]** & The authors evaluate a network & Our approach uses an ANN \\  & based on AlphaZero against a & (see Section 5.2) \\
**[PERSON] et al. [38]** & MCTS implementation. & integrated in MCTS. \\  & They focus on generating a & \\  & good quality data set. & \\ \hline
**[PERSON] et al. [37]** & The authors propose two & Our approach proposes other \\  & implementations of MCTS & integration of ANN \\
**[PERSON] et al. [37]** & integrated with a value net and & in MCTS and with no \\  & a policy net. They use Alpha-Beta & auxiliary algorithms. \\  & as an auxiliary method. & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Contribution comparison solutions for this game) in a generic way. It will not use any heuristic based on the domain knowledge of the game that could affect MCTS algorithm. In this section we will explain our contributions to classic MCTS described in Section 3. First, we focus on the contributions to MCTS and then on the implementation of our artificial neural network. ### Monte Carlo

In MCTS, each node just uses one counter to sum up number of victories, draws and defeats. We are adding a double counter for each node to solve the problem. In selection phase, a node must be selected according to the greatest UCB value, i.e., to select the next move from the current state. The UCB formula is represented as follows:

\[UCB=\widehat{X}_{j}+2C_{p}\sqrt{\frac{2\ln(n)}{n_{j}}} \tag{1}\]

where \(\widehat{X}_{j}\) is the mean of wins resulted from node \(j\), \(n_{j}\) is the number of visits \(j\) node received, \(n\) the number of visits for the parent of the node and \(C_{p}\) is a constant. For calculating \(\widehat{X}_{j}\), we are adding a \"win\" every time node \(j\) reaches a win game status during its simulations. According to [PERSON] et al. [44] we get a better performance of this formula if the value we assign as winning or losing values in the range [0,1], i.e., normalized. Dots and boxes has three possible game ended status: victory, defeat or draw. Each node has a counter which is updated during backtracking by adding a certain value for victory, defeat or draw. \[\widehat{X}_{j}=\ \frac{unique\_counter}{n_{j}} \tag{2}\]

This value is \(\widehat{X}_{j}\) in UCB formula. If we say that the current move is for Player 1 (P1) and we use just one counter for both players, the next move (next selected node) will be chosen as the best value for P1. This is false for a game with alternative turns. The next move must be the best for the other player, Player 2 (P2) to get a meaningful set of moves.