Further development of the Monte Carlo tree search method by controlling the search tree shape

Abstract

Representing the information of a certain problem in the form of a tree and searching for the best solutions within this problem with the construction of a decision tree by the Monte Carlo method, which was named MCTS (Monte Carlo Tree Search), is one of the best approaches for performing a search for solving problems in which finding the best solutions is a very difficult and time-consuming process. The article is devoted to the previously proposed variant of further development of the tree search by the MCTS method by means of controlling the shape of the search tree. This variant was named MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control) and is based on the DW (Depth-Width) kind criteria in order to control the shape of the search tree during its construction. The article proposes two new DW kind criteria: DWC and WDC, the principle of which affects the shape of the search tree in a different way from the previously proposed criteria. Approbation of the use of the new proposed tree shape control criteria DWC and WDC showed an increase in the efficiency of searching for the best subsequent moves of the player who used the MCTS-TSC search variant with tree shape control compared to the player who used the standard MCTS-UCT search variant. The MCTS-TSC player won 55% more games than the MCTS-UCT player when using the DWC criterion, and 42% more when using the WDC criterion, which is significantly better than the previously proposed criteria showed. As conclusions, it is stated that since the formulas for calculating the criteria of the DW kind are simple, their implementation for controlling the shape of the tree will not significantly affect the search time of the MCTS-TSC variant. In addition, it was noted that the proposed new DW kind criteria can also be used for more efficient parallelization of the MCTS search process and more efficient use of available hardware resources. Possible directions for the further development of the MCTS-TSC search using the Monte Carlo method with the control of the of the  search tree shape  are also proposed.