Аналіз керування формою дерева пошуку MCTS за допомогою критеріїв виду «глибина-ширина»

Анотація

В цій статті розглядається перевірка та аналіз здатності способу вдосконалення пошуку по дереву методом Монте-Карло за допомогою контролю форми дерева пошуку MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control), який був розроблений авторами раніше, виконувати такий контроль. Принцип керування формою дерева пошуку у способі MCTS-TSC базується на застосуванні критеріїв DW (Depth-Width) виду «глибина-ширина». Апробація здатності MCTS-TSC контролювати та скеровувати в потрібному напрямку форму дерева пошуку в процесі його побудови проводилася на виконанні множини партій гри Connect Four, які були зіграні гравцями, що грали як за стандартною реалізацією пошуку по дереву методом Монте-Карло, яка називається MCTS-UCT (Monte-Carlo Tree Search with Upper Confidence bounds applied to Trees), так і за реалізацією способу цього пошуку з контролем форми дерева MCTS-TSC. З метою порівняння процесу побудови дерева пошуку стандартним способом MCTS-UCT і способом із застосуванням контролю за формою дерева MCTS-TSC були отримані дерева, побудовані після виконання однакової кількості ітерацій процесу пошуку і з різними значеннями налаштування параметрів критеріїв виду DW для контролю форми дерев в процесі їх побудови. Після цього була зібрана статистика форм побудованих дерев пошуку і виконаний порівняльний аналіз форми побудованих дерев пошуку і відмінностей процесу їх побудови обома способами пошуку. Проведена апробація та аналіз форми побудованих дерев пошуку показали, що спосіб пошуку по дереву за допомогою контролю форми дерева MCTS-TSC на основі встановлення певних параметрів формули критеріїв виду «глибина-ширина», не змінюючи загального асиметричного принципу побудови дерева пошуку, дозволяє скерувати процес цієї побудови до більш широкої і неглибокої форми дерева, або до більш вузької і глибокої форми. Отримані результати підтверджують здатність способу MCTS-TSC керувати формою дерева пошуку  MCTS за допомогою критеріїв виду «глибина-ширина»