Метод Монте-Карло для пошуку в дереві



Метод Монте-Карло це алгоритм прийняття рішень, часто використовуваний в іграх в якості основи штучного інтелекту. Сильний вплив він справив на програми для гри в Го, хоча знаходить своє застосування і в інших іграх, як настільних, так і звичайних комп'ютерних (наприклад, Total War: Rome II). Так само, варто відзначити, що метод Монте-Карло використовується у відомій програмі AlphaGo, перемогла го-професіонала 9-го дана Чи Седоля в серії з 5 ігор.

У даній статті хотілося б розповісти про версію алгоритму Монте-Карло під назвою Upper Confidence bound applied to Trees (UCT). Саме після публікації цього алгоритму в 2006-му році, програми для гри в Го значно посилили свої позиції і досягли значних успіхів в грі проти людини.

Основою алгоритму UCT є вирішення завдання многоруких бандитів. Зокрема використовується алгоритм Upper-Confidence-Bound (UCB). Він вже був описаний на хабре тут, але я все ж повторю основні моменти.

Завдання звучить так: є набір ігрових автоматів, кожен зі своєю ймовірність виграшу. Потрібно визначити автомат, який принесе більший виграш.

Алгоритм UCB:
1. Ініціалізація. Зіграти на кожній машині один раз
2. На кожній наступній ітерації вибрати машину з максимальним значенням величини ,це середній виграш i-ї машини, кількість ігор на всіх машинах, а кількість ігор, зіграних на і-й машині.

На практиці для пошуку в дереві ходів настільних ігор часто використовується модифікація формули UCB.

Наприклад, така: ,

тут це кількість перемог i-го вузла. — кількість відвідувань i-го вузла, а кількість відвідувань всіх сусідніх вузлів. c це константа, яка використовується для установки потрібного балансу між шириною і глибиною пошуку. Чим вона більше, тим більше буде глибокий пошук.

Як видно з назви, алгоритм UCT (Upper Confidence bound applied to Trees) використовує підхід UCB для пошуку по дереву. Розглянемо покроково кожну фазу алгоритму:


Перша фаза, вибір. Кожну позицію ми розглядаємо як завдання багаторукого бандита. Вузли на кожному етапі вибираються згідно алгоритму UCB. Ця фаза діє до тих пір, поки не буде знайдений вузол в якому ще не всі дочірні вузли мають статистику перемог. На малюнку перше значення у вузлі це кількість перемог, друге загальна кількість ігор в цьому вузлі.


Друга фаза, розширення. Коли алгоритм UCB більше не може бути застосований, додається новий дочірній вузол.


Третя фаза, симуляція. Із створеного на попередньому етапі вузла запускається гра з випадковими або, у разі використання евристик, не зовсім випадковими ходами. Гра йде до кінця партії. Тут важлива тільки інформація про переможця, оцінка позиції не має значення.


Четверта фаза, зворотне поширення. На цьому етапі інформація про зіграної партії поширюється вгору по дереву, оновлюючи інформацію в кожному з раніше пройдених вузлів. Кожен з цих вузлів збільшує показник кількості ігор, а вузли, що збігаються з переможцем, збільшують також і кількість перемог. В кінці алгоритму вибирається вузол, відвіданий найбільшу кількість разів.

UCT не завжди вибирає тільки найкращий хід, але так само періодично досліджує і менш успішні вузли. Другий параметр формули повільно зростає для тих вузлів, які відвідуються не так часто. І в підсумку на якомусь етапі алгоритм обере саме такий хід в якості пріоритетного. Якщо хід виправдав очікування, наступного разу він буде обраний з більшою ймовірністю.

У порівнянні з іншими алгоритмами для пошуку оптимальних ходів, UCT володіє наступними перевагами:

  • UCT може бути безболісно зупинений на будь-якому етапі роботи. І на момент зупинки він прорахує рівномірно всі варіанти ходів з кореневого вузла

    Приклад зупинки алгоритму альфа-бета. Видно, що вузли зі знаком «?» так і не були досліджені
  • Дерево росте асиметрично, досліджуючи кращі ходи глибше за інших. Таким чином, досягається більша ефективність у порівнянні з іншими алгоритмами в іграх зі значною кількістю варіантів для перебору.


Т. к. ходи, вибрані випадково в більшості своєму безглузді та не мають якогось загального напряму, то для поліпшення роботи алгоритму використовуються різні евристичні методи, засновані на інформації про конкретній грі. Один з таких методів це застосування шаблонів.

Ось приклад шаблону 3x3 для розрізання каменів в Го:

Хід буде розцінений як цікавий, коли перший шаблон співпадає, а другий і третій немає. Тобто білу групу можна «розрізати». Квадратиком зображена цікавить нас позиція.

Шаблони можуть використовуватися як на етапі вибору ходу в дереві, так і на етапі симуляції. Найчастіше такі шаблони шукаються десь в околицях останнього зробленого ходу. Це робиться тому, що поточний хід не рідко є відповіддю на попередній і швидше за все, буде зроблений десь поблизу.

Приклад з серії до і після. Зліва ігрова ситуація з використанням звичайного UCT, праворуч UCT c застосуванням шаблонів:

Видно, що на першому малюнку камені безсистемно розставлені по всій дошці.

У більшості випадків шаблони пишуться вручну, але є так само і приклади автоматичної генерації.

Для того щоб не розпорошуватись на всю дошку і не витрачати час на прорахунок зайвих варіантів. Можна виділити найбільш важливу область, в якій вже і досліджувати ходи. Очевидно, що якщо в даний момент вся боротьба зосереджена навколо однієї групи в певному кутку дошки, то не має сенсу розглядати порожні області навколо. Алгоритми визначення таких областей виходять за рамки статті, але ті, кому цікаво може почитати детальніше тут: Common Fate Graph.

Алгоритм UCT може бути одночасно запущений в декількох потоках. Ось деякі способи паралелізації обчислень:
  • Розпаралелювання вузлів, одночасна симуляція ігор з одного і того ж вузла.
  • Розпаралелювання кореня, побудова незалежних дерев.
  • Розпаралелювання дерева, спільне побудова одного дерева декількома потоками.


Це напевно все, що хотілося б сказати про алгоритм Монте-Карло і зокрема UCT. У цілому алгоритм з урахуванням додаткових модифікацій показує непогані результати гри. На користь цього твердження говорить, те, що всі сучасні Го-програми використовують саме його. Сподіваюся, що для когось із вас він теж опиниться корисний.



Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.