Depth-width type criteria approbation for tree shape control for the Monte Carlo tree search method

Скорочена інформація про документ
dc.contributor.authorMarchenko, Oleksii
dc.contributor.authorMarchenko, Oleksandr
dc.date.accessioned2025-04-16T11:34:11Z
dc.date.available2025-04-16T11:34:11Z
dc.date.issued2024
dc.description.abstractThis 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.
dc.description.abstractotherЦя стаття присвячена науковій проблемі вдосконалення пошуку по дереву методом Монте-Карло (Monte Carlo Tree Search, MCTS). Об’єктом дослідження є процес виконання пошуку по дереву за допомогою MCTS. Предметом дослідження є спосіб вдосконалення MCST з керуванням формою дерева пошуку шляхом використання раніше запропонованих авторами критеріїв DWC (Depth/Width Criterion) та WDC (Width/Depth Criterion). Цей спосіб отримав назву MCTS-TSC (Monte Carlo Tree Search with Tree Shape Control). Методи дослідження базуються на теорії структур даних і методах аналізу. Метою роботи є проведення розширеної експериментальної апробації способу MCTS-TSC, що вдосконалює метод MCTS. Зокрема, мета полягає у підтвердженні того, що критерії контролю форми дерева DWC і WDC забезпечують вибір кращого ходу та збільшення сили гравця порівняно зі стандартним способом реалізації методу MCTS – MCTS-UCT (Monte Carlo Tree Search with Upper Confidence bounds applied to Trees). Для досягнення мети були поставлені наступні завдання: згідно з розробленою методикою апробації провести серію експериментів для підтвердження, що критерій WDC способу MCTS-TSC здатен вдосконалити пошук методом MCTS; згідно з розробленою методикою апробації провести серію експериментів для підтвердження, що критерій DWC способу MCTS-TSC здатен вдосконалити пошук методом MCTS. Обидва критерії, WDC та DWC, способу MCTS-TSC були протестовані на серії партій гри Connect Four між гравцем, який використовував спосіб MCTS-TSC, і гравцем, який використовував спосіб MCTS-UCT. В експериментах були використані різні параметри налаштування формул критеріїв WDC і DWC способу MCTS-TSC. У статті описана методика апробації способу MCTS-TSC порівняно зі способом MCTS-UCT, а також виконаний порівняльний аналіз результатів експериментів. Для деяких форм дерева пошуку, у випадку використання критерію WDC, гравець MCTS-TSC виграв від 30% до 70% більше ігор, ніж гравець MCTS-UCT, і виграв від 19% до 52% більше ігор у випадку використання критерію DWC. Отже, ефективність запропонованого способу MCTS-TSC для вдосконалення методу MCTS була підтверджена для обох критеріїв WDC і DWC.
dc.format.pagerangePp. 80-89
dc.identifier.citationMarchenko, O. Depth-width type criteria approbation for tree shape control for the Monte Carlo tree search method / Oleksii Marchenko, Oleksandr Marchenko // Information, Computing and Intelligent systems. – 2024. – No. 5. – Pp. 80-89. – Bibliogr.: 10 ref.
dc.identifier.doihttps://doi.org/10.20535.2786-8729.5.2024/317209
dc.identifier.orcid0000-0002-5080-4811
dc.identifier.orcid0000-0002-4537-3420
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/73393
dc.language.isoen
dc.publisherNational Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
dc.publisher.placeKyiv
dc.relation.ispartofInformation, Computing and Intelligent systems, No.5
dc.subjectdepth-width type criteria
dc.subjectMonte Carlo tree search method
dc.subjectMCTS
dc.subjectMCTS-UCT
dc.subjectMCTS-TSC
dc.subjectsearch tree shape control
dc.subjectкритерії типу глибина-ширина
dc.subjectпошук в дереві методом Монте-Карло
dc.subjectконтроль форми дерева пошуку
dc.subject.udc004.02
dc.titleDepth-width type criteria approbation for tree shape control for the Monte Carlo tree search method
dc.typeArticle

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
80-89.pdf
Розмір:
895.8 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information, Computing and Intelligent systems, No. 5