Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

Історія

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

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

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

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

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

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

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

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

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

Принцип дії

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покращення

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  1. Silver, David; ; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda (28 січня 2016). Mastering the game of Go with deep neural networks and tree search. Nature. 529 (7587): 484—489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042.image
  2. >Artificial Intelligence: A Modern Approach (вид. 3rd). Prentice Hall. 2009.
  3. Jonathan Rubin; Ian Watson (April 2011). (PDF). Artificial Intelligence. 175 (5–6): 958—987. doi:10.1016/j.artint.2010.12.005. Архів оригіналу (PDF) за 13 серпня 2012.
  4. . AI Game Dev. Архів оригіналу за 13 March 2017. Процитовано 25 лютого 2017.
  5. Tesla's AI Day video https://youtube.com/watch?v=j0z4FweCy4M [ 15 грудня 2021 у Wayback Machine.]
  6. Abramson, Bruce (1987). (PDF). Technical report, Department of Computer Science, Columbia University. Архів оригіналу (PDF) за 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). (PDF). Technical report, Department of Physics, Syracuse University. Архів оригіналу (PDF) за 14 квітня 2021. Процитовано 15 грудня 2021.
  11. Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). (PDF). Operations Research. 53: 126—139. doi:10.1287/opre.1040.0145. Архів оригіналу (PDF) за 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. (2008). The Monte-Carlo Revolution in Go. Japanese-French Frontiers of Science Symposium.
  15. (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 .
  16. . ISBN . {{}}: Пропущений або порожній |title= ()
  17. Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). (PDF). Technical report, INRIA. Архів оригіналу (PDF) за 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; Tzung-Pei Hong (2009). (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 1 (1): 73—89. doi:10.1109/tciaig.2009.2018703. Архів оригіналу (PDF) за 26 вересня 2013. Процитовано 15 грудня 2021.
  19. Markus Enzenberger; Martin Mūller (2008). (PDF). Technical report, University of Alberta. Архів оригіналу (PDF) за 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). (PDF). . 32 (2): 114—116. doi:10.3233/ICG-2009-32218. Архів оригіналу (PDF) за 16 квітня 2021. Процитовано 15 грудня 2021.
  26. Timo Ewalds (2011). (PDF). Master's thesis, University of Alberta. Архів оригіналу (PDF) за 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 .
  28. Tomáš Kozelek (2009). (PDF). Master's thesis, Charles University in Prague. Архів оригіналу (PDF) за 16 квітня 2021. Процитовано 15 грудня 2021.
  29. Xiaocong Gan; Yun Bao; Zhangang Han (December 2011). Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. . 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). 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. {{}}: |archive-url= вимагає |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 .
  35. G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). (PDF). New Mathematics and Natural Computation. 4 (3): 343—359. doi:10.1142/s1793005708001094. Архів оригіналу (PDF) за 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. {{}}: Перевірте значення |arxiv= ()
  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. doi:10.1007/978-3-642-31866-5_22. ISBN .
  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 .
  47. 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. с. 273—280. ISBN . {{}}: |archive-url= вимагає |url= ()
  48. David Silver (2009). (PDF). PhD thesis, University of Alberta. Архів оригіналу (PDF) за 3 березня 2022. Процитовано 15 грудня 2021.
  49. . 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, (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 .
  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 .

Бібліографія

  • Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Perez; Spyridon Samothrakis (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.

Посилання

  • Посібник для початківців з дерева пошуку Монте-Карло [ 15 грудня 2021 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U informatici derevo poshuku Monte Karlo angl Monte Carlo tree search DPMK ce evristichnij algoritm poshuku yakij mozhna vikoristati dlya deyakih vidiv procesiv virishuvannya 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 KarloKlasAlgoritm poshuku U 2016 roci DPMK ta nejronna merezha buli ob yednanni dlya gri v Go Takozh cej algoritm vikoristovuvali v inshih nastilnih igrah takih yak shahi ta sogi igrah z nepovnoyu informaciyeyu takih yak bridzh i poker a takozh u pokrokovih strategichnih videoigrah napriklad Total War Rome II v kompaniyi zi shtuchnim intelektom visokoyi skladnosti DPMK takozh vikoristovuvavsya v avtomobilyah z avtopilotom Jogo napriklad vikoristali v programnomu zabezpechenni Tesla Autopilot IstoriyaMetod Monte Karlo 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 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 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 U 2002 roci Chang ta inshi 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 markovskih procesiv virishuvannya ABV buv pershim algoritmom yakij vikoristav ideyu en dlya pobudovi derev vibirki modelyuvannya Monte Karlo i posluzhiv osnovoyu dlya verhnih derev doviri angl Upper Confidence Trees UCT Derevo poshuku Monte Karlo 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 U 2006 roci nathnennij poperednikami en opisav zastosuvannya metodu Monte Karlo dlya pobudovi dereva igor i pridumav nazvu Derevo Poshuku Monte Karlo L Koksis ta Ks Shepeshvari rozrobili algoritm UCT Verhnih mezh doviri yaki zastosovuyutsya do derev a S Gelli ta inshi vprovadili UCT u svoyu programu MoGo U 2008 roci MoGo dosyagla rivnya dan majster u Go 9 9 i programa Fuego pochala peremagati u silnih gravciv amatoriv u Go 9 9 U sichni 2012 roku programa Dzen peremogla z rahunkom 3 1 u matchi Go na doshci 19 19 z en Google Deepmind rozrobiv programu AlphaGo yaka v zhovtni 2015 roku stala pershoyu programoyu gri v Go yaka zmogla obigrati profesijnogo gravcya v Go bez en na povnorozmirnij doshci 19x19 U berezni 2016 roku AlphaGo otrimav pochesnij riven 9 danu majster u Go 19 19 za peremogu nad Li Sedolom u en z pidsumkovim rahunkom chotiri peremogi proti odniyeyi porazki 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 Algoritm DPMK takozh vikoristovuvali v programah yaki grali v inshi nastilni igri na specialnij doshci Geks en en i en videoigri v realnomu chasi napriklad Ms Pac Man i en a takozh nedeterminovani igri taki yak skat poker Magic The Gathering abo Kolonizatori Princip diyiOsnovna 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 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 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 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 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 KarloCyu 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 en Vin shoditsya do optimalnoyi strategiyi yaksho k nablizhayetsya do neskinchennosti u nastilnih igrah iz vipadkovim poryadkom hodu napriklad u Geks AlphaZero vid DeepMind zaminiv etap simulyaciyi na vikoristannya ocinki na osnovi nejronnoyi merezhi Rozvidka ta ekspluataciyaOsnovna 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 UCT bazuyetsya na formuli UCB1 vivedenoyi Auerom Cheza Bianki ta Fisherom i na dokazi zbizhnosti algoritmu ABV angl Adaptive Multi stage Sampling yakij bulo vpershe zastosovano do bagatostupenevih modelej virishuvannya zokrema markovskih procesiv virishuvannya Changom Fu Hu i Markusom 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 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 empirichno Liva 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 virishuvannya MDP predstavlenih Changom ta in 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 Perevagi ta nedolikiHocha bulo dovedeno sho ocinka hodiv u derevi poshuku Monte Karlo shoditsya do minimaksa bazova versiya dereva poshuku Monte Karlo zbigayetsya lishe v tak zvanih igrah Monte Carlo Perfect 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 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 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 Vvazhayetsya sho ce moglo buti odniyeyu z prichin 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 PokrashennyaDlya 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 Ci evristichni metodi mozhut vikoristovuvati rezultati poperednih rozigrashiv napriklad metod ostannoyi garnoyi vidpovidi 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 Paradoksalno ale neoptimalna gra v simulyaciyi inodi robit programu dereva poshuku Monte Karlo silnishe v kincevomu rozrahunku 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 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 Shozhij metod yakij nazivayetsya progresivnim zmishennyam polyagaye v dodavanni do formuli UCB1 b i n i displaystyle frac b i n i de bi evristichna ocinka i go hodu 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 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 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 maye najbilshe znachennya U cij formuli w i displaystyle tilde w i ce kilkist vigranih rozigruvan yaki mistyat hid i n i displaystyle tilde n i ce kilkist usih rozigruvan yaki mistyat hid i b n i n i displaystyle beta n i tilde n i funkciya yaka nablizhayetsya do odinici dlya vidnosno malih ni i do nulya dlya vidnosno velikih n i displaystyle tilde n i Odna z bagatoh formul dlya b n i n i displaystyle beta n i tilde n i yaku zaproponuvav D Silver 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 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 Derevo poshuku Monte Karlo mozhe odnochasno obrahovuvatis bagatma potokami abo procesami Isnuye dekilka principovo riznih metodiv jogo paralelnogo vikonannya 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 Div takozhAlphaGo programa dlya Go sho vikoristovuye derevo poshuku Monte Karlo navchannya z pidkriplennyam i gliboke navchannya 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 PrimitkiSilver David Maddison Chris J Guez Arthur Sifre Laurent Driessche George van den Schrittwieser Julian Antonoglou Ioannis Panneershelvam Veda 28 sichnya 2016 Mastering the game of Go with deep neural networks and tree search Nature 529 7587 484 489 Bibcode 2016Natur 529 484S doi 10 1038 nature16961 ISSN 0028 0836 PMID 26819042 gt Artificial Intelligence A Modern Approach vid 3rd Prentice Hall 2009 Jonathan Rubin Ian Watson April 2011 PDF Artificial Intelligence 175 5 6 958 987 doi 10 1016 j artint 2010 12 005 Arhiv originalu PDF za 13 serpnya 2012 AI Game Dev Arhiv originalu za 13 March 2017 Procitovano 25 lyutogo 2017 Tesla s AI Day video https youtube com watch v j0z4FweCy4M 15 grudnya 2021 u Wayback Machine Abramson Bruce 1987 PDF Technical report Department of Computer Science Columbia University Arhiv originalu PDF 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 red 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 Journal of Neural Networks Research amp Applications 2 1 3 16 Arhiv originalu za 15 kvitnya 2021 Procitovano 15 grudnya 2021 Brugmann Bernd 1993 PDF Technical report Department of Physics Syracuse University Arhiv originalu PDF za 14 kvitnya 2021 Procitovano 15 grudnya 2021 Chang Hyeong Soo Fu Michael C Hu Jiaqiao Marcus Steven I 2005 PDF Operations Research 53 126 139 doi 10 1287 opre 1040 0145 Arhiv originalu PDF za 20 kvitnya 2021 Procitovano 15 grudnya 2021 Hyeong Soo Chang Michael Fu Jiaqiao Hu Steven I Marcus 2016 OR MS Today 45 5 24 29 Arhiv originalu za 15 grudnya 2021 Procitovano 15 grudnya 2021 Arhiv originalu za 6 travnya 2021 Procitovano 3 travnya 2012 2008 The Monte Carlo Revolution in Go Japanese French Frontiers of Science Symposium 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 ISBN 3 540 45375 X a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite conference title Shablon Cite conference cite conference a Propushenij abo porozhnij title dovidka Sylvain Gelly Yizao Wang Remi Munos Olivier Teytaud November 2006 PDF Technical report INRIA Arhiv originalu PDF 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 Tzung Pei Hong 2009 PDF IEEE Transactions on Computational Intelligence and AI in Games 1 1 73 89 doi 10 1109 tciaig 2009 2018703 Arhiv originalu PDF za 26 veresnya 2013 Procitovano 15 grudnya 2021 Markus Enzenberger Martin Muller 2008 PDF Technical report University of Alberta Arhiv originalu PDF za 9 lipnya 2021 Procitovano 15 grudnya 2021 Arhiv originalu za 14 kvitnya 2021 Procitovano 2 travnya 2012 Google Research Blog 27 sichnya 2016 Arhiv originalu za 30 sichnya 2016 Procitovano 15 grudnya 2021 BBC News 27 sichnya 2016 Arhiv originalu za 2 grudnya 2021 Procitovano 15 grudnya 2021 Youtube 9 bereznya 2016 Arhiv originalu za 29 bereznya 2017 Procitovano 15 grudnya 2021 ZDNet 28 sichnya 2016 Arhiv originalu za 31 sichnya 2016 Procitovano 15 grudnya 2021 Broderick Arneson Ryan Hayward Philip Henderson June 2009 PDF 32 2 114 116 doi 10 3233 ICG 2009 32218 Arhiv originalu PDF za 16 kvitnya 2021 Procitovano 15 grudnya 2021 Timo Ewalds 2011 PDF Master s thesis University of Alberta Arhiv originalu PDF 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 PDF Master s thesis Charles University in Prague Arhiv originalu PDF 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 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 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 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a archive url vimagaye url dovidka Istvan Szita Guillaume Chaslot Pieter Spronck 2010 Monte Carlo Tree Search in Settlers of Catan U Jaap Van Den Herik red 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 G M J B Chaslot M H M Winands J W H M Uiterwijk H J van den Herik B Bouzy 2008 PDF New Mathematics and Natural Computation 4 3 343 359 doi 10 1142 s1793005708001094 Arhiv originalu PDF za 14 kvitnya 2021 Procitovano 15 grudnya 2021 Bradberry Jeff 7 veresnya 2015 Arhiv originalu za 17 chervnya 2021 Procitovano 15 grudnya 2021 Peres Yuval 2006 Random Turn Hex and other selection games arXiv abs math 0508580 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite arXiv title Shablon Cite arXiv cite arXiv a Perevirte znachennya arxiv dovidka 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 T 7168 s 258 269 doi 10 1007 978 3 642 31866 5 22 ISBN 978 3 642 31865 8 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 Arhiv originalu za 26 zhovtnya 2021 Procitovano 15 grudnya 2021 Ramanujan Raghuram Selman Bart March 2011 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 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 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 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a archive url vimagaye url dovidka David Silver 2009 PDF PhD thesis University of Alberta Arhiv originalu PDF za 3 bereznya 2022 Procitovano 15 grudnya 2021 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 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 red 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 BibliografiyaCameron Browne Edward Powley Daniel Whitehouse Simon Lucas Peter I Cowling Philipp Rohlfshagen Stephen Tavener Diego Perez Spyridon Samothrakis 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 PosilannyaPosibnik dlya pochatkivciv z dereva poshuku Monte Karlo 15 grudnya 2021 u Wayback Machine

Дата публікації:
Топ