www.wikidata.uk-ua.nina.az

Дерево пошуку Монте Карло У інформатиці дерево пошуку Монте Карло англ Monte Carlo tree search ДПМК це евристичний алгор

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

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

Дерево пошуку Монте-Карло
Клас Алгоритм пошуку

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

Історія ред.

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

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

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

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

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

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

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

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

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

Принцип дії ред.

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

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

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

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

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

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

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

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

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

Основна складність у виборі дочірніх вузлів полягає в підтримці певного балансу між експлуатацією глибоких варіантів після ходів з високим середнім виграшем і розвідкою ходів з невеликою кількістю симуляцій. Першу формулу для балансування експлуатації та розвідки в іграх, яка називається UCT (Upper Confidence Bound 1, яку було застосовано до дерев), було виведено Левенте Кочисом і Чаба Шепешварі. UCT базується на формулі UCB1, виведеної Ауером, Чеза-Біанкі та Фішером, і на доказі збіжності алгоритму АБВ (англ. Adaptive Multi-stage Sampling), який було вперше застосовано до багатоступеневих моделей прийняття рішень (зокрема, Марковський процес прийняття рішень) Чангом, Фу, Ху і Маркусом. Кочис і Шепешварі рекомендували обирати в кожному вузлі дерева гри хід, для якого вираз набуває найбільшого значення. У цій формулі:

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

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

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

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

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

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

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

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

Покращення ред.

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

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

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

При побудові дерева гри можуть бути використані знання, що стосуються предметної області для того, щоб експлуатувати деякі варіанти. Один з таких методів призначає ненульові значення виграним і зіграним симуляціям під час створення кожного дочірнього вузла. Це призводить до штучно підвищення або зниження середнього рівня виграшу, що призводить до того, що вузол вибирається частіше або рідше. Схожий метод, який називається прогресивним зміщенням, полягає в додаванні до формули UCB1 , де bi — евристична оцінка i-го ходу.

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

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

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

При використанні RAVE під час етапу вибору обирається вузол, для якого модифікована формула UCB1 має найбільше значення. У цій формулі:

  •  — це кількість виграних розігрувань, які містять хід i.
  • - це кількість усіх розігрувань, які містять хід i.
  •  — функція, яка наближається до одиниці для відносно малих ni і до нуля для відносно великих .

Одна з багатьох формул для , яку запропонував Д. Сільвер, стверджує, що в збалансованих позиціях можна вважати, що , де b — емпірично обрана константа.

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

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

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

Див. також ред.

Примітки ред.

  1. ↑ Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis та ін. (28 січня 2016). Mastering the game of Go with deep neural networks and tree search. Nature 529 (7587): 484–489. Bibcode:2016Natur.529..484S. ISSN 0028-0836. PMID 26819042. doi:10.1038/nature16961.  {{cite journal}}: рекомендується |displayauthors= (довідка)
  2. ↑ >Artificial Intelligence: A Modern Approach (вид. 3rd). Prentice Hall. 2009. 
  3. ↑ Jonathan Rubin; Ian Watson (April 2011). . Artificial Intelligence 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005. Архів оригіналу за 13 серпня 2012. 
  4. . AI Game Dev. Архів оригіналу за 13 березня 2017. Процитовано 25 лютого 2017. 
  5. Tesla's AI Day video https://youtube.com/watch?v=j0z4FweCy4M [ 15 грудня 2021 у Wayback Machine.]
  6. Abramson, Bruce (1987). . Technical report, Department of Computer Science, Columbia University. Архів оригіналу за 27 жовтня 2016. Процитовано 23 грудня 2013. 
  7. Wolfgang Ertel; Johann Schumann; Christian Suttner (1989). Learning Heuristics for a Theorem Prover using Back Propagation.. У J. Retti. 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95. Springer. 
  8. Christian Suttner; Wolfgang Ertel (1990). Automatic Acquisition of Search Guiding Heuristics.. CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449. Springer. 
  9. Christian Suttner; Wolfgang Ertel (1991). . Journal of Neural Networks Research & Applications 2 (1): 3–16. Архів оригіналу за 15 квітня 2021. Процитовано 15 грудня 2021. 
  10. ↑ Brügmann, Bernd (1993). . Technical report, Department of Physics, Syracuse University. Архів оригіналу за 14 квітня 2021. Процитовано 15 грудня 2021. 
  11. ↑ Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). . Operations Research 53: 126–139. doi:10.1287/opre.1040.0145. Архів оригіналу за 20 квітня 2021. Процитовано 15 грудня 2021. 
  12. ↑ Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). . OR/MS Today 45 (5): 24–29. Архів оригіналу за 15 грудня 2021. Процитовано 15 грудня 2021. 
  13. . Архів оригіналу за 6 травня 2021. Процитовано 3 травня 2012. 
  14. Rémi Coulom (2008). The Monte-Carlo Revolution in Go. Japanese-French Frontiers of Science Symposium. 
  15. Rémi Coulom (2007). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. Springer. с. 72–83. ISBN 978-3-540-75537-1. 
  16. ↑ . ISBN 3-540-45375-X.  {{cite conference}}: Пропущений або порожній |title= (довідка)
  17. ↑ Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). . Technical report, INRIA. Архів оригіналу за 30 липня 2014. Процитовано 15 грудня 2021. 
  18. Chang-Shing Lee; Mei-Hui Wang; Guillaume Chaslot; Jean-Baptiste Hoock; Arpad Rimmel; Olivier Teytaud; Shang-Rong Tsai; Shun-Chin Hsu та ін. (2009). . IEEE Transactions on Computational Intelligence and AI in Games 1 (1): 73–89. doi:10.1109/tciaig.2009.2018703. Архів оригіналу за 26 вересня 2013. Процитовано 15 грудня 2021.  {{cite journal}}: рекомендується |displayauthors= (довідка)
  19. Markus Enzenberger; Martin Mūller (2008). . Technical report, University of Alberta. Архів оригіналу за 9 липня 2021. Процитовано 15 грудня 2021. 
  20. . Архів оригіналу за 14 квітня 2021. Процитовано 2 травня 2012. 
  21. . Google Research Blog. 27 січня 2016. Архів оригіналу за 30 січня 2016. Процитовано 15 грудня 2021. 
  22. . BBC News. 27 січня 2016. Архів оригіналу за 2 грудня 2021. Процитовано 15 грудня 2021. 
  23. . Youtube. 9 березня 2016. Архів оригіналу за 29 березня 2017. Процитовано 15 грудня 2021. 
  24. . ZDNet. 28 січня 2016. Архів оригіналу за 31 січня 2016. Процитовано 15 грудня 2021. 
  25. Broderick Arneson; Ryan Hayward; Philip Henderson (June 2009). . ICGA Journal 32 (2): 114–116. doi:10.3233/ICG-2009-32218. Архів оригіналу за 16 квітня 2021. Процитовано 15 грудня 2021. 
  26. Timo Ewalds (2011). . Master's thesis, University of Alberta. Архів оригіналу за 4 березня 2016. Процитовано 15 грудня 2021. 
  27. Richard J. Lorentz (2008). Amazons Discover Monte-Carlo. Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. Springer. с. 13–24. ISBN 978-3-540-87607-6. 
  28. Tomáš Kozelek (2009). . Master's thesis, Charles University in Prague. Архів оригіналу за 16 квітня 2021. Процитовано 15 грудня 2021. 
  29. Xiaocong Gan; Yun Bao; Zhangang Han (December 2011). Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. ICGA Journal 34 (4): 209–222. doi:10.3233/ICG-2011-34404. 
  30. Tom Pepels; Mark H. M. Winands; Marc Lanctot (September 2014). Real-Time Monte Carlo Tree Search in Ms Pac-Man. IEEE Transactions on Computational Intelligence and AI in Games 6 (3): 245–257. doi:10.1109/tciaig.2013.2291577. 
  31. Mountain, Gwaredd (2015). . Архів оригіналу за 8 червня 2019. Процитовано 8 червня 2019. «.. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...» 
  32. Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). Improving State Evaluation, Inference, and Search in Trick-Based Card Games. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. с. 1407–1413. 
  33. C.D. Ward; P.I. Cowling (2009). . CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press.  {{cite book}}: |archiveurl= вимагає |url= (довідка)
  34. István Szita; Guillaume Chaslot; Pieter Spronck (2010). Monte-Carlo Tree Search in Settlers of Catan. У Jaap Van Den Herik. Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer. с. 21–32. ISBN 978-3-642-12992-6. 
  35. ↑ G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). . New Mathematics and Natural Computation 4 (3): 343–359. doi:10.1142/s1793005708001094. Архів оригіналу за 14 квітня 2021. Процитовано 15 грудня 2021. 
  36. Bradberry, Jeff (7 вересня 2015). . Архів оригіналу за 17 червня 2021. Процитовано 15 грудня 2021. 
  37. Peres, Yuval (2006). «Random-Turn Hex and other selection games». arXiv:abs/math/0508580. 
  38. Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47 (2/3): 235–256. doi:10.1023/a:1013689704352. 
  39. Bouzy, Bruno. Old-fashioned Computer Go vs Monte-Carlo Go. IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii. 
  40. Althöfer, Ingo (2012). On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness. Advances in Computer Games. Lecture Notes in Computer Science 7168. с. 258–269. ISBN 978-3-642-31865-8. doi:10.1007/978-3-642-31866-5_22. 
  41. Ramanujan, Raghuram; Sabharwal, Ashish; Selman, Bart (May 2010). . ICAPS '10: Proceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling: 242–245. Архів оригіналу за 26 жовтня 2021. Процитовано 15 грудня 2021. 
  42. Ramanujan, Raghuram; Selman, Bart (March 2011). . ICAPS '11: Proceedings of the International Conference on Automated Planning and Scheduling 21 (1): 202–209. Архів оригіналу за 29 жовтня 2021. Процитовано 15 грудня 2021. 
  43. . Go Game Guru. Архів оригіналу за 16 листопада 2016. Процитовано 4 липня 2017. 
  44. Świechowski, M.; Mańdziuk, J., «Self-Adaptation of Playing Strategies in General Game Playing» (2010), IEEE Transactions on Computational Intelligence and AI in Games, vol: 6(4), pp. 367—381, doi: 10.1109/TCIAIG.2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
  45. Drake, Peter (December 2009). The Last-Good-Reply Policy for Monte-Carlo Go. ICGA Journal 32 (4): 221–227. doi:10.3233/ICG-2009-32404. 
  46. Seth Pellegrino; Peter Drake (2010). Investigating the Effects of Playout Strength in Monte-Carlo Go. Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA. CSREA Press. с. 1015–1018. ISBN 978-1-60132-148-0. 
  47. ↑ Gelly, Sylvain; Silver, David (2007). . Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007. ACM. с. 273–280. ISBN 978-1-59593-793-3.  {{cite book}}: |archiveurl= вимагає |url= (довідка)
  48. David Silver (2009). . PhD thesis, University of Alberta. Архів оригіналу за 3 березня 2022. Процитовано 15 грудня 2021. 
  49. Rémi Coulom. CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning. ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22. 
  50. Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. Springer. с. 60–71. ISBN 978-3-540-87607-6. 
  51. Markus Enzenberger; Martin Müller (2010). A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm. У Jaap Van Den Herik. Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers. Springer. с. 14–20. ISBN 978-3-642-12992-6. 

Бібліографія ред.

  • Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Perez та ін. (March 2012). A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games 4 (1): 1–43. doi:10.1109/tciaig.2012.2186810.  {{cite journal}}: рекомендується |displayauthors= (довідка)

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U informatici derevo poshuku Monte Karlo angl Monte Carlo tree search DPMK ce evristichnij algoritm poshuku yakij mozhna vikoristati dlya deyakih vidiv procesiv uhvalennya rishen a osoblivo dlya tih yaki vikoristovuyutsya v programnomu zabezpechenni yake graye v nastilni igri z doshkoyu U comu konteksti DPMK vikoristovuyetsya dlya pobudovi dereva gri Derevo poshuku Monte KarloKlas Algoritm poshukuU 2016 roci DPMK ta nejronna merezha buli ob yednanni dlya gri v Go 1 Takozh cej algoritm vikoristovuvali v inshih nastilnih igrah takih yak shahi ta sogi igrah z nepovnoyu informaciyeyu takih yak bridzh 2 i poker 3 a takozh u pokrokovih strategichnih videoigrah napriklad Total War Rome II v kompaniyi zi shtuchnim intelektom visokoyi skladnosti 4 DPMK takozh vikoristovuvavsya v avtomobilyah z avtopilotom Jogo napriklad vikoristali v programnomu zabezpechenni Tesla Autopilot 5 Zmist 1 Istoriya 1 1 Metod Monte Karlo 1 2 Derevo poshuku Monte Karlo 2 Princip diyi 3 Chistij igrovij poshuk Monte Karlo 4 Rozvidka ta ekspluataciya 5 Perevagi ta nedoliki 6 Pokrashennya 7 Div takozh 8 Primitki 9 Bibliografiya 10 PosilannyaIstoriya red Metod Monte Karlo red Metod Monte Karlo bere svij pochatok z 1940 h rokiv Vin vikoristovuye vipadkovu vibirku dlya deterministichnih zadach yaki vazhko abo nemozhlivo virishiti za dopomogoyu inshih pidhodiv U svoyij doktorskij disertaciyi 1987 roku Bryus Abramson ob yednav minimaksnij poshuk iz modellyu ochikuvanogo rezultatu yaka vikoristovuye vipadkovij vibir diyi u gri do kincya zamist ocinyuvalnoyi funkciyi yaku vikoristovuyut zazvichaj Abramson skazav sho model ochikuvanogo rezultatu viyavilas tochnoyu legko peredbachuvalnoyu takoyu sho mozhlivo efektivno obchisliti ta mozhna legko vikoristati nezalezhnoyu vid sferi zavdannya 6 Vin bagato eksperimentuvav z hrestikami nolikami a potim z ocinyuvalnimi funkciyami yaki bulo zgenerovano mashinoyu dlya reversi ta shahiv Potim takij metod bulo doslidzheno ta uspishno zastosovano V Ertelom Dzh Shumanom ta K Zutnerom u 1989 roci dlya evristichnogo poshuku v oblasti avtomatizovanogo dovedennya teorem 7 8 9 takim chinom zmenshuyuchi chas vikonannya z eksponencialnogo neinformovanih algoritmiv poshuku takih yak poshuk u shirinu poshuk u glibinu abo z poshuk v glibinu z iterativnim zagliblennyam U 1992 roci B Bryugmann vpershe zastosuvav jogo dlya gri v Go 10 U 2002 roci Chang ta inshi 11 zaproponuvali ideyu rekursivnogo rozgortannya ta zvorotnogo vidstezhennya z adaptivnim viborom vibirki u svoyemu algoritmi adaptivnoyi bagatostupenevoyi vibirki angl Adaptive Multi stage Sampling AMS dlya modeli procesiv uhvalennya rishen Markova ABV buv pershim algoritmom yakij vikoristav ideyu rozvidki ta ekspluataciyi na osnovi UCB en dlya pobudovi derev vibirki modelyuvannya Monte Karlo i posluzhiv osnovoyu dlya verhnih derev doviri angl Upper Confidence Trees UCT 12 Derevo poshuku Monte Karlo red nbsp Rejting najkrashih program dlya gri v Go na serveri KGS z 2007 roku Z 2006 roku vsi najkrashi programi vikoristovuyut algoritm dereva poshuku Monte Karlo 13 U 2006 roci nathnennij poperednikami 14 Remi Kolum en opisav zastosuvannya metodu Monte Karlo dlya pobudovi dereva igor i pridumav nazvu Derevo Poshuku Monte Karlo 15 L Koksis ta Ks Shepeshvari rozrobili algoritm UCT Verhnih mezh doviri yaki zastosovuyutsya do derev 16 a S Gelli ta inshi vprovadili UCT u svoyu programu MoGo 17 U 2008 roci MoGo dosyagla rivnya dan majster u Go 9 9 18 i programa Fuego pochala peremagati u silnih gravciv amatoriv u Go 9 9 19 U sichni 2012 roku programa Dzen peremogla z rahunkom 3 1 u matchi Go na doshci 19 19 z gravcem amatorom z 2 danom en 20 Google Deepmind rozrobiv programu AlphaGo yaka v zhovtni 2015 roku stala pershoyu programoyu gri v Go yaka zmogla obigrati profesijnogo gravcya v Go bez fori en na povnorozmirnij doshci 19x19 1 21 22 U berezni 2016 roku AlphaGo otrimav pochesnij riven 9 danu majster u Go 19 19 za peremogu nad Li Sedolom u seriyi z p yatoh igor en z pidsumkovim rahunkom chotiri peremogi proti odniyeyi porazki 23 AlphaGo yavlyaye soboyu znachne pokrashennya v porivnyanni z poperednimi programami gri v Go Takozh vona znamenuvala novu vihu v mashinnomu navchanni oskilki vona vikoristovuye derevo poshuku Monte Karlo u poyednanni zi shtuchnoyu nejronnoyu merezheyu metod glibokogo navchannya dlya rozrobki strategiyi yakij ye efektivnim i znachno perevershuye poperedni programi 24 Algoritm DPMK takozh vikoristovuvali v programah yaki grali v inshi nastilni igri na specialnij doshci Geks 25 Gavanna en 26 Igri Amazonok en 27 i Arimaa en 28 videoigri v realnomu chasi napriklad Ms Pac Man 29 30 i Fable Legends en 31 a takozh nedeterminovani igri taki yak skat 32 poker 3 Magic The Gathering 33 abo Kolonizatori 34 Princip diyi red Osnovna ideya DPMK polyagaye v analizi najbilsh perspektivnih hodiv rozshirenni dereva poshuku na osnovi vipadkovoyi vibirki danih prostoru poshuku Zastosuvannya dereva poshuku Monte Karlo v igrah bazuyetsya na bagatoh vidtvorennyah yaki takozh nazivayutsya rozgortannyami U kozhnomu vidtvoreni gra rozgortayetsya do samogo kincya shlyahom viboru hodu vipadkovim chinom Kincevij rezultat gri kozhnogo rozigruvannya potim vikoristovuyetsya dlya pobudovi vagi vuzliv u derevi gri shob obirati vuzli yaki prizvedut do krashih rezultativ u majbutnih rozigruvannyah Najprostishij sposib vikoristannya rozigruvan ce zastosovuvati odnakovu kilkist rozigruvan pislya kozhnogo dozvolenogo hodu potochnogo gravcya a potim obrati hid yakij priviv do najbilshoyi kilkosti peremog 10 Efektivnist cogo metodu yakij nazivayetsya chistij igrovij poshuk Monte Karlo chasto zrostaye z chasom oskilki bulo provedeno bilshe rozigrashiv dlya hodiv yaki chastishe prizvodili do peremogi potochnogo gravcya u porivnyanni z poperednimi rozigruvannyami Kozhen raund pobudovi dereva poshuku Monte Karlo skladayetsya z chotiroh krokiv 35 Vibir Pochinayuchi z korenya dereva R obijti poslidovno dochirni vuzli poki ne bude dosyagnuto vuzol L R ce potochnij stan gri a list ce bud yakij vuzol u yakogo potencijno isnuye dochirnij element z yakogo she ne bulo inicijovano simulyaciyu vidtvorennya Rozdil nizhche rozpovidaye bilshe pro sposib zmishennya viboru dochirnih vuzliv sho dozvolyaye derevu gri rozshiryuvatisya same do najperspektivnishih hodiv sho i ye sutnistyu dereva poshuku Monte Karlo Rozshirennya Yaksho L zakinchuye gru napriklad peremoga progrash nichiya dlya bud yakogo gravcya stvorit odin abo bilshe dochirnih vuzliv i viberit vuzol C pomizh nih Dochirni vuzli ce bud yaki hodi v mezhah pravil z igrovoyi poziciyi L Simulyaciya zavershite odne vipadkove rozigruvannya z vuzla C Cej krok inodi takozh nazivayut vidtvorennyam abo rozgortannyam Dlya viboru rozigruvannya mozhna vikoristati prostij algoritm yak napriklad vibir rivnomirno vipadkovih hodiv do togo momentu yak partiya bude zakinchena napriklad u shahah partiya vigrana prograna chi nichiya Zvorotne poshirennya vikoristovujte rezultat simulyaciyi dlya onovlennya informaciyi u vuzlah mizh C ta R nbsp Krok u algoritmi dereva poshuku Monte Karlo Cej grafik pokazuye chastinu algoritmu viboru odnogo rishennya de kozhen vuzol pokazuye vidnoshennya vigrashiv do zagalnoyi kilkosti rozigrashiv z ciyeyi tochki v derevi gri dlya gravcya yakij predstavlyaye cej vuzol 36 Na diagrami toj yakij graye za chornih maye uhvaliti rishennya Sudyachi z korenevogo vuzla bili z ciyeyi poziciyi vigrali 11 z 21 igor Takozh vihodit sho chorni peremogli v 10 z 21 igor sho vihodit yaksho sklasti znachennya troh chornih vuzliv pid nim yaki predstavlyayut mozhlivi hodi chornih Yaksho bili prograyut simulyaciyu vsi vuzli na shlyahu viboru zbilshuyut svoyu kilkist simulyaciyi znamennik i tilki chorni vuzli zbilshuyut kilkist peremog peremogoyu chiselnik Yaksho peremozhut bili usi vuzli na shlyahu vse odno zbilshat kilkist simulyacij i tilki bilim zarahuyetsya peremoga U igrah de mozhliva nichiya vona prizvodit do zbilshennya chiselnika dlya oboh na 0 5 a znamennika na 1 Ce garantuye sho pid chas rozrahunku vibir kozhnogo gravcya rozshiryuyetsya do najperspektivnishih hodiv dlya togo shob maksimizuvati cinnist svogo hodu Poki ye chas vidvedenij na hid proces poshuku povtoryuyetsya Potim yak ostatochna vidpovid vibirayetsya hid iz najbilshoyu kilkistyu zroblenih simulyacij tobto najbilshim znamennikom Chistij igrovij poshuk Monte Karlo red Cyu bazovu proceduru mozhna zastosuvati do bud yakoyi gri z kincevoyu kilkistyu hodiv kincevoyi dovzhini Dlya kozhnoyi poziciyi viznachayutsya vsi mozhlivi hodi k vipadkovih igor rozigruyutsya do samogo kincya a rezultati zberigayutsya Obirayetsya hid yakij vede do najkrashogo rezultatu Zv yazki rozrivayutsya za dopomogoyu pidkidannya moneti Chistij igrovij poshuk Monte Karlo daye garni rezultati pri dekilkoh igrah z vipadkovimi elementami yak napriklad u gri EinStein wurfelt nicht en Vin shoditsya do optimalnoyi strategiyi yaksho k nablizhayetsya do neskinchennosti u nastilnih igrah iz vipadkovim poryadkom hodu napriklad u Geks 37 AlphaZero vid DeepMind zaminiv etap simulyaciyi na vikoristannya ocinki na osnovi nejronnoyi merezhi 2 Rozvidka ta ekspluataciya red Osnovna skladnist u vibori dochirnih vuzliv polyagaye v pidtrimci pevnogo balansu mizh ekspluataciyeyu glibokih variantiv pislya hodiv z visokim serednim vigrashem i rozvidkoyu hodiv z nevelikoyu kilkistyu simulyacij Pershu formulu dlya balansuvannya ekspluataciyi ta rozvidki v igrah yaka nazivayetsya UCT Upper Confidence Bound 1 yaku bulo zastosovano do derev bulo vivedeno Levente Kochisom i Chaba Shepeshvari 16 UCT bazuyetsya na formuli UCB1 vivedenoyi Auerom Cheza Bianki ta Fisherom 38 i na dokazi zbizhnosti algoritmu ABV angl Adaptive Multi stage Sampling yakij bulo vpershe zastosovano do bagatostupenevih modelej prijnyattya rishen zokrema Markovskij proces prijnyattya rishen Changom Fu Hu i Markusom 11 Kochis i Shepeshvari rekomenduvali obirati v kozhnomu vuzli dereva gri hid dlya yakogo viraz w i n i c ln N i n i displaystyle frac w i n i c sqrt frac ln N i n i nbsp nabuvaye najbilshogo znachennya U cij formuli wi oznachaye kilkist vigrashiv dlya vuzla pislya i go hodu ni oznachaye kilkist simulyacij dlya vuzla pislya i go peremishennya Ni oznachaye zagalnu kilkist simulyacij batkivskogo vuzla pislya i go peremishennya c parametr rozvidki teoretichno rivnij 2 na praktici zazvichaj vibirayetsya empirichnoLiva chastina formuli vishe vidpovidaye za ekspluataciyu vona maye velike znachennya dlya hodiv z visokim serednim koeficiyentom vigrashu Prava chastina vidpovidaye za rozvidku vona visoka dlya hodiv z nevelikoyu kilkistyu simulyacij Bilshist suchasnih realizacij dereva poshuku Monte Karlo bazuyutsya na varianti UCT yakij bazuyetsya na ABV algoritmi optimizaciyi modelyuvannya dlya ocinki funkciyi znachennya v kincevih gorizontah Markovskih procesiv MDP predstavlenih Changom ta in 11 2005 u doslidzhenni operacij ABV bula pershoyu robotoyu yaka doslidzhuvala ideyu rozvidki ta ekspluataciyi na osnovi UCB pri pobudovi vibirkovih modelovanih derev Monte Karlo i bula osnovoyu dlya UCT 12 Perevagi ta nedoliki red Hocha bulo dovedeno sho ocinka hodiv u derevi poshuku Monte Karlo shoditsya do minimaksa 39 bazova versiya dereva poshuku Monte Karlo zbigayetsya lishe v tak zvanih igrah Monte Carlo Perfect 40 Odnak derevo poshuku Monte Karlo maye znachni perevagi u porivnyani z alfa beta vidsichennyam ta podibnimi algoritmami sho minimizuyut prostir poshuku Zokrema chistij poshuk dereva Monte Karlo ne potrebuye yavnoyi ocinyuvalnoyi funkciyi Dlya doslidzhennya prostoru poshuku tobto generuvannya dozvolenih hodiv z zadanoyi poziciyi ta umov zakinchennya gri dostatno realizaciyi mehaniki gri Derevo poshuku Monte Karlo mozhna vikoristovuvati v igrah bez rozroblenoyi teoriyi abo v universalnih igrovih programah en Derevo gri v algoritmi dereva poshuku Monte Karlo zrostaye asimetrichno oskilki metod koncentruyetsya na najperspektivnishih pidderevah Takim chinom vin dosyagaye krashih rezultativ u porivnyani z klasichnimi algoritmami v igrah z visokim koeficiyentom rozgaluzhennya en Nedolikom algoritmu ye te sho v pevnih poziciyah mozhut buti hodi yaki viglyadayut na pershij poglyad perspektivnimi ale naspravdi prizvodyat do prograshu Taki stani pastki vimagayut retelnogo analizu ta pravilnoyi obrobki osoblivo pid chas gri proti dosvidchenogo gravcya odnak DPMK mozhe ne pomichati taki liniyi cherez svoyu strategiyu vibirkovogo rozshirennya vuzliv 41 42 Vvazhayetsya sho ce moglo buti odniyeyu z prichin porazki AlphaGo u chetvertij gri proti Li Sedola en cherez te sho algoritm namagayetsya obrizati mensh relevantni poslidovnosti U deyakih vipadkah gra mozhe prizvesti do duzhe specifichnoyi liniyi gri yaka ye vazhlivoyu prote yaku ne pomichaye algoritm i obrizaye jogo Taka liniya znahoditsya poza radarom poshuku 43 Pokrashennya red Dlya skorochennya chasu poshuku buli zaproponovani rizni modifikaciyi osnovnogo metodu algoritmu dereva poshuku Monte Karlo Deyaki pokrashennya vihodyat zi znannya pevnoyi oblasti inshi ni Derevo poshuku Monte Karlo mozhe vikoristovuvati yak legki tak i vazhki rozigruvannya Legki rozigruvannya skladayutsya z vipadkovih hodiv todi yak vazhki rozigruvannya zastosovuyut rizni evristichni metodi shob vplivati na vibir hodiv 44 Ci evristichni metodi mozhut vikoristovuvati rezultati poperednih rozigrashiv napriklad metod ostannoyi garnoyi vidpovidi 45 abo ekspertni znannya danoyi gri Napriklad u bagatoh programah dlya gri v Go pevni vizerunki kameniv na chastini doshki vplivayut na jmovirnist peremishennya v cyu oblast 17 Paradoksalno ale neoptimalna gra v simulyaciyi inodi robit programu dereva poshuku Monte Karlo silnishe v kincevomu rozrahunku 46 nbsp Vizerunki hane otochennya kameniv suprotivnika yaki vikoristovuyutsya v rozigruvannyah programoyu MoGo Dlya chornogo i bilogo vigidno postaviti kamin na serednij kvadrat za vinyatkom krajnogo pravogo vizerunka de vin viddaye perevagu lishe chornomu 17 Pri pobudovi dereva gri mozhut buti vikoristani znannya sho stosuyutsya predmetnoyi oblasti dlya togo shob ekspluatuvati deyaki varianti Odin z takih metodiv priznachaye nenulovi znachennya vigranim i zigranim simulyaciyam pid chas stvorennya kozhnogo dochirnogo vuzla Ce prizvodit do shtuchno pidvishennya abo znizhennya serednogo rivnya vigrashu sho prizvodit do togo sho vuzol vibirayetsya chastishe abo ridshe 47 Shozhij metod yakij nazivayetsya progresivnim zmishennyam polyagaye v dodavanni do formuli UCB1 b i n i displaystyle frac b i n i nbsp de bi evristichna ocinka i go hodu 35 Bazovij algoritm dereva poshuku Monte Karlo zbiraye dostatno informaciyi dlya togo shob znajti najbilsh perspektivni hodi lishe pislya bagatoh raundiv do tih pir jogo rishennya majzhe vipadkovi Cya faza rozvidki mozhe buti znachno zmenshena v pevnomu klasi igor iz vikoristannyam RAVE Rapid Action Value Estimation 47 U cih igrah perestanovki poslidovnosti hodiv prizvodyat do togo zh polozhennya Yak pravilo ce nastilni igri v yakih hid peredbachaye rozmishennya figuri abo kamenya na doshci U takih igrah na cinnist kozhnogo hodu chasto majzhe ne vplivayut inshi hodi U RAVE dlya danogo vuzla dereva igor N jogo dochirni vuzli Ci zberigayut ne tilki statistiku peremog u rozigruvannyah rozpochatih u vuzli N ale i statistiku peremog u vsih rozigrashah yaki bulo rozpochato u vuzli N i nizhche yaksho voni mistyat ce peremishennya Takim chinom na vmist vuzliv dereva vplivayut ne tilki hodi yaki vikonuyutsya v danij poziciyi ale j ti hodi yaki vikonuyutsya piznishe nbsp RAVE na prikladi hrestikiv nulikiv U chervonih vuzlah statistika RAVE bude onovlena pislya modelyuvannya b1 a2 b3 Pri vikoristanni RAVE pid chas etapu viboru obirayetsya vuzol dlya yakogo modifikovana formula UCB1 1 b n i n i w i n i b n i n i w i n i c ln t n i 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 nbsp maye najbilshe znachennya U cij formuli w i displaystyle tilde w i nbsp ce kilkist vigranih rozigruvan yaki mistyat hid i n i displaystyle tilde n i nbsp ce kilkist usih rozigruvan yaki mistyat hid i b n i n i displaystyle beta n i tilde n i nbsp funkciya yaka nablizhayetsya do odinici dlya vidnosno malih ni i do nulya dlya vidnosno velikih n i displaystyle tilde n i nbsp Odna z bagatoh formul dlya b n i n i displaystyle beta n i tilde n i nbsp yaku zaproponuvav D Silver 48 stverdzhuye sho v zbalansovanih poziciyah mozhna vvazhati sho b n i n i n i n i n i 4 b 2 n i n i displaystyle beta n i tilde n i frac tilde n i n i tilde n i 4b 2 n i tilde n i nbsp de b empirichno obrana konstanta Obrahunki sho vikoristovuyetsya v algoritmi dereva poshuku Monte Karlo chasto zalezhat vid bagatoh parametriv Isnuyut avtomatizovani metodi nalashtuvannya parametriv shob maksimizuvati vigrash 49 Derevo poshuku Monte Karlo mozhe odnochasno obrahovuvatis bagatma potokami abo procesami Isnuye dekilka principovo riznih metodiv jogo paralelnogo vikonannya 50 Paralelizaciya listiv tobto paralelne vikonannya bagatoh rozigruvan odnogo lista igrovogo dereva Koreneva paralelizaciya tobto paralelne stvorennya nezalezhnih igrovih derev yaki vikonuyut hodi na osnovi koreniv vsih cih derev Paralelizaciya dereva tobto paralelna pobudova odnogo igrovogo dereva yake zahishaye dani vid odnochasnogo zapisu za dopomogoyu odnogo globalnogo myuteksu z kilkoma m yuteksami abo z neblokuyuchoyu sinhronizaciyeyu 51 Div takozh red AlphaGo programa dlya Go sho vikoristovuye derevo poshuku Monte Karlo navchannya z pidkriplennyam i gliboke navchannya AlphaGo Zero en onovlena programa dlya Go sho vikoristovuye derevo poshuku Monte Karlo navchannya z pidkriplennyam i gliboke navchannya AlphaZero uzagalnena versiya AlphaGo Zero z vikoristannyam dereva poshuku Monte Karlo navchannya z pidkriplennyam i glibokogo navchannya Leela Chess Zero bezkoshtovna programna realizaciya metodiv AlphaZero dlya gri v shahi yaki na danij moment ye odniyeyu z providnih program dlya gri v shahi Primitki red a b Silver David Huang Aja Maddison Chris J Guez Arthur Sifre Laurent Driessche George van den Schrittwieser Julian Antonoglou Ioannis ta in 28 sichnya 2016 Mastering the game of Go with deep neural networks and tree search Nature 529 7587 484 489 Bibcode 2016Natur 529 484S ISSN 0028 0836 PMID 26819042 doi 10 1038 nature16961 b cite journal b rekomenduyetsya displayauthors dovidka nbsp a b gt Artificial Intelligence A Modern Approach vid 3rd Prentice Hall 2009 a b Jonathan Rubin Ian Watson April 2011 Computer poker A review Artificial Intelligence 175 5 6 958 987 doi 10 1016 j artint 2010 12 005 Arhiv originalu za 13 serpnya 2012 Monte Carlo Tree Search in TOTAL WAR ROME II s Campaign AI AI Game Dev Arhiv originalu za 13 bereznya 2017 Procitovano 25 lyutogo 2017 Tesla s AI Day video https youtube com watch v j0z4FweCy4M Arhivovano 15 grudnya 2021 u Wayback Machine Abramson Bruce 1987 The Expected Outcome Model of Two Player Games Technical report Department of Computer Science Columbia University Arhiv originalu za 27 zhovtnya 2016 Procitovano 23 grudnya 2013 Wolfgang Ertel Johann Schumann Christian Suttner 1989 Learning Heuristics for a Theorem Prover using Back Propagation U J Retti 5 Osterreichische Artificial Intelligence Tagung Informatik Fachberichte 208 pp 87 95 Springer Christian Suttner Wolfgang Ertel 1990 Automatic Acquisition of Search Guiding Heuristics CADE90 10th Int Conf on Automated Deduction pp 470 484 LNAI 449 Springer Christian Suttner Wolfgang Ertel 1991 Using Back Propagation Networks for Guiding the Search of a Theorem Prover Journal of Neural Networks Research amp Applications 2 1 3 16 Arhiv originalu za 15 kvitnya 2021 Procitovano 15 grudnya 2021 a b Brugmann Bernd 1993 Monte Carlo Go Technical report Department of Physics Syracuse University Arhiv originalu za 14 kvitnya 2021 Procitovano 15 grudnya 2021 a b v Chang Hyeong Soo Fu Michael C Hu Jiaqiao Marcus Steven I 2005 An Adaptive Sampling Algorithm for Solving Markov Decision Processes Operations Research 53 126 139 doi 10 1287 opre 1040 0145 Arhiv originalu za 20 kvitnya 2021 Procitovano 15 grudnya 2021 a b Hyeong Soo Chang Michael Fu Jiaqiao Hu Steven I Marcus 2016 Google DeepMind s Alphago O R s unheralded role in the path breaking achievement OR MS Today 45 5 24 29 Arhiv originalu za 15 grudnya 2021 Procitovano 15 grudnya 2021 Sensei s Library KGSBotRatings Arhiv originalu za 6 travnya 2021 Procitovano 3 travnya 2012 Remi Coulom 2008 The Monte Carlo Revolution in Go Japanese French Frontiers of Science Symposium Remi Coulom 2007 Efficient Selectivity and Backup Operators in Monte Carlo Tree Search Computers and Games 5th International Conference CG 2006 Turin Italy May 29 31 2006 Revised Papers Springer s 72 83 ISBN 978 3 540 75537 1 a b ISBN 3 540 45375 X b cite conference b Propushenij abo porozhnij title dovidka a b v Sylvain Gelly Yizao Wang Remi Munos Olivier Teytaud November 2006 Modification of UCT with Patterns in Monte Carlo Go Technical report INRIA Arhiv originalu za 30 lipnya 2014 Procitovano 15 grudnya 2021 Chang Shing Lee Mei Hui Wang Guillaume Chaslot Jean Baptiste Hoock Arpad Rimmel Olivier Teytaud Shang Rong Tsai Shun Chin Hsu ta in 2009 The Computational Intelligence of MoGo Revealed in Taiwan s Computer Go Tournaments IEEE Transactions on Computational Intelligence and AI in Games 1 1 73 89 doi 10 1109 tciaig 2009 2018703 Arhiv originalu za 26 veresnya 2013 Procitovano 15 grudnya 2021 b cite journal b rekomenduyetsya displayauthors dovidka Markus Enzenberger Martin Muller 2008 Fuego An Open Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search Technical report University of Alberta Arhiv originalu za 9 lipnya 2021 Procitovano 15 grudnya 2021 The Shodan Go Bet Arhiv originalu za 14 kvitnya 2021 Procitovano 2 travnya 2012 Research Blog AlphaGo Mastering the ancient game of Go with Machine Learning Google Research Blog 27 sichnya 2016 Arhiv originalu za 30 sichnya 2016 Procitovano 15 grudnya 2021 Google achieves AI breakthrough by beating Go champion BBC News 27 sichnya 2016 Arhiv originalu za 2 grudnya 2021 Procitovano 15 grudnya 2021 Match 1 Google DeepMind Challenge Match Lee Sedol vs AlphaGo Youtube 9 bereznya 2016 Arhiv originalu za 29 bereznya 2017 Procitovano 15 grudnya 2021 Google AlphaGo AI clean sweeps European Go champion ZDNet 28 sichnya 2016 Arhiv originalu za 31 sichnya 2016 Procitovano 15 grudnya 2021 Broderick Arneson Ryan Hayward Philip Henderson June 2009 MoHex Wins Hex Tournament ICGA Journal 32 2 114 116 doi 10 3233 ICG 2009 32218 Arhiv originalu za 16 kvitnya 2021 Procitovano 15 grudnya 2021 Timo Ewalds 2011 Playing and Solving Havannah Master s thesis University of Alberta Arhiv originalu za 4 bereznya 2016 Procitovano 15 grudnya 2021 Richard J Lorentz 2008 Amazons Discover Monte Carlo Computers and Games 6th International Conference CG 2008 Beijing China September 29 October 1 2008 Proceedings Springer s 13 24 ISBN 978 3 540 87607 6 Tomas Kozelek 2009 Methods of MCTS and the game Arimaa Master s thesis Charles University in Prague Arhiv originalu za 16 kvitnya 2021 Procitovano 15 grudnya 2021 Xiaocong Gan Yun Bao Zhangang Han December 2011 Real Time Search Method in Nondeterministic Game Ms Pac Man ICGA Journal 34 4 209 222 doi 10 3233 ICG 2011 34404 Tom Pepels Mark H M Winands Marc Lanctot September 2014 Real Time Monte Carlo Tree Search in Ms Pac Man IEEE Transactions on Computational Intelligence and AI in Games 6 3 245 257 doi 10 1109 tciaig 2013 2291577 Mountain Gwaredd 2015 Tactical Planning and Real time MCTS in Fable Legends Arhiv originalu za 8 chervnya 2019 Procitovano 8 chervnya 2019 we implemented a simulation based approach which involved modelling the game play and using MCTS to search the potential plan space Overall this worked well Michael Buro Jeffrey Richard Long Timothy Furtak Nathan R Sturtevant 2009 Improving State Evaluation Inference and Search in Trick Based Card Games IJCAI 2009 Proceedings of the 21st International Joint Conference on Artificial Intelligence Pasadena California USA July 11 17 2009 s 1407 1413 C D Ward P I Cowling 2009 Monte Carlo Search Applied to Card Selection in Magic The Gathering CIG 09 Proceedings of the 5th international conference on Computational Intelligence and Games IEEE Press b cite book b archiveurl vimagaye url dovidka Istvan Szita Guillaume Chaslot Pieter Spronck 2010 Monte Carlo Tree Search in Settlers of Catan U Jaap Van Den Herik Advances in Computer Games 12th International Conference ACG 2009 Pamplona Spain May 11 13 2009 Revised Papers Springer s 21 32 ISBN 978 3 642 12992 6 a b G M J B Chaslot M H M Winands J W H M Uiterwijk H J van den Herik B Bouzy 2008 Progressive Strategies for Monte Carlo Tree Search New Mathematics and Natural Computation 4 3 343 359 doi 10 1142 s1793005708001094 Arhiv originalu za 14 kvitnya 2021 Procitovano 15 grudnya 2021 Bradberry Jeff 7 veresnya 2015 Introduction to Monte Carlo Tree Search Arhiv originalu za 17 chervnya 2021 Procitovano 15 grudnya 2021 Peres Yuval 2006 Random Turn Hex and other selection games arXiv abs math 0508580 Auer Peter Cesa Bianchi Nicolo Fischer Paul 2002 Finite time Analysis of the Multiarmed Bandit Problem Machine Learning 47 2 3 235 256 doi 10 1023 a 1013689704352 Bouzy Bruno Old fashioned Computer Go vs Monte Carlo Go IEEE Symposium on Computational Intelligence and Games April 1 5 2007 Hilton Hawaiian Village Honolulu Hawaii Althofer Ingo 2012 On Board Filling Games with Random Turn Order and Monte Carlo Perfectness Advances in Computer Games Lecture Notes in Computer Science 7168 s 258 269 ISBN 978 3 642 31865 8 doi 10 1007 978 3 642 31866 5 22 Ramanujan Raghuram Sabharwal Ashish Selman Bart May 2010 On adversarial search spaces and sampling based planning ICAPS 10 Proceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling 242 245 Arhiv originalu za 26 zhovtnya 2021 Procitovano 15 grudnya 2021 Ramanujan Raghuram Selman Bart March 2011 Trade Offs in Sampling Based Adversarial Planning ICAPS 11 Proceedings of the International Conference on Automated Planning and Scheduling 21 1 202 209 Arhiv originalu za 29 zhovtnya 2021 Procitovano 15 grudnya 2021 Lee Sedol defeats AlphaGo in masterful comeback Game 4 Go Game Guru Arhiv originalu za 16 listopada 2016 Procitovano 4 lipnya 2017 Swiechowski M Mandziuk J Self Adaptation of Playing Strategies in General Game Playing 2010 IEEE Transactions on Computational Intelligence and AI in Games vol 6 4 pp 367 381 doi 10 1109 TCIAIG 2013 2275163 http ieeexplore ieee org stamp stamp jsp tp amp arnumber 6571225 amp isnumber 4804729 Drake Peter December 2009 The Last Good Reply Policy for Monte Carlo Go ICGA Journal 32 4 221 227 doi 10 3233 ICG 2009 32404 Seth Pellegrino Peter Drake 2010 Investigating the Effects of Playout Strength in Monte Carlo Go Proceedings of the 2010 International Conference on Artificial Intelligence ICAI 2010 July 12 15 2010 Las Vegas Nevada USA CSREA Press s 1015 1018 ISBN 978 1 60132 148 0 a b Gelly Sylvain Silver David 2007 Combining Online and Offline Knowledge in UCT Machine Learning Proceedings of the Twenty Fourth International Conference ICML 2007 Corvallis Oregon USA June 20 24 2007 ACM s 273 280 ISBN 978 1 59593 793 3 b cite book b archiveurl vimagaye url dovidka David Silver 2009 Reinforcement Learning and Simulation Based Search in Computer Go PhD thesis University of Alberta Arhiv originalu za 3 bereznya 2022 Procitovano 15 grudnya 2021 Remi Coulom CLOP Confident Local Optimization for Noisy Black Box Parameter Tuning ACG 2011 Advances in Computer Games 13 Conference Tilburg the Netherlands November 20 22 Guillaume M J B Chaslot Mark H M Winands Jaap van den Herik 2008 Parallel Monte Carlo Tree Search Computers and Games 6th International Conference CG 2008 Beijing China September 29 October 1 2008 Proceedings Springer s 60 71 ISBN 978 3 540 87607 6 Markus Enzenberger Martin Muller 2010 A Lock free Multithreaded Monte Carlo Tree Search Algorithm U Jaap Van Den Herik Advances in Computer Games 12th International Conference ACG 2009 Pamplona Spain May 11 13 2009 Revised Papers Springer s 14 20 ISBN 978 3 642 12992 6 Bibliografiya red Cameron Browne Edward Powley Daniel Whitehouse Simon Lucas Peter I Cowling Philipp Rohlfshagen Stephen Tavener Diego Perez ta in March 2012 A Survey of Monte Carlo Tree Search Methods IEEE Transactions on Computational Intelligence and AI in Games 4 1 1 43 doi 10 1109 tciaig 2012 2186810 b cite journal b rekomenduyetsya displayauthors dovidka Posilannya red Posibnik dlya pochatkivciv z dereva poshuku Monte Karlo Arhivovano 15 grudnya 2021 u Wayback Machine Otrimano z https uk wikipedia org w index php title Derevo poshuku Monte Karlo amp oldid 40993320