У інформатиці дерево пошуку Монте-Карло (, ДПМК) — це евристичний алгоритм пошуку який можна використати для деяких видів процесів вирішування, а особливо для тих, які використовуються в програмному забезпеченні, яке грає в настільні ігри з дошкою. У цьому контексті ДПМК використовується для побудови дерева гри.
У 2016 році ДПМК та нейронна мережа були об'єднанні для гри в Ґо. Також цей алгоритм використовували в інших настільних іграх, таких як: шахи та сьоґі; іграх з неповною інформацією, таких як бридж> і покер, а також у покрокових стратегічних відеоіграх (наприклад, Total War: Rome II в компанії зі штучним інтелектом високої складності). ДПМК також використовувався в автомобілях з автопілотом. Його, наприклад використали в програмному забезпеченні Tesla Autopilot.Tesla's AI Day video https://youtube.com/watch?v=j0z4FweCy4M
Історія
Метод Монте-Карло Метод Монте-Карло бере свій початок з 1940-х років. Він використовує випадкову вибірку для детерміністичних задач, які важко або неможливо вирішити за допомогою інших підходів. У своїй докторській дисертації 1987 року Брюс Абрамсон об'єднав мінімаксний пошук із моделлю очікуваного результату, яка використовує випадковий вибір дії у гри до кінця, замість оцінювальної функції, яку використовують зазвичай. Абрамсон сказав, що модель очікуваного результату «виявилась точною, легко передбачувальною, такою, що можливо ефективно обчислити та можна легко використати незалежною від сфери завдання». Він багато експериментував з хрестиками-ноликами, а потім з оцінювальними функціями, які було згенеровано машиною для реверсі та шахів.
Потім такий метод було досліджено та успішно застосовано В. Ертелом, Дж. Шуманом та К. Зутнером у 1989 році для евристичного пошуку в області автоматизованого доведення теорем, таким чином зменшуючи час виконання з експоненціального неінформованих алгоритмів пошуку, таких як, пошук у ширину, пошук у глибину або з пошук в глибину з ітеративним заглибленням.
У 1992 році Б. Брюгманн вперше застосував його для гри в Ґо. У 2002 році Чанг та інші запропонували ідею «рекурсивного розгортання та зворотного відстеження» з «адаптивним» вибором вибірки у своєму алгоритмі адаптивної багатоступеневої вибірки () для моделі марковських процесів вирішування. АБВ був першим алгоритмом, який використав ідею для побудови дерев вибірки/моделювання (Монте-Карло) і послужив основою для верхніх дерев довіри ().
Дерево пошуку Монте-Карло
У 2006 році, натхненний попередниками, описав застосування методу Монте-Карло для побудови дерева ігор і придумав назву: «Дерево Пошуку Монте-Карло» Л.Коксіс та Кс. Шепешварі розробили алгоритм "Upper Confidence bounds applied to Trees", або UCT (алгоритм Верхніх меж довіри, які застосовуються до дерев) а С. Геллі та інші впровадили UCT у свою програму MoGo. У 2008 році MoGo досягла рівня дан (майстер) у Го 9×9, і програма Fuego почала перемагати у сильних гравців-аматорів у Го 9×9.
У січні 2012 року програма Дзен перемогла з рахунком 3:1 у матчі Го на дошці 19×19 з . Google Deepmind розробив програму AlphaGo, яка в жовтні 2015 року стала першою програмою гри в Ґо, яка змогла обіграти професійного гравця в Ґо без на повнорозмірній дошці 19x19. У березні 2016 року AlphaGo отримав почесний рівень 9 дану (майстер) у Ґо 19×19 за перемогу над Лі Седолом у з підсумковим рахунком чотири перемоги проти однієї поразки. AlphaGo являє собою значне покращення в порівнянні з попередніми програмами гри в Ґо. Також вона знаменувала нову віху в машинному навчанні, оскільки вона використовує дерево пошуку Монте-Карло у поєднанні зі штучною нейронною мережею (метод глибокого навчання) для розробки стратегії, який є ефективним і значно перевершує попередні програми.
Алгоритм ДПМК також використовували в програмах, які грали в інші настільні ігри на спеціальній дошці (Гекс, , , і ), відеоігри в реальному часі (наприклад, Ms. Pac-Man і ), а також недетерміновані ігри (такі як скат, покер, Magic: The Gathering, або Колонізатори).
Принцип дії Основна ідея ДПМК полягає в аналізі найбільш перспективних ходів, розширенні дерева пошуку на основі випадкової вибірки даних простору пошуку. Застосування дерева пошуку Монте-Карло в іграх базується на багатьох відтвореннях, які також називаються розгортаннями. У кожному відтворені гра розгортається до самого кінця шляхом вибору ходу випадковим чином. Кінцевий результат гри кожного розігрування потім використовується для побудови ваги вузлів у дереві гри, щоб обирати вузли, які призведуть до кращих результатів у майбутніх розігруваннях.
Найпростіший спосіб використання розігрувань — це застосовувати однакову кількість розігрувань після кожного дозволеного ходу поточного гравця, а потім обрати хід, який привів до найбільшої кількості перемог. Ефективність цього методу, який називається чистий ігровий пошук Монте-Карло, часто зростає з часом, оскільки було проведено більше розіграшів для ходів, які частіше призводили до перемоги поточного гравця у порівнянні з попередніми розігруваннями. Кожен раунд побудови дерева пошуку Монте-Карло складається з чотирьох кроків:
Вибір: Починаючи з кореня дерева обійти послідовно дочірні вузли, поки не буде досягнуто вузол . — це поточний стан гри, а лист — це будь-який вузол, у якого потенційно існує дочірній елемент, з якого ще не було ініційовано симуляцію (відтворення). Розділ нижче розповідає більше про спосіб зміщення вибору дочірніх вузлів, що дозволяє дереву гри розширюватися саме до найперспективніших ходів, що і є сутністю дерева пошуку Монте-Карло. Розширення: Якщо не закінчує гру (наприклад, перемога/програш/нічия) для будь-якого гравця, створіть один (або більше) дочірніх вузлів і виберіть вузол поміж них. Дочірні вузли — це будь-які ходи в межах правил з ігрової позиції . Симуляція: завершіть одне випадкове розігрування з вузла . Цей крок іноді також називають відтворенням або розгортанням. Для вибору розігрування можна використати простий алгоритм, як, наприклад, вибір рівномірно випадкових ходів до того моменту, як партія буде закінчена (наприклад, у шахах партія виграна, програна чи нічия). Зворотне поширення: використовуйте результат симуляції для оновлення інформації у вузлах між та
Цей графік показує частину алгоритму вибору одного рішення, де кожен вузол показує відношення виграшів до загальної кількості розіграшів з цієї точки в дереві гри для гравця, який представляє цей вузол. На діаграмі той, хто грає за чорних, має ухвалити рішення. Судячи з кореневого вузла, білі з цієї позиції виграли 11 з 21 ігор. Також виходить, що чорні перемогли в 10 з 21 ігор (21 - 11 = 10, це також можна визначити, якщо скласти значення трьох чорних вузлів під ним, які представляють можливі ходи чорних).
Якщо білі програють симуляцію, всі вузли на шляху вибору збільшують свою кількість симуляцій (знаменник), і тільки чорні вузли збільшують кількість перемог (чисельник). Якщо переможуть білі, усі вузли на шляху все одно збільшать кількість симуляцій, і тільки білим зарахується перемога. У іграх, де можлива нічия, вона призводить до збільшення чисельника для обох на 0,5, а знаменника - на 1. Це гарантує, що під час розрахунку вибір кожного гравця розширюється до найперспективніших ходів для того, щоб максимізувати цінність свого ходу.
Поки є час, відведений на хід, процес пошуку повторюється. Потім, як остаточна відповідь, вибирається хід із найбільшою кількістю зроблених симуляцій (тобто найбільшим знаменником).
Чистий ігровий пошук Монте-Карло Цю базову процедуру можна застосувати до будь-якої гри з кінцевою кількістю ходів кінцевої довжини. Для кожної позиції визначаються всі можливі ходи: k випадкових ігор розігруються до самого кінця, а результати зберігаються. Обирається хід, який веде до найкращого результату. Зв'язки розриваються за допомогою підкидання монети. Чистий ігровий пошук Монте-Карло дає гарні результати при декількох іграх з випадковими елементами, як, наприклад у грі . Він сходиться до оптимальної стратегії (якщо k наближається до нескінченності) у настільних іграх із випадковим порядком ходу, наприклад у Гекс. AlphaZero від DeepMind замінив етап симуляції на використання оцінки на основі нейронної мережі.
Розвідка та використання Основна складність у виборі дочірніх вузлів полягає в підтримці певного балансу між використанням глибоких варіантів після ходів з високим середнім виграшем і розвідкою ходів з невеликою кількістю симуляцій. Першу формулу для балансування використання та розвідки в іграх, яка називається UCT (Upper Confidence Bound 1, яку було застосовано до дерев), було виведено Левенте Кочисом і Чаба Шепешварі. UCT базується на формулі UCB1, виведеної Ауером, Чеза-Біанкі та Фішером, і на доказі збіжності алгоритму Адаптивного Багатоступеневего Відбору, або АБВ (), який було вперше застосовано до багатоступеневих моделей вирішування (зокрема, марковських процесів вирішування) Чангом, Фу, Ху і Маркусом. Кочис і Шепешварі рекомендували обирати в кожному вузлі дерева гри хід, для якого вираз набуває найбільшого значення. У цій формулі:
означає кількість виграшів для вузла після i-го ходу означає кількість симуляцій для вузла після i-го переміщення означає загальну кількість симуляцій батьківського вузла після i-го переміщення параметр розвідки, теоретично рівний ; на практиці зазвичай вибирається емпірично
Ліва частина формули вище відповідає за використання; вона має велике значення для ходів з високим середнім коефіцієнтом виграшу. Права частина відповідає за розвідку; вона висока для ходів з невеликою кількістю симуляцій.
Більшість сучасних реалізацій дерева пошуку Монте-Карло базуються на варіанті UCT, який базується на АБВ: алгоритмі оптимізації моделювання для оцінки функції значення в кінцевих горизонтах марковських процесів вирішування (MDP), представлених Чангом та ін. (2005) у дослідженні операцій. (АБВ була першою роботою, яка досліджувала ідею розвідки та експлуатації на основі UCB при побудові вибіркових/модельованих дерев (Монте-Карло) і була основою для UCT.)
Переваги та недоліки Хоча було доведено, що оцінка ходів у дереві пошуку Монте-Карло сходиться до мінімакса, базова версія дерева пошуку Монте-Карло збігається лише в так званих іграх «Monte Carlo Perfect». Однак дерево пошуку Монте-Карло має значні переваги у порівняні з альфа-бета відсіченням та подібними алгоритмами, що мінімізують простір пошуку.
Зокрема, чистий пошук дерева Монте-Карло не потребує явної оцінювальної функції. Для дослідження простору пошуку (тобто генерування дозволених ходів з заданої позиції та умов закінчення гри) достатньо реалізації механіки гри. Дерево пошуку Монте-Карло можна використовувати в іграх без розробленої теорії або в .
Дерево гри в алгоритмі дерева пошуку Монте-Карло зростає асиметрично, оскільки метод концентрується на найперспективніших піддеревах. Таким чином він досягає кращих результатів, у порівняні з класичними алгоритмами в іграх з високим коефіцієнтом розгалуження.
Недоліком алгоритму є те, що в певних позиціях можуть бути ходи, які виглядають, на перший погляд, перспективними, але насправді призводять до програшу. Такі «стани пастки» вимагають ретельного аналізу та правильної обробки, особливо під час гри проти досвідченого гравця; однак ДПМК може не «помічати» такі лінії через свою стратегію вибіркового розширення вузлів. Вважається, що це могло бути однією з причин через те, що алгоритм намагається обрізати менш релевантні послідовності. У деяких випадках гра може призвести до дуже специфічної лінії гри, яка є важливою, проте яку не помічає алгоритм і обрізає його. Така лінія знаходиться «поза радаром пошуку».
Покращення Для скорочення часу пошуку були запропоновані різні модифікації основного методу алгоритму дерева пошуку Монте-Карло. Деякі покращення виходять зі знання певної області, інші ні.