Апробація критеріїв типу глибина-ширина для контролю форми дерева для пошуку в дереві методом Mонте Карло

This paper is devoted to the scientific problem of improvements of the Monte Carlo Tree Search (MCTS) method. The object of research is the process of performing a tree search using the MCTS. The subject of research is the MCST improvement technique with control of the search tree shape by usage of the previously proposed be the authors DWC (Depth/Width Criterion) and WDC (Width/Depth Criterion) criteria. This technique was named Monte Carlo Tree Search with Tree Shape Control (MCTS-TSC). The research methods are based on the theory of data structures and analysis methods. The aim of the study is to conduct extended study of the previously proposed MCTS-TSC technique for improvement of the MCTS method. In particular, the aim is to approve that the DWC and WDC tree shape control criteria ensure the better move selection and increasing player strength compared to the standard Monte Carlo Tree Search with Upper Confidence bounds applied to Trees (MCTS-UCT) technique. To achieve the aim, the following tasks were set: to conduct a set of experiments according to the developed approbation methodology to approve that the WDC criterion of the MCTS-TSC technique is able to improve the MCTS method; to conduct a set of experiments according to the developed approbation methodology to approve that the DWC criterion of the MCTS-TSC technique is able to improve the MCTS method. Both WDC and DWC criteria of the MCTS-TSC technique were tested on a series of games of Connect Four between a player, which used the MCTS-TSC technique, and a player which used the MCTS-UCT technique. Different parameters for tuning the formulas of the WDC and DWC criteria of the MCTS-TSC technique were used in the experiments. The paper describes the methodology of the approbation of the MCTS-TSC technique with usage of the WDC and DWC criteria compared to the MCTS-UCT technique and conducts comparative analysis of the results of the experiments. The MCTS-TSC player won from 30% to 70% more games than the MCTS-UCT player for some search tree shapes, when WDC criterion was used, and from 19% to 52% more games, when DWC criterion was used. So, ability of the proposedMCTS-TSC technique to improve the MCTS method was approved for both criteria, WDC and DWC. Key words: depth-width type criteria, Monte Carlo tree search method, MCTS, MCTS-UCT, MCTS-TSC, search tree shape control.