Подальший розвиток пошуку по дереву методом Монте-Карло за допомогою контролю форми дерева пошуку

Анотація

Представлення інформації певної задачі у вигляді дерева і пошук найкращих рішень в рамках цієї задачі з побудовою дерева рішень методом Монте-Карло, який отримав назву MCTS (Monte Carlo Tree Search) є одним з найкращих підходів для виконання пошуку для розв’язку задач, в яких знаходження найкращих рішень є дуже складним і часовитратним процесом. Стаття присвячена запропонованому раніше варіанту подальшого розвитку пошуку по дереву методом MCTS за допомогою контролю форми дерева пошуку. Цей варіант був названий MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control) і базується на критеріях виду DW (Depth-Width) з метою контролювання форми дерева пошуку під час його побудови. В статті пропонується два нових критерії виду DW: DWC і WDC, принцип впливу яких на форму дерева пошуку, що будується, відрізняється від раніше запропонованих критеріїв. Апробація використання нових запропонованих критеріїв контролю форми дерева DWC і WDC показала підвищення ефективності пошуку кращих подальших ходів гравця, який використовував варіант пошуку MCTS-TSC з контролем форми дерева, порівняно до гравця, що використовував стандартний варіант пошуку MCTS-UCT. Гравець MCTS-TSC при використанні критерію DWC виграв у гравця MCTS-UCT на 55% партій більше, а при використанні критерію WDC – на 42% більше, що суттєво краще, ніж у запропонованих раніше критеріїв. У якості висновків зазначено, що оскільки формули обчислення критеріїв виду DW є нескладними, то їх реалізація для контролю форми дерева не буде суттєво впливати на час пошуку варіантом MCTS-TSC. Крім того, відзначено, що запропоновані нові критерії виду DW можуть бути також використані для більш ефективного розпаралелення процесу пошуку MCTS і більш ефективного використання наявних апаратних ресурсів. Запропоновані також можливі напрямки подальшого розвитку пошуку методом Монте-Карло з контролем форми дерева пошуку MCTS-TSC.