# Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics
## 3 Monte Carlo Tree Search Algorithm
## 4 Background

Dots and Boxes problem is challenging because it has a large search space. For a \(m\times n\) board it has \(m\times(n+1)+(m+1)\times n\) edges, i.e., for a \(5\times 5\) board it has 60 edges and \(2^{60}\) state space, since any combination of movements is legal. In addition, a naive search space would generate 60! states, with many of them being duplicates reached from different configurations of the game. This makes infeasible to solve the entire game for larger grids if no specific heuristics are used. In addition, this is a special and interesting game in the sense that despite being impartial (i.e., in Dots and Boxes the possible moves does not depend on the current player), it does not use the normal play convention (i.e., in Dots and Boxes the last player to move not necessarily wins). Being a classic impartial, combinatorial game, there are many studies about the resolution of Dots and Boxes. [PERSON] et al. [25; 29] explain the game from a mathematical point of view, describing specific strategies to win the game and presenting the problem as NP-hard. [PERSON] and [PERSON] [30] describe the evolution of intelligent rule-based agent teams for the Dots and Boxes game. The authors achieve a win rate close to 40% after 3,000,000 games playing against the artificial player [PERSON]'s Dots and Boxes ([[http://dsl.ee.unsw.edu.au/dslcdrom/unsw/projects/dots/](http://dsl.ee.unsw.edu.au/dslcdrom/unsw/projects/dots/)]([http://dsl.ee.unsw.edu.au/dslcdrom/unsw/projects/dots/](http://dsl.ee.unsw.edu.au/dslcdrom/unsw/projects/dots/)) (accessed on 9 March 2020)) over a period of approximately 100,000 games. To that end, some structural information about the game space must be included with an artificial economy model. Since it is a two-player, perfect-information game, researchers try to solve the game, i.e., to discover what can happen if two players are able to play optimally. [PERSON]([[https://wilson.engr.wisc.edu/boxe/](https://wilson.engr.wisc.edu/boxe/)]([https://wilson.engr.wisc.edu/boxe/](https://wilson.engr.wisc.edu/boxe/)) (accessed on 9 March 2020)) solved the game for a 4 \(\times\) 4 board in 2020 and some partially completed 5 \(\times\) 5 games. [PERSON] and [PERSON] [31] propose a solution that is up to an order-of-magnitude faster than previous works. To achieve that, they apply Alpha-Beta minimax search and different general and problem-specific techniques (based on chains, transposition tables, symmetries and move ordering) to reduce the search space. They can solve a 4 \(\times\) 5 game, being a tie given optimal play by both players. Dots and Boxes 5 \(\times\) 5 has a 2\({}^{60}\) state space. Algorithms which tend to explore the whole search space would take a big amount of time and most of the computers may not be able to handle that computational cost. An example of this is minimax. As we explained previously, some approaches were developed to reduce the search space, such as Alpha-Beta pruning or MCTS. MCTS makes use of the number of iterations to prune the search space. Also, the introduction of ANN helps to converge the results of the simulations to partially avoid bad quality moves. [PERSON] et al. [32] presents a board presentation specifically designed to solve the Dots and Boxes game. The authors use game-specific knowledge to classify and manage 12 different types of chains and 4 categories of edges. Regarding the strategy to play, authors have used MCTS together with an Artificial Neural Network (ANN) to avoid random movements in the Monte Carlo tree. The ANN has 3 layers (input, hidden and output) with hyperbolic tangent as the activation function and an output that ranges from \(-\)1 to 1 which provides a probability of victory or defeat. For a 5 \(\times\) 5 game, the input only contains 25 elements given their specific representation of the board.