Analysis of MCTS search tree shape control using "depth-width" kind criteria

Abstract

This article examines the verification and analysis of ability of the MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control) improving technique, which was developed by the authors earlier, to perform such control. The principle of controlling the shape of the search tree in the MCTS-TSC technique is based on the application of DW (Depth-Width) criteria of the "depth-width" kind. The ability of the MCTS-TSC to control and correct the shape of the search tree during its construction was tested on multiple games of Connect Four played by players which used both the standard Monte Carlo tree search technique called MCTS-UCT (Monte-Carlo Tree Search with Upper Confidence bounds applied to Trees) and the MCTS-TSC technique with control of the tree shape. In order to compare the search tree construction process by the standard MCTS-UCT technique and the MCTS-TSC tree shape control technique, trees were obtained after performing the same number of iterations of the search process and with different setting values parameters of the DW kind criteria for controlling the shape of trees during their construction. After that, statistics of the constructed search trees shape were collected and comparative analysis of the constructed search trees shapes and differences in the process of their construction by both search techniques was performed. The approbation and analysis of the shape of the built search trees showed that the MCTS-TSC technique of tree search by controlling the shape of the  tree based on setting certain parameters of the formulas of the "depth-width" kind criteria, without changing the general asymmetric principle of building the search tree, allows you to direct the process of this construction to a wider and shallow tree shape, or to a narrower and deeper shape. The obtained results confirm the ability of the MCTS-TSC technique to control the shape of the MCTS search tree using depth-width criteria