Depth-Width type criteria approbation for tree shape control for the Monte Carlo Tree search method
DOI:
https://doi.org/10.20535/2786-8729.5.2024.317209Keywords:
depth-width type criteria, Monte Carlo tree search method, MCTS, MCTS-UCT, MCTS-TSC, search tree shape controlAbstract
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 proposed
MCTS-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.
References
C. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, et al., “A Survey of Monte Carlo Tree Search Methods”, IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, pp. 1–43, March 2012. https://doi.org/10.1109/TCIAIG.2012.2186810.
M. Kemmerling, D. Lütticke, and R. H. Schmitt, “Beyond games: a systematic review of neural Monte Carlo tree search Applications”, Applied Intelligence, vol.54, pp. 1020–1046, 2024. https://doi.org/10.1007/s10489-023-05240-w.
J. Jooken, P. Leyman, T. Wauters, and P. De Causmaecker, “Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems”, Computers & Operations Research, ISSN: 0305-0548, vol. 150, pp. 1–46, 2023. https://doi.org/10.1016/j.cor.2022.106070.
T. Ou, Y. Lu, X. Wu, and J. Cao, “Monte Carlo Tree Search: A Survey of Theories and Applications”, 2022 3rd International Conference on Big Data, Artificial Intelligence and Internet of Things Engineering (ICBAIE), Xi’an, China, pp. 388–396, 2022. https://doi.org/10.1109/ICBAIE56435.2022.9985899.
E. Steinmetz, “More Trees or Larger Trees: Parallelizing Monte Carlo Tree Search”, IEEE Transactions on Games, vol. 13, no. 3, pp.315–320, September 2021. https://doi.org/10.1109/TG.2020.3048331.
H. Finnsson and Y. Björnsson, “Game-Tree Properties and MCTS Performance”, GIGA 2011: Proceedings of the 2nd International General Game Playing Workshop, pp. 23–30, Jan. 2011. Available: http://surl.li/hlmyrs. Accessed on: Dec 05, 2024.
J. Veness, K. Siong Ng, M. Hutter, W. Uther, and D. Silver, “A Monte-Carlo AIXI Approximation”, Journal of Artificial Intelligence Research, ISSN:1076-9757, vol. 40, no. 1, pp. 95–142, January 2011. Available: https://dl.acm.org/doi/abs/10.5555/2016945.2016949. Accessed on: Dec 05, 2024.
R. Ramanujan and B. Selman, “Trade-offs in sampling-based adversarial planning”, Proc. 21st Int. Conf. Automat. Plan. Sched., Freiburg, Germany, pp. 202–209, June 2011. https://doi.org/10.1609/icaps.v21i1.13472.
O. I. Marchenko and O. O. Marchenko, “Monte-Carlo tree search with tree shape control”, 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), Kyiv, Ukraine, pp. 812–817, 2017. https://doi.org/10.1109/UKRCON.2017.8100358.
O. O. Marchenko, “Further development of the Monte Carlo tree search method by controlling the search tree shape”, Computer-Integrated Technologies: Education, Science, Production,
№ 56, pp. 213–219, 2024. https://doi.org/10.36910/6775-2524-0560-2024-56-27.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Information, Computing and Intelligent systems
This work is licensed under a Creative Commons Attribution 4.0 International License.
