Дерево пошуку Монте-Карло

У інформатиці дерево пошуку Монте-Карло (англ. Monte Carlo tree search, ДПМК) — це евристичний алгоритм пошуку який можна використати для деяких видів процесів вирішування, а особливо для тих, які використовуються в програмному забезпеченні, яке грає в настільні ігри з дошкою. У цьому контексті ДПМК використовується для побудови дерева гри.

Дерево пошуку Монте-Карло

Клас	Алгоритм пошуку

У 2016 році ДПМК та нейронна мережа були об'єднанні для гри в Ґо.^[1] Також цей алгоритм використовували в інших настільних іграх, таких як: шахи та сьоґі; іграх з неповною інформацією, таких як бридж^[2] і покер^[3], а також у покрокових стратегічних відеоіграх (наприклад, Total War: Rome II в компанії зі штучним інтелектом високої складності^[4]). ДПМК також використовувався в автомобілях з автопілотом. Його, наприклад використали в програмному забезпеченні Tesla Autopilot.^[5]

Історія

Метод Монте-Карло

Метод Монте-Карло бере свій початок з 1940-х років. Він використовує випадкову вибірку для детерміністичних задач, які важко або неможливо вирішити за допомогою інших підходів. У своїй докторській дисертації 1987 року Брюс Абрамсон об'єднав мінімаксний пошук із моделлю очікуваного результату, яка використовує випадковий вибір дії у гри до кінця, замість оцінювальної функції, яку використовують зазвичай. Абрамсон сказав, що модель очікуваного результату «виявилась точною, легко передбачувальною, такою, що можливо ефективно обчислити та можна легко використати незалежною від сфери завдання».^[6] Він багато експериментував з хрестиками-ноликами, а потім з оцінювальними функціями, які було згенеровано машиною для реверсі та шахів.

Потім такий метод було досліджено та успішно застосовано В. Ертелом, Дж. Шуманом та К. Зутнером у 1989 році для евристичного пошуку в області автоматизованого доведення теорем^[7][8][9], таким чином зменшуючи час виконання з експоненціального неінформованих алгоритмів пошуку, таких як, пошук у ширину, пошук у глибину або з пошук в глибину з ітеративним заглибленням.

У 1992 році Б. Брюгманн вперше застосував його для гри в Ґо.^[10] У 2002 році Чанг та інші^[11] запропонували ідею «рекурсивного розгортання та зворотного відстеження» з «адаптивним» вибором вибірки у своєму алгоритмі адаптивної багатоступеневої вибірки (англ. Adaptive Multi-stage Sampling, AMS) для моделі марковських процесів вирішування. АБВ був першим алгоритмом, який використав ідею розвідки та експлуатації на основі UCB^[en] для побудови дерев вибірки/моделювання (Монте-Карло) і послужив основою для верхніх дерев довіри (англ. Upper Confidence Trees, UCT).^[12]

Дерево пошуку Монте-Карло

Рейтинг найкращих програм для гри в Ґо на сервері KGS з 2007 року. З 2006 року всі найкращі програми використовують алгоритм дерева пошуку Монте-Карло.^[13]

У 2006 році, натхненний попередниками,^[14] Ремі Колум^[en] описав застосування методу Монте-Карло для побудови дерева ігор і придумав назву: «Дерево Пошуку Монте-Карло»^[15] Л.Коксіс та Кс. Шепешварі розробили алгоритм UCT (Верхніх меж довіри, які застосовуються до дерев)^[16] а С. Геллі та інші впровадили UCT у свою програму MoGo.^[17] У 2008 році MoGo досягла рівня дан (майстер) у Го 9×9,^[18] і програма Fuego почала перемагати у сильних гравців-аматорів у Го 9×9.^[19]

У січні 2012 року програма Дзен перемогла з рахунком 3:1 у матчі Го на дошці 19×19 з гравцем-аматором з 2 даном^[en].^[20] Google Deepmind розробив програму AlphaGo, яка в жовтні 2015 року стала першою програмою гри в Ґо, яка змогла обіграти професійного гравця в Ґо без фори^[en] на повнорозмірній дошці 19x19.^[1][21][22] У березні 2016 року AlphaGo отримав почесний рівень 9 дану (майстер) у Ґо 19×19 за перемогу над Лі Седолом у серії з п'ятьох ігор^[en] з підсумковим рахунком чотири перемоги проти однієї поразки.^[23] AlphaGo являє собою значне покращення в порівнянні з попередніми програмами гри в Ґо. Також вона знаменувала нову віху в машинному навчанні, оскільки вона використовує дерево пошуку Монте-Карло у поєднанні зі штучною нейронною мережею (метод глибокого навчання) для розробки стратегії, який є ефективним і значно перевершує попередні програми.^[24]

Алгоритм ДПМК також використовували в програмах, які грали в інші настільні ігри на спеціальній дошці (Гекс,^[25] Гаванна^[en],^[26] Ігри Амазонок^[en],^[27] і Арімаа^[en][28]), відеоігри в реальному часі (наприклад, Ms. Pac-Man^[29][30] і Fable Legends^[en][31]), а також недетерміновані ігри (такі як скат,^[32] покер,^[3] Magic: The Gathering,^[33] або Колонізатори^[34]).

Принцип дії

Основна ідея ДПМК полягає в аналізі найбільш перспективних ходів, розширенні дерева пошуку на основі випадкової вибірки даних простору пошуку. Застосування дерева пошуку Монте-Карло в іграх базується на багатьох відтвореннях, які також називаються розгортаннями. У кожному відтворені гра розгортається до самого кінця шляхом вибору ходу випадковим чином. Кінцевий результат гри кожного розігрування потім використовується для побудови ваги вузлів у дереві гри, щоб обирати вузли, які призведуть до кращих результатів у майбутніх розігруваннях.

Найпростіший спосіб використання розігрувань — це застосовувати однакову кількість розігрувань після кожного дозволеного ходу поточного гравця, а потім обрати хід, який привів до найбільшої кількості перемог.^[10] Ефективність цього методу, який називається чистий ігровий пошук Монте-Карло, часто зростає з часом, оскільки було проведено більше розіграшів для ходів, які частіше призводили до перемоги поточного гравця у порівнянні з попередніми розігруваннями. Кожен раунд побудови дерева пошуку Монте-Карло складається з чотирьох кроків:^[35]

• Вибір: Починаючи з кореня дерева R обійти послідовно дочірні вузли, поки не буде досягнуто вузол L. R — це поточний стан гри, а лист — це будь-який вузол, у якого потенційно існує дочірній елемент, з якого ще не було ініційовано симуляцію (відтворення). Розділ нижче розповідає більше про спосіб зміщення вибору дочірніх вузлів, що дозволяє дереву гри розширюватися саме до найперспективніших ходів, що і є сутністю дерева пошуку Монте-Карло.
• Розширення: Якщо L закінчує гру (наприклад, перемога/програш/нічия) для будь-якого гравця, створіть один (або більше) дочірніх вузлів і виберіть вузол C поміж них. Дочірні вузли — це будь-які ходи в межах правил з ігрової позиції L.
• Симуляція: завершите одне випадкове розігрування з вузла C. Цей крок іноді також називають відтворенням або розгортанням. Для вибору розігрування можна використати простий алгоритм, як, наприклад вибір рівномірно випадкових ходів до того моменту, як партія буде закінчена (наприклад, у шахах партія виграна, програна чи нічия).
• Зворотне поширення: використовуйте результат симуляції для оновлення інформації у вузлах між C та R

Крок у алгоритмі дерева пошуку Монте-Карло.

Цей графік показує частину алгоритму вибору одного рішення, де кожен вузол показує відношення виграшів до загальної кількості розіграшів з цієї точки в дереві гри для гравця, який представляє цей вузол.^[36] На діаграмі той, який грає за чорних, має ухвалити рішення. Судячи з кореневого вузла, білі з цієї позиції виграли 11 з 21 ігор. Також виходить, що чорні перемогли в 10 з 21 ігор, що виходить, якщо скласти значення трьох чорних вузлів під ним, які представляють можливі ходи чорних.

Якщо білі програють симуляцію, всі вузли на шляху вибору збільшують свою кількість симуляції (знаменник), і тільки чорні вузли збільшують кількість перемог перемогою (чисельник). Якщо переможуть білі, усі вузли на шляху все одно збільшать кількість симуляцій, і тільки білим зарахується перемога. У іграх, де можлива нічия, вона призводить до збільшення чисельника для обох на 0,5, а знаменника на 1. Це гарантує, що під час розрахунку вибір кожного гравця розширюється до найперспективніших ходів, для того, щоб максимізувати цінність свого ходу.

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

Чистий ігровий пошук Монте-Карло

Цю базову процедуру можна застосувати до будь-якої гри з кінцевою кількістю ходів кінцевої довжини. Для кожної позиції визначаються всі можливі ходи: k випадкових ігор розігруються до самого кінця, а результати зберігаються. Обирається хід, який веде до найкращого результату. Зв'язки розриваються за допомогою підкидання монети. Чистий ігровий пошук Монте-Карло дає гарні результати при декількох іграх з випадковими елементами, як, наприклад у грі EinStein würfelt nicht!^[en]. Він сходиться до оптимальної стратегії (якщо k наближається до нескінченності) у настільних іграх із випадковим порядком ходу, наприклад у Гекс.^[37] AlphaZero від DeepMind замінив етап симуляції на використання оцінки на основі нейронної мережі.^[2]

Розвідка та експлуатація

Основна складність у виборі дочірніх вузлів полягає в підтримці певного балансу між експлуатацією глибоких варіантів після ходів з високим середнім виграшем і розвідкою ходів з невеликою кількістю симуляцій. Першу формулу для балансування експлуатації та розвідки в іграх, яка називається UCT (Upper Confidence Bound 1, яку було застосовано до дерев), було виведено Левенте Кочисом і Чаба Шепешварі.^[16] UCT базується на формулі UCB1, виведеної Ауером, Чеза-Біанкі та Фішером^[38], і на доказі збіжності алгоритму АБВ (англ. Adaptive Multi-stage Sampling), який було вперше застосовано до багатоступеневих моделей вирішування (зокрема, марковських процесів вирішування) Чангом, Фу, Ху і Маркусом.^[11] Кочис і Шепешварі рекомендували обирати в кожному вузлі дерева гри хід, для якого вираз ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$ набуває найбільшого значення. У цій формулі:

• w_i означає кількість виграшів для вузла після i-го ходу
• n_i означає кількість симуляцій для вузла після i-го переміщення
• N_i означає загальну кількість симуляцій батьківського вузла після i-го переміщення
• c параметр розвідки, теоретично рівний √2; на практиці зазвичай вибирається емпірично

Ліва частина формули вище відповідає за експлуатацію; вона має велике значення для ходів з високим середнім коефіцієнтом виграшу. Права частина відповідає за розвідку; вона висока для ходів з невеликою кількістю симуляцій.

Більшість сучасних реалізацій дерева пошуку Монте-Карло базуються на варіанті UCT, який базується на АБВ: алгоритмі оптимізації моделювання для оцінки функції значення в кінцевих горизонтах марковських процесів вирішування (MDP), представлених Чангом та ін.^[11] (2005) у дослідженні операцій. (АБВ була першою роботою, яка досліджувала ідею розвідки та експлуатації на основі UCB при побудові вибіркових/модельованих дерев (Монте-Карло) і була основою для UCT.^[12])

Переваги та недоліки

Хоча було доведено, що оцінка ходів у дереві пошуку Монте-Карло сходиться до мінімакса^[39], базова версія дерева пошуку Монте-Карло збігається лише в так званих іграх «Monte Carlo Perfect».^[40] Однак дерево пошуку Монте-Карло має значні переваги у порівняні з альфа-бета відсіченням та подібними алгоритмами, що мінімізують простір пошуку.

Зокрема, чистий пошук дерева Монте-Карло не потребує явної оцінювальної функції. Для дослідження простору пошуку (тобто генерування дозволених ходів з заданої позиції та умов закінчення гри) достатньо реалізації механіки гри. Дерево пошуку Монте-Карло можна використовувати в іграх без розробленої теорії або в універсальних ігрових програмах^[en].

Дерево гри в алгоритмі дерева пошуку Монте-Карло зростає асиметрично, оскільки метод концентрується на найперспективніших піддеревах. Таким чином він досягає кращих результатів, у порівняні з класичними алгоритмами в іграх з високим коефіцієнтом розгалуження.

Недоліком алгоритму є те, що в певних позиціях можуть бути ходи, які виглядають, на перший погляд, перспективними, але насправді призводять до програшу. Такі «стани пастки» вимагають ретельного аналізу та правильної обробки, особливо під час гри проти досвідченого гравця; однак ДПМК може не «помічати» такі лінії через свою стратегію вибіркового розширення вузлів.^[41][42] Вважається, що це могло бути однією з причин поразки AlphaGo у четвертій грі проти Лі Седола^[en] через те, що алгоритм намагається обрізати менш релевантні послідовності. У деяких випадках гра може призвести до дуже специфічної лінії гри, яка є важливою, проте яку не помічає алгоритм і обрізає його. Така лінія знаходиться «поза радаром пошуку».^[43]

Покращення

Для скорочення часу пошуку були запропоновані різні модифікації основного методу алгоритму дерева пошуку Монте-Карло. Деякі покращення виходять зі знання певної області, інші ні.

Дерево пошуку Монте-Карло може використовувати як легкі, так і важкі розігрування. Легкі розігрування складаються з випадкових ходів, тоді як важкі розігрування застосовують різні евристичні методи, щоб впливати на вибір ходів.^[44] Ці евристичні методи можуть використовувати результати попередніх розіграшів (наприклад, метод останньої гарної відповіді^[45]) або експертні знання даної гри. Наприклад, у багатьох програмах для гри в Ґо певні візерунки каменів на частині дошки впливають на ймовірність переміщення в цю область.^[17] Парадоксально, але неоптимальна гра в симуляції іноді робить програму дерева пошуку Монте-Карло сильніше в кінцевому розрахунку.^[46]

Візерунки хане (оточення каменів супротивника), які використовуються в розігруваннях програмою MoGo. Для чорного і білого вигідно поставити камінь на середній квадрат, за винятком крайнього правого візерунка, де він віддає перевагу лише чорному.^[17]

При побудові дерева гри можуть бути використані знання, що стосуються предметної області для того, щоб експлуатувати деякі варіанти. Один з таких методів призначає ненульові значення виграним і зіграним симуляціям під час створення кожного дочірнього вузла. Це призводить до штучно підвищення або зниження середнього рівня виграшу, що призводить до того, що вузол вибирається частіше або рідше.^[47] Схожий метод, який називається прогресивним зміщенням, полягає в додаванні до формули UCB1 ${\displaystyle {\frac {b_{i}}{n_{i}}}}$, де b_i — евристична оцінка i-го ходу.^[35]

Базовий алгоритм дерева пошуку Монте-Карло збирає достатньо інформації для того, щоб знайти найбільш перспективні ходи, лише після багатьох раундів; до тих пір його рішення майже випадкові. Ця фаза розвідки може бути значно зменшена в певному класі ігор із використанням RAVE (Rapid Action Value Estimation).^[47] У цих іграх перестановки послідовності ходів призводять до того ж положення. Як правило, це настільні ігри, в яких хід передбачає розміщення фігури або каменя на дошці. У таких іграх на цінність кожного ходу часто майже не впливають інші ходи.

У RAVE для даного вузла дерева ігор N його дочірні вузли C_i зберігають не тільки статистику перемог у розігруваннях, розпочатих у вузлі N, але і статистику перемог у всіх розіграшах, які було розпочато у вузлі N і нижче, якщо вони містять це переміщення. Таким чином, на вміст вузлів дерева впливають не тільки ходи, які виконуються в даній позиції, але й ті ходи, які виконуються пізніше.

RAVE на прикладі хрестиків-нуликів. У червоних вузлах статистика RAVE буде оновлена після моделювання b1-a2-b3.

При використанні RAVE під час етапу вибору обирається вузол, для якого модифікована формула UCB1 ${\displaystyle (1-\beta (n_{i},{\tilde {n}}_{i})){\frac {w_{i}}{n_{i}}}+\beta (n_{i},{\tilde {n}}_{i}){\frac {{\tilde {w}}_{i}}{{\tilde {n}}_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}}$ має найбільше значення. У цій формулі:

• ${\displaystyle {\tilde {w}}_{i}}$ — це кількість виграних розігрувань, які містять хід i.
• ${\displaystyle {\tilde {n}}_{i}}$- це кількість усіх розігрувань, які містять хід i.
• ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ — функція, яка наближається до одиниці для відносно малих n_i і до нуля для відносно великих ${\displaystyle {\tilde {n}}_{i}}$.

Одна з багатьох формул для ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$, яку запропонував Д. Сільвер,^[48] стверджує, що в збалансованих позиціях можна вважати, що ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})={\frac {{\tilde {n}}_{i}}{n_{i}+{\tilde {n}}_{i}+4b^{2}n_{i}{\tilde {n}}_{i}}}}$, де b — емпірично обрана константа.

Обрахунки, що використовується в алгоритмі дерева пошуку Монте-Карло, часто залежать від багатьох параметрів. Існують автоматизовані методи налаштування параметрів, щоб максимізувати виграш.^[49]

Дерево пошуку Монте-Карло може одночасно обраховуватись багатьма потоками або процесами. Існує декілька принципово різних методів його паралельного виконання:^[50]

• Паралелізація листів, тобто паралельне виконання багатьох розігрувань одного листа ігрового дерева.
• Коренева паралелізація, тобто паралельне створення незалежних ігрових дерев, які виконують ходи на основі коренів всіх цих дерев.
• Паралелізація дерева, тобто паралельна побудова одного ігрового дерева, яке захищає дані від одночасного запису за допомогою одного глобального мьютексу, з кількома м'ютексами або з неблокуючою синхронізацією.^[51]

Див. також

• AlphaGo, програма для Ґо, що використовує дерево пошуку Монте-Карло, навчання з підкріпленням і глибоке навчання.
• AlphaGo Zero^[en], оновлена програма для Ґо, що використовує дерево пошуку Монте-Карло, навчання з підкріпленням і глибоке навчання.
• AlphaZero, узагальнена версія AlphaGo Zero з використанням дерева пошуку Монте-Карло, навчання з підкріпленням і глибокого навчання.
• Leela Chess Zero, безкоштовна програмна реалізація методів AlphaZero для гри в шахи, які на даний момент є однією з провідних програм для гри в шахи.