# Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics
## 3 Monte Carlo Tree Search Algorithm
Training data for the ANN is generated randomly by generating random states in the middle of the game, applying a minimax search to find the winner when both players play in an optimal way (due to the huge search space it would be impossible to apply that technique from the start of the game). The authors also propose several problem-specific refinements such as (1) the use of UCB1-TUNED [33] instead of the common Upper Confidence bounds applied to Trees (UCT) [34]; (2) auxiliary minimax search; (3) auxiliary greedy policy; (4) exploring order for non-visited nodes; (5) pruning; (6) reusing information of parent nodes; and (7) parallelization. The authors present their implementation in an open-source software called QDab ([[http://dotsandboxes.tar.xyz/](http://dotsandboxes.tar.xyz/)]([http://dotsandboxes.tar.xyz/](http://dotsandboxes.tar.xyz/)) (accessed on 8 March 2020)). According to their tests, after turn 24 the ANN succeeds to indicate the right move with 66.8% accuracy. After 32 moves the accuracy grows up to 83.8%. QDab was tested with a high success rate against Dabble ([[https://www.mathstat.dal.ca/~jpg/dabble/](https://www.mathstat.dal.ca/~jpg/dabble/)]([https://www.mathstat.dal.ca/~jpg/dabble/](https://www.mathstat.dal.ca/~jpg/dabble/)) (accessed on 8 March 2020)) and PRsBoxes ([[http://www.dianneandpaul.net/PRsBoxes/](http://www.dianneandpaul.net/PRsBoxes/)]([http://www.dianneandpaul.net/PRsBoxes/](http://www.dianneandpaul.net/PRsBoxes/)) (accessed on 8 March 2020)). [PERSON] and [PERSON] [35] combine heuristics with MCTS to avoid MCTS simulations to reach terminal states. The authors obtain an improvement of the performance of the algorithm. [PERSON] and [PERSON] [36] explore how controlling different resources (i.e., number of simulations, number of independent learners, amount of information shared among learners, how frequently learners share information), the performance of the game may change by using a parallelized version of MCTS. [PERSON] et al. [37] use convolutional neural networks integrated with MCTS in a value and a policy net inspired by AlphaGo. [PERSON] et al. [38] applies AlphaZero algorithm to Dots and Boxes proposing a reinforcement learning method able to improve its ability to play by playing against itself in order avoid the lack of good quality sample data when training a neural network. Table 1 shows the differences between the contributions of previous studies and ours. We are comparing our approach with [PERSON] et al. work, they also play against other systems while other solutions just use their own implementations or humans for testing. In addition to the works cited, there are many other works related to how to solve the game in some aspect, although most of them focus on using game-specific rules and heuristics to take advantage of the domain knowledge. For example, [PERSON] et al. [39] work on how to design and implement the board to optimize size and processing time. [PERSON] et al. [40] design an evaluation function with parameters based on a genetic algorithm to optimize them. [PERSON] [41] gives algorithms for best play in Dots and Boxes consisting of loops and long chains. There are even variations of the game such as Narrow Misere Dots and Boxes by [PERSON] et al. [42], where the goal is to receive the minimum number of points instead of the maximum, reducing the complexity of the original problem. Although Dots and Boxes is a well-studied game, it still lacks a game records database as there may be in other classic games such as Chess or Go. Thus, [PERSON] et al. [43] propose a game records standard format based on JSON to support cross-platform applications and portability. The main difference of our work with previous proposed works is that our system can learn to play through auto-generated games without any heuristic or extra knowledge added to MCTS. For that, we user Dots and Boxes as a use case.