Метод розпаралелення пошуку по дереву методом MCTS

Анотація

Метод, який пропонується в цій статті, ґрунтується на двох напрямках подальшого розвитку пошуку по дереву методом Монте-Карло (MCTS): напрямку вдосконалення теоретичних підходів цього методу і напрямку розпаралелення процесу пошуку цим методом. Розпаралелення пошуку MCTS виконується на основі раніше запропонованих авторському варіанті MCTS-TSC (Monte-Carlo Tree Search with Tree Shape Control) з контролем форми дерева пошуку, узагальненій графово-структурній гетерогенній моделі динамічного розпаралелення пошуку по дереву методом Монте-Карло, а також моделі ресурсів гетерогенної розподіленої комп’ютерної системи з локальними зв’язками та її графу. Запропонований метод розпаралелення враховує всі три відомі методи апаратно-незалежного розпаралелення MCTS: кореневе, деревне і листкове розпаралелення і складається із семи етапів. Принциповою відмінністю запропонованого метода від методів інших дослідників є більш інтелектуальне прийняття рішення про вид розпаралелення та степінь розпаралелення у вершинах дерева пошуку на етапах 1-3, яке приймається як на основі наявних апаратних ресурсів, так і на основі поточної форми дерева пошуку, щоб спрямувати подальшу побудову дерева у бажаному напрямку (в глибину, чи в ширину), в той час, як іншими дослідниками, як правило, виконується тільки достатньо жорстко прив’язана до конкретної конфігурації обчислювальної системи реалізація кореневого розпаралелення між декількома комп’ютерами, реалізація деревного розпаралелення чи реалізація листкового розпаралелення на платах GPU. Запропонований метод розпаралелення пошуку методом MCTS забезпечує більш ефективне завантаження наявних апаратних ресурсів і дозволяє як прискорити процес пошуку в цілому, так і підвищити ефективність пошуку методом MCTS.