Перегляд вихідного коду сторінки Дерево пошуку Монте-Карло

{{Infobox algorithm|class=[[Алгоритм пошуку]]|image=[[Файл:MCTS Algorithm.png|250пкс]]|data=|time=|best-time=|average-time=|space=|optimal=|complete=}}
{{Алгоритми пошуку графами}}
У [[Інформатика|інформатиці]] '''дерево пошуку Монте-Карло''' ({{lang-en|Monte Carlo tree search}}, '''ДПМК''')&nbsp;— це [[Евристичний алгоритм|евристичний]] [[алгоритм пошуку]] який можна використати для деяких видів [[Ухвалення рішень|процесів вирішування]], а особливо для тих, які використовуються в [[Програмне забезпечення|програмному забезпеченні,]] яке грає в [[Ігри на спеціальній дошці|настільні ігри з дошкою]]. У цьому контексті ДПМК використовується для побудови [[Дерево гри|дерева гри]].

У 2016 році ДПМК та нейронна мережа були об'єднанні для гри в [[Комп'ютерне ґо|Ґо]].<ref name="alphago">{{Cite journal|last=Silver|first=David|last2=Huang|first2=Aja|author-link2=Aja Huang|last3=Maddison|first3=Chris J.|last4=Guez|first4=Arthur|last5=Sifre|first5=Laurent|last6=Driessche|first6=George van den|last7=Schrittwieser|first7=Julian|last8=Antonoglou|first8=Ioannis|last9=Panneershelvam|first9=Veda|date=28 січня 2016|title=Mastering the game of Go with deep neural networks and tree search|journal=[[Nature (journal)|Nature]]|volume=529|issue=7587|pages=484–489|bibcode=2016Natur.529..484S|doi=10.1038/nature16961|issn=0028-0836|pmid=26819042}}{{Closed access}}</ref> Також цей алгоритм використовували в інших настільних іграх, таких як: [[шахи]] та [[сьоґі]]; іграх з неповною інформацією, таких як [[бридж]]<ref name="AIAP">>{{Cite book
|title=Artificial Intelligence: A Modern Approach
|url=https://archive.org/details/nlsiu.340.11.rus.27359
|year=2009
|publisher=[[Prentice Hall]]
|edition=3rd
}}</ref> і [[покер]]<ref name="cpr">{{Cite journal|last=Jonathan Rubin|last2=Ian Watson|date=April 2011|title=Computer poker: A review|url=https://www.cs.auckland.ac.nz/~jrub001/files/CPReviewPreprintAIJ.pdf|journal=Artificial Intelligence|volume=175|issue=5–6|pages=958–987|doi=10.1016/j.artint.2010.12.005|archive-url=https://web.archive.org/web/20120813081731/https://www.cs.auckland.ac.nz/~jrub001/files/CPReviewPreprintAIJ.pdf|archive-date=2012-08-13}}</ref>, а також у покрокових стратегічних відеоіграх (наприклад, [[Total War: Rome II]] в компанії зі штучним інтелектом високої складності<ref>{{Cite web|title=Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI|url=http://aigamedev.com/open/coverage/mcts-rome-ii/|website=AI Game Dev|accessdate=25 лютого 2017|archiveurl=https://web.archive.org/web/20170313041719/http://aigamedev.com/open/coverage/mcts-rome-ii/|archivedate=13 March 2017}}</ref>). ДПМК також використовувався в автомобілях з автопілотом. Його, наприклад використали в програмному забезпеченні Tesla Autopilot.<ref>Tesla's AI Day video https://youtube.com/watch?v=j0z4FweCy4M {{Webarchive|url=https://web.archive.org/web/20211215133348/https://www.youtube.com/watch?v=j0z4FweCy4M |date=15 грудня 2021 }}</ref>

== Історія ==

=== Метод Монте-Карло ===
Метод [[Метод Монте-Карло|Монте-Карло]] бере свій початок з 1940-х років. Він використовує випадкову вибірку для детерміністичних задач, які важко або неможливо вирішити за допомогою інших підходів. У своїй докторській дисертації 1987 року Брюс Абрамсон об'єднав [[Мінімакс|мінімаксний пошук]] із ''моделлю очікуваного результату'', яка використовує випадковий вибір дії у гри до кінця, замість [[Оцінювальна функція|оцінювальної функції]], яку використовують зазвичай. Абрамсон сказав, що модель очікуваного результату «виявилась точною, легко передбачувальною, такою, що можливо ефективно обчислити та можна легко використати незалежною від сфери завдання».<ref name="Abramson">{{Cite book
|url=http://academiccommons.columbia.edu/download/fedora_content/download/ac:142327/CONTENT/CUCS-315-87.pdf
|title=The Expected-Outcome Model of Two-Player Games
|last=Abramson
|first=Bruce
|year=1987
|publisher=Technical report, Department of Computer Science, Columbia University
|accessdate=23 грудня 2013
|archive-date=27 жовтня 2016
|archive-url=https://web.archive.org/web/20161027040145/http://academiccommons.columbia.edu/download/fedora_content/download/ac:142327/CONTENT/CUCS-315-87.pdf
}}</ref> Він багато експериментував з [[Хрестики-нулики|хрестиками-ноликами]], а потім з оцінювальними функціями, які було згенеровано машиною для [[реверсі]] та [[Шахи|шахів]].

Потім такий метод було досліджено та успішно застосовано В. Ертелом, Дж. Шуманом та К. Зутнером у 1989 році для евристичного пошуку в області [[Автоматизоване доведення теорем|автоматизованого доведення теорем]]<ref>{{Cite book
|title=5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95.
|last=Wolfgang Ertel
|last2=Johann Schumann
|last3=Christian Suttner
|year=1989
|editor-last=J. Retti
|publisher=Springer
|chapter=Learning Heuristics for a Theorem Prover using Back Propagation.
}}</ref><ref>{{Cite book
|title=CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449.
|last=Christian Suttner
|last2=Wolfgang Ertel
|year=1990
|publisher=Springer
|chapter=Automatic Acquisition of Search Guiding Heuristics.
}}</ref><ref>{{Cite journal|last=Christian Suttner|last2=Wolfgang Ertel|date=1991|title=Using Back-Propagation Networks for Guiding the Search of a Theorem Prover.|url=http://www.hs-weingarten.de/~ertel/veroeff_bib.html#ES90:IJNN|journal=Journal of Neural Networks Research & Applications|volume=2|issue=1|pages=3–16|accessdate=15 грудня 2021|archive-date=15 квітня 2021|archive-url=https://web.archive.org/web/20210415031802/http://www.hs-weingarten.de/~ertel/veroeff_bib.html#ES90:IJNN}}</ref>, таким чином зменшуючи час виконання з експоненціального неінформованих алгоритмів пошуку, таких як, [[пошук у ширину]], пошук у глибину або з [[пошук в глибину з ітеративним заглибленням]].

У 1992 році Б. Брюгманн вперше застосував його для гри в [[Комп'ютерне ґо|Ґо]].<ref name="Bruegmann">{{Cite book
|url=http://www.ideanest.com/vegos/MonteCarloGo.pdf
|title=Monte Carlo Go
|last=Brügmann
|first=Bernd
|year=1993
|publisher=Technical report, Department of Physics, Syracuse University
|accessdate=15 грудня 2021
|archive-date=14 квітня 2021
|archive-url=https://web.archive.org/web/20210414125720/http://www.ideanest.com/vegos/MonteCarloGo.pdf
}}</ref> У 2002 році Чанг та інші<ref name="Chang2005">{{Cite journal|last=Chang|first=Hyeong Soo|last2=Fu|first2=Michael C.|last3=Hu|first3=Jiaqiao|last4=Marcus|first4=Steven I.|year=2005|title=An Adaptive Sampling Algorithm for Solving Markov Decision Processes|url=http://scholar.rhsmith.umd.edu/sites/default/files/mfu/files/cfhm05.pdf?m=1449834091|journal=Operations Research|volume=53|pages=126–139|doi=10.1287/opre.1040.0145|accessdate=15 грудня 2021|archive-date=20 квітня 2021|archive-url=https://web.archive.org/web/20210420114214/https://scholar.rhsmith.umd.edu/sites/default/files/mfu/files/cfhm05.pdf?m=1449834091}}</ref> запропонували ідею «рекурсивного розгортання та зворотного відстеження» з «адаптивним» вибором вибірки у своєму алгоритмі адаптивної багатоступеневої вибірки ({{lang-en|Adaptive Multi-stage Sampling, AMS}}) для моделі [[Марковський процес вирішування|марковських процесів вирішування]]. АБВ був першим алгоритмом, який використав ідею {{Не перекладено|Вибірка Томпсона|розвідки та експлуатації на основі UCB|en|Thompson_sampling}} для побудови дерев вибірки/моделювання (Монте-Карло) і послужив основою для верхніх дерев довіри ({{lang-en|Upper Confidence Trees, UCT}}).<ref name="changORMStoday">{{Cite journal|last=Hyeong Soo Chang|last2=Michael Fu|last3=Jiaqiao Hu|last4=Steven I. Marcus|year=2016|title=Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement|url=https://www.informs.org/ORMS-Today/Public-Articles/October-Volume-43-Number-5|journal=OR/MS Today|volume=45|issue=5|pages=24–29|accessdate=15 грудня 2021|archive-date=15 грудня 2021|archive-url=https://web.archive.org/web/20211215133348/https://www.informs.org/ORMS-Today/Public-Articles/October-Volume-43-Number-5}}</ref>

=== Дерево пошуку Монте-Карло ===
[[Файл:Computer-go-ratings-English.svg|міні| Рейтинг найкращих програм для гри в Ґо на сервері KGS з 2007 року. З 2006 року всі найкращі програми використовують алгоритм дерева пошуку Монте-Карло.<ref>{{Cite web|url=http://senseis.xmp.net/?KGSBotRatings|title=Sensei's Library: KGSBotRatings|accessdate=2012-05-03|archive-date=6 травня 2021|archive-url=https://web.archive.org/web/20210506152255/https://senseis.xmp.net/?KGSBotRatings}}</ref>]]
У 2006 році, натхненний попередниками,<ref>{{Cite book
|title=Japanese-French Frontiers of Science Symposium
|last=Rémi Coulom
|authorlink1=Rémi Coulom
|year=2008
|chapter=The Monte-Carlo Revolution in Go
}}</ref> {{Не перекладено|Ремі Колум|3=en|4=Rémi Coulom}} описав застосування методу Монте-Карло для побудови дерева ігор і придумав назву: «Дерево Пошуку Монте-Карло»<ref>{{Cite book
|title=Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers
|url=https://archive.org/details/computersgamesco2006heri
|last=Rémi Coulom
|authorlink1=Rémi Coulom
|year=2007
|publisher=Springer
|pages=[https://archive.org/details/computersgamesco2006heri/page/n82 72]–83
|chapter=Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search
|isbn=978-3-540-75537-1
}}</ref> Л.Коксіс та Кс. Шепешварі розробили алгоритм UCT (Верхніх меж довіри, які застосовуються до дерев)<ref name="Kocsis-Szepesvari">{{Cite conference|isbn=3-540-45375-X}}</ref> а С. Геллі та інші впровадили UCT у свою програму MoGo.<ref name="Gelly-et-al">{{Cite book
|url=http://hal.inria.fr/docs/00/11/72/66/PDF/MoGoReport.pdf
|title=Modification of UCT with Patterns in Monte-Carlo Go
|last=Sylvain Gelly
|last2=Yizao Wang
|last3=Rémi Munos
|last4=Olivier Teytaud
|date=November 2006
|publisher=Technical report, INRIA
|accessdate=15 грудня 2021
|archive-date=30 липня 2014
|archive-url=https://web.archive.org/web/20140730050628/http://hal.inria.fr/docs/00/11/72/66/PDF/MoGoReport.pdf
}}</ref> У 2008 році MoGo досягла рівня [[Дан (ступінь)|дан]] (майстер) у Го 9×9,<ref>{{Cite journal|last=Chang-Shing Lee|last2=Mei-Hui Wang|last3=Guillaume Chaslot|last4=Jean-Baptiste Hoock|last5=Arpad Rimmel|last6=Olivier Teytaud|last7=Shang-Rong Tsai|last8=Shun-Chin Hsu|last9=Tzung-Pei Hong|year=2009|title=The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments|url=http://hal.inria.fr/docs/00/36/97/86/PDF/TCIAIG-2008-0010_Accepted_.pdf|journal=IEEE Transactions on Computational Intelligence and AI in Games|volume=1|issue=1|pages=73–89|doi=10.1109/tciaig.2009.2018703|accessdate=15 грудня 2021|archive-date=26 вересня 2013|archive-url=https://web.archive.org/web/20130926031115/http://hal.inria.fr/docs/00/36/97/86/PDF/TCIAIG-2008-0010_Accepted_.pdf}}</ref> і програма Fuego почала перемагати у сильних гравців-аматорів у Го 9×9.<ref>{{Cite book
|url=http://pug.raph.free.fr/files/Fuego.pdf
|title=Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search
|last=Markus Enzenberger
|last2=Martin Mūller
|year=2008
|publisher=Technical report, University of Alberta
|accessdate=15 грудня 2021
|archive-date=9 липня 2021
|archive-url=https://web.archive.org/web/20210709135309/http://pug.raph.free.fr/files/Fuego.pdf
}}</ref>

У січні 2012 року програма Дзен перемогла з рахунком 3:1 у матчі Го на дошці 19×19 з {{Не перекладено|Ранги і рейтинги Ґо|гравцем-аматором з 2 даном|en|Go ranks and ratings}}.<ref>{{Cite web|url=http://dcook.org/gobet/|title=The Shodan Go Bet|accessdate=2012-05-02|archive-date=14 квітня 2021|archive-url=https://web.archive.org/web/20210414124239/http://dcook.org/gobet/}}</ref> [[DeepMind|Google Deepmind]] розробив програму [[AlphaGo]], яка в жовтні 2015 року стала першою програмою гри в Ґо, яка змогла обіграти професійного гравця в Ґо без {{Не перекладено|Фора в Ґо|фори|en|Handicapping in Go}} на повнорозмірній дошці 19x19.<ref name="alphago"/><ref>{{Cite web|url=http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html|title=Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning|date=27 січня 2016|website=Google Research Blog|accessdate=15 грудня 2021|archive-date=30 січня 2016|archive-url=https://web.archive.org/web/20160130003400/http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html}}</ref><ref>{{Cite web|url=https://www.bbc.com/news/technology-35420579|title=Google achieves AI 'breakthrough' by beating Go champion|date=27 січня 2016|website=BBC News|accessdate=15 грудня 2021|archive-date=2 грудня 2021|archive-url=https://web.archive.org/web/20211202120959/https://www.bbc.com/news/technology-35420579}}</ref> У березні 2016 року AlphaGo отримав почесний рівень 9 дану (майстер) у Ґо 19×19 за перемогу над [[Лі Седол]]ом у {{Не перекладено|AphaGo проти Лі Седола|серії з п'ятьох ігор|en|AlphaGo versus Lee Sedol}} з підсумковим рахунком чотири перемоги проти однієї поразки.<ref>{{Cite web|url=https://www.youtube.com/watch?v=vFr3K2DORc8&t=1h57m|title=Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo|date=9 березня 2016|website=Youtube|accessdate=15 грудня 2021|archive-date=29 березня 2017|archive-url=https://web.archive.org/web/20170329005648/https://www.youtube.com/watch?v=vFr3K2DORc8&t=1h57m}}</ref> AlphaGo являє собою значне покращення в порівнянні з попередніми програмами гри в Ґо. Також вона знаменувала нову віху в [[Машинне навчання|машинному навчанні,]] оскільки вона використовує дерево пошуку Монте-Карло у поєднанні зі [[Штучна нейронна мережа|штучною нейронною мережею]] ([[Глибоке навчання|метод глибокого навчання]]) для розробки стратегії, який є ефективним і значно перевершує попередні програми.<ref>{{Cite web|url=http://www.zdnet.com/article/google-alphago-ai-clean-sweeps-european-go-champion/|title=Google AlphaGo AI clean sweeps European Go champion|date=28 січня 2016|website=ZDNet|accessdate=15 грудня 2021|archive-date=31 січня 2016|archive-url=https://web.archive.org/web/20160131085535/http://www.zdnet.com/article/google-alphago-ai-clean-sweeps-european-go-champion/}}</ref>

Алгоритм ДПМК також використовували в програмах, які грали в інші [[Ігри на спеціальній дошці|настільні ігри на спеціальній дошці]] ([[Гекс]],<ref>{{Cite journal|last=Broderick Arneson|last2=Ryan Hayward|last3=Philip Henderson|date=June 2009|title=MoHex Wins Hex Tournament|url=http://webdocs.cs.ualberta.ca/~hayward/papers/rptPamplona.pdf|journal=[[ICGA Journal]]|volume=32|issue=2|pages=114–116|doi=10.3233/ICG-2009-32218|accessdate=15 грудня 2021|archive-date=16 квітня 2021|archive-url=https://web.archive.org/web/20210416092530/http://webdocs.cs.ualberta.ca/~hayward/papers/rptPamplona.pdf}}</ref> {{Не перекладено|Гаванна|Гаванна|en|Havannah (board game)}},<ref>{{Cite book
|url=http://havannah.ewalds.ca/static/thesis.pdf
|title=Playing and Solving Havannah
|last=Timo Ewalds
|year=2011
|publisher=Master's thesis, University of Alberta
|accessdate=15 грудня 2021
|archive-date=4 березня 2016
|archive-url=https://web.archive.org/web/20160304051450/http://havannah.ewalds.ca/static/thesis.pdf
}}</ref> {{Не перекладено|Ігри Амазонок|3=en|4=Game of the Amazons}},<ref>{{Cite book
|title=Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings
|last=Richard J. Lorentz
|year=2008
|publisher=Springer
|pages=13–24
|chapter=Amazons Discover Monte-Carlo
|isbn=978-3-540-87607-6
}}</ref> і {{Не перекладено|Арімаа|3=en|4=Arimaa}}<ref>{{Cite book
|url=http://arimaa.com/arimaa/papers/TomasKozelekThesis/mt.pdf
|title=Methods of MCTS and the game Arimaa
|last=Tomáš Kozelek
|year=2009
|publisher=Master's thesis, Charles University in Prague
|accessdate=15 грудня 2021
|archive-date=16 квітня 2021
|archive-url=https://web.archive.org/web/20210416092715/http://arimaa.com/arimaa/papers/TomasKozelekThesis/mt.pdf
}}</ref>), [[Відеогра|відеоігри]] в реальному часі (наприклад, [[Ms. Pac-Man]]<ref>{{Cite journal|last=Xiaocong Gan|last2=Yun Bao|last3=Zhangang Han|date=December 2011|title=Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man|journal=[[ICGA Journal]]|volume=34|issue=4|pages=209–222|doi=10.3233/ICG-2011-34404}}</ref><ref>{{Cite journal|last=Tom Pepels|last2=Mark H. M. Winands|last3=Marc Lanctot|date=September 2014|title=Real-Time Monte Carlo Tree Search in Ms Pac-Man|journal=IEEE Transactions on Computational Intelligence and AI in Games|volume=6|issue=3|pages=245–257|doi=10.1109/tciaig.2013.2291577}}</ref> і {{Не перекладено|Fable Legends|3=en|4=Fable Legends}}<ref>{{Cite web|url=https://archives.nucl.ai/recording/tactical-planning-and-real-time-mcts-in-fable-legends/|title=Tactical Planning and Real-time MCTS in Fable Legends|last=Mountain|first=Gwaredd|date=2015|accessdate=2019-06-08|quote=..&nbsp;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,&nbsp;...|archive-date=8 червня 2019|archive-url=https://web.archive.org/web/20190608203340/https://archives.nucl.ai/recording/tactical-planning-and-real-time-mcts-in-fable-legends/}}</ref>), а також недетерміновані ігри (такі як [[Скат (гра)|скат]],<ref>{{Cite book
|title=IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009
|last=Michael Buro
|last2=Jeffrey Richard Long
|last3=Timothy Furtak
|last4=Nathan R. Sturtevant
|year=2009
|pages=1407–1413
|chapter=Improving State Evaluation, Inference, and Search in Trick-Based Card Games
}}</ref> [[покер]],<ref name="cpr"/> [[Magic: The Gathering]],<ref>{{Cite book
|title=CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games
|last=C.D. Ward
|last2=P.I. Cowling
|year=2009
|publisher=IEEE Press
|chapter=Monte Carlo Search Applied to Card Selection in Magic: The Gathering
|archiveurl=https://web.archive.org/web/20160528074031/http://scim.brad.ac.uk/staff/pdf/picowlin/CIG2009.pdf
|archivedate=2016-05-28
}}</ref> або [[Колонізатори (гра)|Колонізатори]]<ref>{{Cite book
|title=Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers
|last=István Szita
|last2=Guillaume Chaslot
|last3=Pieter Spronck
|year=2010
|editor-last=Jaap Van Den Herik
|publisher=Springer
|pages=21–32
|chapter=Monte-Carlo Tree Search in Settlers of Catan
|isbn=978-3-642-12992-6
}}</ref>).

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

Найпростіший спосіб використання розігрувань&nbsp;— це застосовувати однакову кількість розігрувань після кожного дозволеного ходу поточного гравця, а потім обрати хід, який привів до найбільшої кількості перемог.<ref name="Bruegmann"/> Ефективність цього методу, який називається ''чистий ігровий пошук Монте-Карло,'' часто зростає з часом, оскільки було проведено більше розіграшів для ходів, які частіше призводили до перемоги поточного гравця у порівнянні з попередніми розігруваннями. Кожен раунд побудови дерева пошуку Монте-Карло складається з чотирьох кроків:<ref name="chaslot2008">{{Cite journal|last=G.M.J.B. Chaslot|last2=M.H.M. Winands|last3=J.W.H.M. Uiterwijk|last4=H.J. van den Herik|last5=B. Bouzy|year=2008|title=Progressive Strategies for Monte-Carlo Tree Search|url=https://dke.maastrichtuniversity.nl/m.winands/documents/pMCTS.pdf|journal=New Mathematics and Natural Computation|volume=4|issue=3|pages=343–359|doi=10.1142/s1793005708001094|accessdate=15 грудня 2021|archive-date=14 квітня 2021|archive-url=https://web.archive.org/web/20210414151134/https://dke.maastrichtuniversity.nl/m.winands/documents/pMCTS.pdf}}</ref>

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

[[Файл:MCTS-steps.svg|центр|міні|800x800пкс| Крок у алгоритмі дерева пошуку Монте-Карло.]]
Цей графік показує частину алгоритму вибору одного рішення, де кожен вузол показує відношення виграшів до загальної кількості розіграшів з цієї точки в дереві гри для гравця, який представляє цей вузол.<ref>{{Cite web|url=http://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/|title=Introduction to Monte Carlo Tree Search|last=Bradberry|first=Jeff|date=2015-09-07|accessdate=15 грудня 2021|archive-date=17 червня 2021|archive-url=https://web.archive.org/web/20210617075136/https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/}}</ref> На діаграмі той, який грає за чорних, має ухвалити рішення. Судячи з кореневого вузла, білі з цієї позиції виграли 11 з 21 ігор. Також виходить, що чорні перемогли в 10 з 21 ігор, що виходить, якщо скласти значення трьох чорних вузлів під ним, які представляють можливі ходи чорних.

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

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

== Чистий ігровий пошук Монте-Карло ==
Цю базову процедуру можна застосувати до будь-якої гри з кінцевою кількістю ходів кінцевої довжини. Для кожної позиції визначаються всі можливі ходи: ''k'' випадкових ігор розігруються до самого кінця, а результати зберігаються. Обирається хід, який веде до найкращого результату. Зв'язки розриваються за допомогою підкидання монети. Чистий ігровий пошук Монте-Карло дає гарні результати при декількох іграх з випадковими елементами, як, наприклад у грі {{Не перекладено|EinStein würfelt nicht!|3=en|4=EinStein würfelt nicht!}}. Він сходиться до оптимальної стратегії (якщо ''k'' наближається до нескінченності) у настільних іграх із випадковим порядком ходу, наприклад у [[Гекс]].<ref>{{Cite arXiv|last=Peres|first=Yuval|title=Random-Turn Hex and other selection games|date=2006|eprint=abs/math/0508580}}</ref> AlphaZero від DeepMind замінив етап симуляції на використання оцінки на основі нейронної мережі.<ref name="AIAP"/>

== Розвідка та експлуатація ==
Основна складність у виборі дочірніх вузлів полягає в підтримці певного балансу між ''експлуатацією'' глибоких варіантів після ходів з високим середнім виграшем і ''розвідкою'' ходів з невеликою кількістю симуляцій. Першу формулу для балансування експлуатації та розвідки в іграх, яка називається UCT (''Upper Confidence Bound'' 1, яку було ''застосовано до дерев''), було виведено Левенте Кочисом і Чаба Шепешварі.<ref name="Kocsis-Szepesvari"/> UCT базується на формулі UCB1, виведеної Ауером, Чеза-Біанкі та Фішером<ref>{{Cite journal|last=Auer|first=Peter|last2=Cesa-Bianchi|first2=Nicolò|last3=Fischer|first3=Paul|year=2002|title=Finite-time Analysis of the Multiarmed Bandit Problem|journal=Machine Learning|volume=47|issue=2/3|pages=235–256|doi=10.1023/a:1013689704352}}</ref>, і на доказі збіжності алгоритму АБВ ({{lang-en|Adaptive Multi-stage Sampling}}), який було вперше застосовано до багатоступеневих моделей вирішування (зокрема, [[Марковський процес вирішування|марковських процесів вирішування]]) Чангом, Фу, Ху і Маркусом.<ref name="Chang2005"/> Кочис і Шепешварі рекомендували обирати в кожному вузлі дерева гри хід, для якого вираз <math>\frac{w_i}{n_i} + c\sqrt{\frac{\ln N_i}{n_i}}</math> набуває найбільшого значення. У цій формулі:

* {{Math|''w''<sub>''i''</sub>}} означає кількість виграшів для вузла після i-го ходу
* {{Math|''n''<sub>''i''</sub>}} означає кількість симуляцій для вузла після i-го переміщення
* {{Math|''N''<sub>''i''</sub>}} означає загальну кількість симуляцій батьківського вузла після i-го переміщення
* {{Math|''c''}} параметр розвідки, теоретично рівний {{Math|{{radic|2}}}}; на практиці зазвичай вибирається емпірично

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

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

== Переваги та недоліки ==
Хоча було доведено, що оцінка ходів у дереві пошуку Монте-Карло сходиться до [[мінімакс]]а<ref>{{Cite book
|title=IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii
|last=Bouzy
|first=Bruno
|chapter=Old-fashioned Computer Go vs Monte-Carlo Go
}}</ref>, базова версія дерева пошуку Монте-Карло збігається лише в так званих іграх «Monte Carlo Perfect».<ref>{{Cite book
|title=Advances in Computer Games
|last=Althöfer
|first=Ingo
|year=2012
|series=Lecture Notes in Computer Science
|volume=7168
|pages=258–269
|chapter=On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness
|doi=10.1007/978-3-642-31866-5_22
|isbn=978-3-642-31865-8
}}</ref> Однак дерево пошуку Монте-Карло має значні переваги у порівняні з [[Відсічення альфа-бета|альфа-бета відсіченням]] та подібними алгоритмами, що мінімізують простір пошуку.

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

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

Недоліком алгоритму є те, що в певних позиціях можуть бути ходи, які виглядають, на перший погляд, перспективними, але насправді призводять до програшу. Такі «стани пастки» вимагають ретельного аналізу та правильної обробки, особливо під час гри проти досвідченого гравця; однак ДПМК може не «помічати» такі лінії через свою стратегію вибіркового розширення вузлів.<ref>{{Cite journal|last=Ramanujan|first=Raghuram|last2=Sabharwal|first2=Ashish|last3=Selman|first3=Bart|date=May 2010|title=On adversarial search spaces and sampling-based planning|url=https://dl.acm.org/doi/10.5555/3037334.3037370|journal=ICAPS '10: Proceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling|pages=242-245|accessdate=15 грудня 2021|archive-date=26 жовтня 2021|archive-url=https://web.archive.org/web/20211026215913/https://dl.acm.org/doi/10.5555/3037334.3037370}}</ref><ref>{{Cite journal|last=Ramanujan|first=Raghuram|last2=Selman|first2=Bart|date=March 2011|title=Trade-Offs in Sampling-Based Adversarial Planning|url=https://ojs.aaai.org/index.php/ICAPS/article/view/13472|journal=ICAPS '11: Proceedings of the International Conference on Automated Planning and Scheduling|volume=21|issue=1|pages=202-209|accessdate=15 грудня 2021|archive-date=29 жовтня 2021|archive-url=https://web.archive.org/web/20211029121656/https://ojs.aaai.org/index.php/ICAPS/article/view/13472}}</ref> Вважається, що це могло бути однією з причин {{Не перекладено|AphaGo проти Лі Седола|поразки AlphaGo у четвертій грі проти Лі Седола|en|AlphaGo versus Lee Sedol}} через те, що алгоритм намагається обрізати менш релевантні послідовності. У деяких випадках гра може призвести до дуже специфічної лінії гри, яка є важливою, проте яку не помічає алгоритм і обрізає його. Така лінія знаходиться «поза радаром пошуку».<ref>{{Cite web|url=https://gogameguru.com/lee-sedol-defeats-alphago-masterful-comeback-game-4/|title=Lee Sedol defeats AlphaGo in masterful comeback - Game 4|publisher=Go Game Guru|accessdate=2017-07-04|archiveurl=https://web.archive.org/web/20161116082508/https://gogameguru.com/lee-sedol-defeats-alphago-masterful-comeback-game-4/|archivedate=2016-11-16}}</ref>

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

Дерево пошуку Монте-Карло може використовувати як ''легкі, так'' і ''важкі'' розігрування. Легкі розігрування складаються з випадкових ходів, тоді як важкі розігрування застосовують різні евристичні методи, щоб впливати на вибір ходів.<ref>Ś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</ref> Ці евристичні методи можуть використовувати результати попередніх розіграшів (наприклад, метод останньої гарної відповіді<ref>{{Cite journal|last=Drake|first=Peter|date=December 2009|title=The Last-Good-Reply Policy for Monte-Carlo Go|journal=ICGA Journal|volume=32|issue=4|pages=221–227|doi=10.3233/ICG-2009-32404}}</ref>) або експертні знання даної гри. Наприклад, у багатьох програмах для гри в Ґо певні візерунки каменів на частині дошки впливають на ймовірність переміщення в цю область.<ref name="Gelly-et-al"/> Парадоксально, але неоптимальна гра в симуляції іноді робить програму дерева пошуку Монте-Карло сильніше в кінцевому розрахунку.<ref>{{Cite book
|title=Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA
|last=Seth Pellegrino
|last2=Peter Drake
|year=2010
|publisher=CSREA Press
|pages=1015–1018
|chapter=Investigating the Effects of Playout Strength in Monte-Carlo Go
|isbn=978-1-60132-148-0
}}</ref>
[[Файл:Mogo-hane.svg|центр|обрамити| Візерунки ''хане'' (оточення каменів супротивника), які використовуються в розігруваннях програмою MoGo. Для чорного і білого вигідно поставити камінь на середній квадрат, за винятком крайнього правого візерунка, де він віддає перевагу лише чорному.<ref name="Gelly-et-al"/>]]
При побудові дерева гри можуть бути використані знання, що стосуються предметної області для того, щоб експлуатувати деякі варіанти. Один з таких методів призначає ненульові значення виграним і зіграним симуляціям під час створення кожного дочірнього вузла. Це призводить до штучно підвищення або зниження середнього рівня виграшу, що призводить до того, що вузол вибирається частіше або рідше.<ref name="Gelly-Silver">{{Cite book
|title=Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007
|last=Gelly
|first=Sylvain
|last2=Silver
|first2=David
|year=2007
|publisher=ACM
|pages=273–280
|chapter=Combining Online and Offline Knowledge in UCT
|isbn=978-1-59593-793-3
|archiveurl=https://web.archive.org/web/20170828123413/http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf
|archivedate=2017-08-28
}}</ref> Схожий метод, який називається ''прогресивним зміщенням'', полягає в додаванні до формули UCB1 <math>\frac{b_i}{n_i}</math>, де {{Math|''b''<sub>''i''</sub>}}&nbsp;— евристична оцінка {{Math|''i''}}-го ходу.<ref name="chaslot2008"/>

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

У RAVE для даного вузла дерева ігор {{Math|''N''}} його дочірні вузли {{Math|''C''<sub>''i''</sub>}} зберігають не тільки статистику перемог у розігруваннях, розпочатих у вузлі {{Math|''N''}}, але і статистику перемог у всіх розіграшах, які було розпочато у вузлі {{Math|''N''}} і нижче, якщо вони містять це переміщення. Таким чином, на вміст вузлів дерева впливають не тільки ходи, які виконуються в даній позиції, але й ті ходи, які виконуються пізніше.
[[Файл:Tic-tac-toe-RAVE-English.svg|центр|обрамити| RAVE на прикладі хрестиків-нуликів. У червоних вузлах статистика RAVE буде оновлена після моделювання b1-a2-b3.]]
При використанні RAVE під час етапу вибору обирається вузол, для якого модифікована формула UCB1 <math>(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}}</math> має найбільше значення. У цій формулі:

* <math>\tilde{w}_i</math>&nbsp;— це кількість виграних розігрувань, які містять хід {{Math|''i''}}.
* <math>\tilde{n}_i</math>- це кількість усіх розігрувань, які містять хід {{Math|''i''}}.
* <math>\beta(n_i, \tilde{n}_i)</math>&nbsp;— функція, яка наближається до одиниці для відносно малих {{Math|''n''<sub>''i''</sub>}} і до нуля для відносно великих <math>\tilde{n}_i</math>.

Одна з багатьох формул для <math>\beta(n_i, \tilde{n}_i)</math>, яку запропонував Д. Сільвер,<ref>{{Cite book
|url=http://papersdb.cs.ualberta.ca/~papersdb/uploaded_files/1029/paper_thesis.pdf
|title=Reinforcement Learning and Simulation-Based Search in Computer Go
|last=David Silver
|year=2009
|publisher=PhD thesis, University of Alberta
|accessdate=15 грудня 2021
|archive-date=3 березня 2022
|archive-url=https://web.archive.org/web/20220303125724/https://papersdb.cs.ualberta.ca/~papersdb/uploaded_files/1029/paper_thesis.pdf
}}</ref> стверджує, що в збалансованих позиціях можна вважати, що <math>\beta(n_i, \tilde{n}_i)=\frac{\tilde{n}_i}{n_i+\tilde{n}_i+4b^2 n_i\tilde{n}_i}</math>, де {{Math|''b''}}&nbsp;— емпірично обрана константа.

Обрахунки, що використовується в алгоритмі дерева пошуку Монте-Карло, часто залежать від багатьох параметрів. Існують автоматизовані методи налаштування параметрів, щоб максимізувати виграш.<ref>{{Cite book
|title=ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22
|last=Rémi Coulom
|authorlink1=Rémi Coulom
|chapter=CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning
}}</ref>

Дерево пошуку Монте-Карло може одночасно обраховуватись багатьма [[Потік (інформатика)|потоками]] або [[Процес (інформатика)|процесами]]. Існує декілька принципово різних методів його [[Паралельні обчислення|паралельного]] виконання:<ref>{{Cite book
|title=Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings
|last=Guillaume M.J-B. Chaslot, Mark H.M. Winands, [[Jaap van den Herik]]
|year=2008
|publisher=Springer
|pages=60–71
|chapter=Parallel Monte-Carlo Tree Search
|isbn=978-3-540-87607-6
}}</ref>

* ''Паралелізація'' листів, тобто паралельне виконання багатьох розігрувань одного листа ігрового дерева.
* ''Коренева паралелізація'', тобто паралельне створення незалежних ігрових дерев, які виконують ходи на основі коренів всіх цих дерев.
* ''Паралелізація дерева'', тобто паралельна побудова одного ігрового дерева, яке захищає дані від одночасного запису за допомогою одного глобального [[Блокування (програмування)|мьютексу]], з кількома м'ютексами або з [[Неблокуючий алгоритм|неблокуючою синхронізацією]].<ref>{{Cite book
|url=https://archive.org/details/advancescomputer00heri_938
|title=Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers
|last=Markus Enzenberger
|last2=Martin Müller
|year=2010
|editor-last=Jaap Van Den Herik
|publisher=Springer
|pages=[https://archive.org/details/advancescomputer00heri_938/page/n26 14]–20
|chapter=A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm
|isbn=978-3-642-12992-6
}}</ref>

== Див. також ==
* [[AlphaGo]], програма для Ґо, що використовує дерево пошуку Монте-Карло, [[навчання з підкріпленням]] і [[глибоке навчання]].
* {{Не перекладено|AlphaGo Zero}}, оновлена програма для Ґо, що використовує дерево пошуку Монте-Карло, [[навчання з підкріпленням]] і [[глибоке навчання]].
* [[AlphaZero]], узагальнена версія AlphaGo Zero з використанням дерева пошуку Монте-Карло, [[навчання з підкріпленням]] і [[Глибоке навчання|глибокого навчання]].
* [[Leela Chess Zero]], [[Вільне програмне забезпечення|безкоштовна програмна]] реалізація методів AlphaZero для гри в шахи, які на даний момент є однією з провідних програм для гри в шахи.

== Примітки ==
{{reflist}}

== Бібліографія ==
* {{Cite journal|last=Cameron Browne|last2=Edward Powley|last3=Daniel Whitehouse|last4=Simon Lucas|last5=Peter I. Cowling|last6=Philipp Rohlfshagen|last7=Stephen Tavener|last8=Diego Perez|last9=Spyridon Samothrakis|date=March 2012|title=A Survey of Monte Carlo Tree Search Methods|journal=IEEE Transactions on Computational Intelligence and AI in Games|volume=4|issue=1|pages=1–43|doi=10.1109/tciaig.2012.2186810}}

== Посилання ==
* [https://int8.io/monte-carlo-tree-search-beginners-guide/#Policy_network_training_in_Alpha_Go_and_Alpha_Zero Посібник для початківців з дерева пошуку Монте-Карло] {{Webarchive|url=https://web.archive.org/web/20211215133337/https://int8.io/monte-carlo-tree-search-beginners-guide/#Policy_network_training_in_Alpha_Go_and_Alpha_Zero |date=15 грудня 2021 }}

{{Бібліоінформація}}
[[Категорія:Оптимальні рішення]]
[[Категорія:Методи Монте-Карло]]
[[Категорія:Евристичні алгоритми]]