Method of the MCTS Tree Search Method Parallelization

Abstract

The method proposed in this article is based on two directions of further development of Monte Carlo tree search method (MCTS): the direction of improving the theoretical approaches of this method and the direction of parallelization of the search process by this method. Parallelization of MCTS search is performed on the basis of previously proposed author's variant MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control) with search tree shape control, a generalized graph-structural heterogeneous model of dynamic parallelization of Monte Carlo tree search, as well as a resource model of a heterogeneous distributed computer system with local connections and its graph. The proposed parallelization method takes into account all three known MCTS hardware-independent parallelization methods: root, tree, and leaf parallelization and consists of seven stages. The fundamental difference between the proposed method and the methods of other researchers is a more intelligent decision-making about the type of parallelization and the degree of parallelization at the vertices of the search tree at stages 1-3, which is made both on the basis of available hardware resources and on the basis of the current shape of the search tree in order to direct further building a tree in the desired direction (in depth or width), while other researchers, as a rule, perform only the implementation of root parallelization between several computers, which is strictly tied to a specific configuration of the computer system, the implementation of tree parallelization or implementation of leaf parallelization on GPU boards. The proposed method of MCTS search parallelization ensures more efficient loading of available hardware resources and allows both speeding up the search process as a whole and increasing the efficiency of MCTS search.