stringtranslate.com

Поиск по дереву Монте-Карло

В информатике поиск по дереву Монте-Карло ( MCTS ) — это эвристический алгоритм поиска для некоторых видов процессов принятия решений , в частности, тех, которые используются в программном обеспечении для настольных игр . В этом контексте MCTS используется для решения дерева игры .

В 2016 году MCTS был объединен с нейронными сетями [1] и использовался в нескольких настольных играх, таких как шахматы , сёги [2] , шашки , нарды , контрактный мост , го , скрэббл и клоббер [3], а также в пошаговых стратегических видеоиграх (например, реализация Total War: Rome II в высокоуровневой кампании ИИ [4] ) и приложениях за пределами игр. [5]

История

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

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

Подобные методы затем были исследованы и успешно применены для эвристического поиска в области автоматизированного доказательства теорем В. Эртелем, Дж. Шуманном и К. Саттнером в 1989 году [8] [9] [10], тем самым улучшая экспоненциальное время поиска неинформированных алгоритмов поиска, таких как, например, поиск в ширину, поиск в глубину или итеративное углубление .

В 1992 году Б. Брюгманн впервые применил его в программе для игры в Го . [11] В 2002 году Чанг и др. [12] предложили идею «рекурсивного развертывания и возврата» с «адаптивными» выборками в своем алгоритме адаптивной многоэтапной выборки (AMS) для модели марковских процессов принятия решений . AMS была первой работой, в которой исследовалась идея исследования и эксплуатации на основе UCB при построении выборочных/моделированных (Монте-Карло) деревьев и была основным источником для UCT (верхних деревьев доверия). [13]

Поиск по дереву Монте-Карло (MCTS)

Рейтинг лучших программ для игры в Го на сервере KGS с 2007 года. С 2006 года все лучшие программы используют поиск по дереву Монте-Карло. [14]

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

В январе 2012 года программа Zen выиграла со счетом 3:1 в матче по го на доске 19×19 с игроком -любителем , имеющим 2 дан . [21] Google Deepmind разработала программу AlphaGo , которая в октябре 2015 года стала первой компьютерной программой го, которая победила профессионального игрока в го без гандикапов на полноразмерной доске 19×19. [1] [22] [23] В марте 2016 года AlphaGo была удостоена почетного 9-го дана (мастерского) уровня в го 19×19 за победу над Ли Седолем в матче из пяти игр с окончательным счетом четыре игры к одной. [24] AlphaGo представляет собой значительное улучшение по сравнению с предыдущими программами го, а также является важной вехой в машинном обучении , поскольку она использует поиск по дереву Монте-Карло с искусственными нейронными сетями ( метод глубокого обучения ) для политики (выбора хода) и ценности, что дает ей эффективность, намного превосходящую предыдущие программы. [25]

Алгоритм MCTS также использовался в программах, которые играют в другие настольные игры (например, Hex , [26] Havannah , [27] Game of the Amazons , [28] и Arimaa [29] ), видеоигры в реальном времени (например, Ms. Pac-Man [30] [31] и Fable Legends [32] ), а также недетерминированные игры (такие как skat , [33] poker , [34] Magic: The Gathering , [35] или Settlers of Catan [36] ).

Принцип действия

Основное внимание MCTS уделяется анализу наиболее перспективных ходов, расширяя дерево поиска на основе случайной выборки пространства поиска. Применение поиска по дереву Монте-Карло в играх основано на многих розыгрышах, также называемых выкатами . В каждом розыгрыше игра разыгрывается до самого конца путем случайного выбора ходов. Окончательный результат игры каждого розыгрыша затем используется для взвешивания узлов в дереве игры, чтобы в будущих розыгрышах с большей вероятностью выбирались лучшие узлы.

Самый простой способ использования переигрываний — это применение одинакового количества переигрываний после каждого допустимого хода текущего игрока, а затем выбор хода, который привел к наибольшему количеству побед. [11] Эффективность этого метода, называемого Чистым поиском игры Монте-Карло , часто увеличивается со временем, поскольку больше переигрываний назначается ходам, которые часто приводили к победе текущего игрока согласно предыдущим переигрыванию. Каждый раунд поиска дерева Монте-Карло состоит из четырех шагов: [37]

Шаг поиска по дереву Монте-Карло.

Этот график показывает шаги, вовлеченные в одно решение, причем каждый узел показывает отношение побед к общему количеству игровых ходов с этой точки в дереве игры для игрока, которого представляет узел. [38] На диаграмме выбора черные собираются сделать ход. Корневой узел показывает, что на данный момент у белых из этой позиции 11 побед из 21 игрового хода. Он дополняет общее количество побед черных 10/21, показанное вдоль трех черных узлов под ним, каждый из которых представляет возможный ход черных. Обратите внимание, что этот график не следует алгоритму UCT, описанному ниже.

Если белые проигрывают симуляцию, все узлы по выбору увеличивают свой счет симуляции (знаменатель), но среди них только черные узлы получают выигрыши (числитель). Если же вместо этого выигрывают белые, все узлы по выбору все равно увеличивают свой счет симуляции, но среди них только белые узлы получают выигрыши. В играх, где возможны ничьи, ничья приводит к увеличению числителя как для черных, так и для белых на 0,5, а знаменателя на 1. Это гарантирует, что во время выбора выбор каждого игрока расширяется в сторону наиболее перспективных ходов для этого игрока, что отражает цель каждого игрока максимизировать ценность своего хода.

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

Поиск игры Pure Monte Carlo

Эту базовую процедуру можно применить к любой игре, позиции которой обязательно имеют конечное число ходов и конечную длину. Для каждой позиции определяются все возможные ходы: k случайных игр разыгрываются до самого конца, и результаты записываются. Выбирается ход, ведущий к лучшему результату. Ничьи разрешаются честным подбрасыванием монеты . Чистый поиск игр Монте-Карло приводит к сильной игре в нескольких играх со случайными элементами, как в игре EinStein würfelt nicht! . Он сходится к оптимальной игре (поскольку k стремится к бесконечности) в играх с заполнением доски со случайным порядком ходов, например, в игре Hex со случайным порядком ходов. [39] AlphaZero от DeepMind заменяет шаг моделирования оценкой, основанной на нейронной сети. [2]

Разведка и эксплуатация

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

Первый компонент формулы выше соответствует эксплуатации; он высок для ходов с высоким средним коэффициентом выигрыша. Второй компонент соответствует исследованию; он высок для ходов с небольшим количеством симуляций.

Большинство современных реализаций поиска по дереву Монте-Карло основаны на некотором варианте UCT, корни которого уходят в алгоритм оптимизации моделирования AMS для оценки функции ценности в процессах принятия решений Маркова с конечным горизонтом (MDP), представленный Чангом и др. [12] (2005) в Operations Research . (AMS был первой работой, изучающей идею исследования и эксплуатации на основе UCB при построении выборочных/моделированных (Монте-Карло) деревьев и был основным источником для UCT. [13] )

Преимущества и недостатки

Хотя было доказано, что оценка ходов в поиске по дереву Монте-Карло сходится к минимаксу при использовании UCT, [17] [41] базовая версия поиска по дереву Монте-Карло сходится только в так называемых играх «Monte Carlo Perfect». [42] Однако поиск по дереву Монте-Карло действительно предлагает значительные преимущества по сравнению с альфа-бета-обрезкой и аналогичными алгоритмами, которые минимизируют пространство поиска.

В частности, чистый поиск по дереву Монте-Карло не нуждается в явной функции оценки . Простой реализации игровой механики достаточно для исследования пространства поиска (т. е. генерации разрешенных ходов в заданной позиции и условий окончания игры). Таким образом, поиск по дереву Монте-Карло может использоваться в играх без разработанной теории или в общем игровом процессе .

Игровое дерево в поиске по дереву Монте-Карло растет асимметрично, поскольку метод концентрируется на более перспективных поддеревьях. Таким образом [ сомнительно – обсудить ] он достигает лучших результатов, чем классические алгоритмы в играх с высоким коэффициентом ветвления .

Недостатком является то, что в определенных позициях могут быть ходы, которые выглядят внешне сильными, но которые на самом деле приводят к проигрышу из-за тонкой линии игры. Такие «состояния ловушек» требуют тщательного анализа для правильной обработки, особенно при игре против опытного игрока; однако MCTS может не «видеть» такие линии из-за своей политики выборочного расширения узлов. [43] [44] Считается, что это могло быть одной из причин проигрыша AlphaGo в ее четвертой игре против Ли Седоля . По сути, поиск пытается обрезать последовательности, которые менее релевантны. В некоторых случаях игра может привести к очень конкретной линии игры, которая важна, но которая упускается из виду при обрезке дерева, и поэтому этот результат «вне радара поиска». [45]

Улучшения

Различные модификации базового метода поиска по дереву Монте-Карло были предложены для сокращения времени поиска. Некоторые используют экспертные знания, специфичные для предметной области, другие — нет.

Поиск по дереву Монте-Карло может использовать как легкие , так и тяжелые розыгрыши. Легкие розыгрыши состоят из случайных ходов, в то время как тяжелые розыгрыши применяют различные эвристики для влияния на выбор ходов. [46] Эти эвристики могут использовать результаты предыдущих розыгрышей (например, эвристику Last Good Reply [47] ) или экспертные знания данной игры. Например, во многих программах игры в Го определенные шаблоны камней в части доски влияют на вероятность перемещения в эту область. [18] Как это ни парадоксально, играя неоптимально в симуляциях, иногда программа поиска по дереву Монте-Карло играет сильнее в целом. [48]

Модели ханэ (окружающие камни противника), используемые в розыгрышах программой MoGo. И черным, и белым выгодно поставить камень на средний квадрат, за исключением самой правой модели, где это выгодно только черным. [18]

Знания, специфичные для домена, могут быть использованы при построении дерева игры, чтобы помочь в эксплуатации некоторых вариантов. Один из таких методов назначает ненулевые априорные значения числу выигранных и сыгранных симуляций при создании каждого дочернего узла, что приводит к искусственно завышенным или заниженным средним показателям выигрышей, которые приводят к более или менее частому выбору узла на этапе выбора. [49] Связанный метод, называемый прогрессивным смещением , состоит в добавлении к формуле UCB1 элемента, где b i — эвристическая оценка i -го хода. [37]

Базовый поиск по дереву Монте-Карло собирает достаточно информации, чтобы найти наиболее перспективные ходы, только после многих раундов; до тех пор его ходы по сути случайны. Эта исследовательская фаза может быть значительно сокращена в определенном классе игр с использованием RAVE ( Rapid Action Value Estimation ). [49] В этих играх перестановки последовательности ходов приводят к одной и той же позиции. Как правило, это настольные игры, в которых ход включает размещение фигуры или камня на доске. В таких играх ценность каждого хода часто лишь незначительно зависит от других ходов.

В RAVE для заданного узла дерева игры N его дочерние узлы C i хранят не только статистику побед в розыгрышах, начатых в узле N, но и статистику побед во всех розыгрышах, начатых в узле N и ниже его, если они содержат ход i (также когда ход был сыгран в дереве, между узлом N и розыгрышем). Таким образом, на содержимое узлов дерева влияют не только ходы, сыгранные немедленно в данной позиции, но и те же ходы, сыгранные позже.

RAVE на примере крестиков-ноликов. В красных узлах статистика RAVE будет обновлена ​​после симуляции b1-a2-b3.

При использовании RAVE шаг выбора выбирает узел, для которого модифицированная формула UCB1 имеет наибольшее значение. В этой формуле и обозначают число выигранных розыгрышей, содержащих ход i , и число всех розыгрышей, содержащих ход i , а функция должна быть близка к единице и к нулю для относительно малых и относительно больших n i и , соответственно. Одна из многих формул для , предложенная Д. Сильвером [50], гласит, что в сбалансированных позициях можно взять , где b — эмпирически выбранная константа.

Эвристики, используемые в поиске по дереву Монте-Карло, часто требуют много параметров. Существуют автоматизированные методы настройки параметров для максимизации коэффициента выигрыша. [51]

Поиск по дереву Монте-Карло может выполняться одновременно многими потоками или процессами . Существует несколько принципиально различных методов его параллельного выполнения: [52]

Смотрите также

Ссылки

  1. ^ аб Сильвер, Дэвид ; Хуанг, Аджа ; Мэддисон, Крис Дж.; Гез, Артур; Сифре, Лоран; Дрессе, Джордж ван ден; Шритвизер, Джулиан; Антоноглу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нхам, Джон; Кальхбреннер, Нал; Суцкевер, Илья ; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грепель, Торе; Хассабис, Демис (28 января 2016 г.). «Освоение игры в го с помощью глубоких нейронных сетей и поиска по дереву». Природа . 529 (7587): 484–489. Бибкод : 2016Natur.529..484S. doi : 10.1038/nature16961. ISSN  0028-0836. PMID  26819042. S2CID  515925.Значок закрытого доступа
  2. ^ ab Silver, David (2017). «Освоение шахмат и сёги с помощью самостоятельной игры с использованием общего алгоритма обучения с подкреплением». arXiv : 1712.01815v1 [cs.AI].
  3. ^ Раджкумар, Прахалад. «Обзор методов Монте-Карло в играх» (PDF) . cs.umd.edu . Архивировано (PDF) из оригинала 2023-04-07.
  4. ^ "Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI". AI Game Dev . Архивировано из оригинала 13 марта 2017 года . Получено 25 февраля 2017 года .
  5. ^ Кеммерлинг, Марко; Люттике, Даниэль; Шмитт, Роберт Х. (1 января 2024 г.). «За пределами игр: систематический обзор приложений поиска по дереву нейронных Монте-Карло». Applied Intelligence . 54 (1): 1020–1046. arXiv : 2303.08060 . doi :10.1007/s10489-023-05240-w. ISSN  1573-7497.
  6. ^ Николас, Метрополис; Станислав, Улам (1949). «Метод Монте-Карло». Журнал Американской статистической ассоциации . 44 (247): 335–341. дои : 10.1080/01621459.1949.10483310. ПМИД  18139350.
  7. ^ Абрамсон, Брюс (1987). Модель ожидаемого результата игр для двух игроков (PDF) . Технический отчет, кафедра компьютерных наук Колумбийского университета . Получено 23 декабря 2013 г.
  8. ^ Вольфганг Эртель; Иоганн Шуман; Кристиан Саттнер (1989). «Изучение эвристики для средства доказательства теорем с использованием обратного распространения ошибки». У Дж. Ретти; К. Лейдлмайр (ред.). 5. Österreichische Искусственный интеллект-Tagung. Informatik-Fachberichte 208, стр. 87-95 . Спрингер. Архивировано из оригинала 15 апреля 2021 г. Проверено 14 августа 2016 г.
  9. ^ Кристиан Зутнер; Вольфганг Эртель (1990). «Автоматическое получение эвристических правил поиска». CADE90, 10-я международная конференция по автоматизированной дедукции. стр. 470–484. LNAI 449. Springer. Архивировано из оригинала 15.04.2021 . Получено 14.08.2016 .
  10. ^ Кристиан Зутнер; Вольфганг Эртель (1991). «Использование сетей обратного распространения для руководства поиском средства доказательства теорем». Журнал исследований и приложений нейронных сетей . 2 (1): 3–16. Архивировано из оригинала 15.04.2021 . Получено 14.08.2016 .
  11. ^ ab Brügmann, Bernd (1993). Monte Carlo Go (PDF) . Технический отчет, Физический факультет Сиракузского университета.
  12. ^ abc Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). «Адаптивный алгоритм выборки для решения марковских процессов принятия решений» (PDF) . Operations Research . 53 : 126–139. doi :10.1287/opre.1040.0145. hdl : 1903/6264 . Архивировано из оригинала (PDF) 2021-04-20 . Получено 25-02-2016 .
  13. ^ ab Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). «Alphago от Google DeepMind: необъявленная роль OR в новаторском достижении». OR/MS Today . 45 (5): 24–29.
  14. ^ "Библиотека сэнсэя: KGSBotRatings" (PDF) . Архивировано из оригинала 2009-06-25 . Получено 2012-05-03 .
  15. ^ Реми Кулом (2008). "Революция Монте-Карло в Го" (PDF) . Японско-французский симпозиум "Границы науки" .
  16. ^ Rémi Coulom (2007). "Эффективная селективность и резервные операторы в поиске по дереву Монте-Карло". Computers and Games, 5-я международная конференция, CG 2006, Турин, Италия, 29–31 мая 2006 г. Пересмотренные статьи . H. Jaap van den Herik, Paolo Ciancarini, HHLM Donkers (ред.). Springer. стр. 72–83. CiteSeerX 10.1.1.81.6817 . ISBN  978-3-540-75537-1.
  17. ^ abc Kocsis, Levente; Szepesvári, Csaba (2006). "Планирование Монте-Карло на основе бандита". В Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (ред.). Машинное обучение: ECML 2006, 17-я Европейская конференция по машинному обучению, Берлин, Германия, 18–22 сентября 2006 г., Труды . Конспект лекций по информатике. Том 4212. Springer. стр. 282–293. CiteSeerX 10.1.1.102.1296 . doi :10.1007/11871842_29. ISBN  3-540-45375-X.
  18. ^ abc Сильвен Желли; Изао Ванг; Реми Муньос; Оливье Тейто (ноябрь 2006 г.). Модификация UCT с помощью шаблонов в Монте-Карло Go (PDF) . Технический отчет, INRIA.
  19. ^ Чан-Шин Ли; Мэй-Хуэй Ван; Гийом Шасло; Жан-Батист Хук; Арпад Риммель; Оливье Тейто; Шан-Ронг Цай; Шун-Чин Сюй; Цунг-Пей Хонг (2009). «Вычислительный интеллект MoGo проявился на компьютерных турнирах по го на Тайване» (PDF) . Труды IEEE по вычислительному интеллекту и ИИ в играх . 1 (1): 73–89. CiteSeerX 10.1.1.470.6018 . doi :10.1109/tciaig.2009.2018703. S2CID  15266518. 
  20. ^ Маркус Энценбергер; Мартин Мюллер (2008). Fuego – фреймворк с открытым исходным кодом для настольных игр и движка Go на основе поиска по дереву Монте-Карло (PDF) . Технический отчет, Университет Альберты.
  21. ^ "The Shodan Go Bet" . Получено 2012-05-02 .
  22. ^ "Исследовательский блог: AlphaGo: Освоение древней игры Го с помощью машинного обучения". Google Research Blog . 27 января 2016 г.
  23. ^ "Google добился 'прорыва' в области ИИ, победив чемпиона по го". BBC News . 27 января 2016 г.
  24. ^ "Матч 1 - Google DeepMind Challenge Match: Ли Седоль против AlphaGo". Youtube . 9 марта 2016 г.
  25. ^ "Google AlphaGo AI полностью побеждает чемпиона Европы по го". ZDNet . 28 января 2016 г.
  26. ^ Бродерик Арнесон; Райан Хейворд; Филип Хендерсон (июнь 2009 г.). «MoHex Wins Hex Tournament» (PDF) . Журнал ICGA . 32 (2): 114–116. doi :10.3233/ICG-2009-32218.
  27. ^ Тимо Эвальдс (2011). Игра и решение Havannah (PDF) . Магистерская диссертация, Университет Альберты.
  28. ^ Ричард Дж. Лоренц (2008). «Амазонки открывают Монте-Карло». Компьютеры и игры, 6-я международная конференция, CG 2008, Пекин, Китай, 29 сентября – 1 октября 2008 г. Труды . H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark HM Winands (ред.). Springer. стр. 13–24. ISBN 978-3-540-87607-6.
  29. ^ Томаш Козелек (2009). Методы MCTS и игра Arimaa (PDF) . Магистерская работа, Карлов университет в Праге.
  30. ^ Сяокун Ган; Юн Бао; Чжанган Хан (декабрь 2011 г.). «Метод поиска в реальном времени в недетерминированной игре - г-жа Пак-Ман». Журнал ICGA . 34 (4): 209–222. doi : 10.3233/ICG-2011-34404.
  31. ^ Том Пепелс; Марк Х. М. Винандс; Марк Ланктот (сентябрь 2014 г.). «Поиск по дереву Монте-Карло в реальном времени в Ms Pac-Man». Труды IEEE по вычислительному интеллекту и ИИ в играх . 6 (3): 245–257. doi : 10.1109/tciaig.2013.2291577 .
  32. ^ Mountain, Gwaredd (2015). "Тактическое планирование и MCTS в реальном времени в Fable Legends". Архивировано из оригинала 2019-06-08 . Получено 2019-06-08 . .. мы реализовали подход, основанный на моделировании, который включал моделирование игрового процесса и использование MCTS для поиска потенциального пространства плана. В целом это сработало хорошо, ...
  33. ^ Майкл Буро; Джеффри Ричард Лонг; Тимоти Фуртак; Натан Р. Стертевант (2009). «Улучшение оценки состояния, вывода и поиска в карточных играх с трюками». IJCAI 2009, Труды 21-й Международной совместной конференции по искусственному интеллекту, Пасадена, Калифорния, США, 11–17 июля 2009 г. Крейг Бутилье (ред.). стр. 1407–1413. CiteSeerX 10.1.1.150.3077 . 
  34. ^ Джонатан Рубин; Ян Уотсон (апрель 2011 г.). «Компьютерный покер: обзор». Искусственный интеллект . 175 (5–6): 958–987. doi : 10.1016/j.artint.2010.12.005 .
  35. ^ CD Ward; PI Cowling (2009). "Поиск Монте-Карло, применяемый к выбору карт в Magic: The Gathering" (PDF) . Труды CIG'09 5-й международной конференции по вычислительному интеллекту и играм . IEEE Press. Архивировано из оригинала (PDF) 28.05.2016.
  36. ^ Иштван Сита; Гийом Шасло; Питер Шпронк (2010). "Поиск по дереву Монте-Карло в Settlers of Catan" (PDF) . В Яапе Ван Ден Херике; Питер Шпронк (ред.). Достижения в компьютерных играх, 12-я международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г. Пересмотренные статьи . Springer. стр. 21–32. ISBN 978-3-642-12992-6. Архивировано из оригинала (PDF) 2016-03-04 . Получено 2015-11-30 .
  37. ^ ab GMJB Часло; МХМ Винандс; JWHM Уитервейк; Х.Дж. ван ден Херик; Б. Бузи (2008). «Прогрессивные стратегии поиска в дереве Монте-Карло» (PDF) . Новая математика и естественные вычисления . 4 (3): 343–359. дои : 10.1142/s1793005708001094.
  38. ^ Брэдберри, Джефф (2015-09-07). «Введение в поиск по дереву Монте-Карло».
  39. ^ Перес, Юваль; Шрамм, Одед; Шеффилд, Скотт; Уилсон, Дэвид Б. (2006). «Random-Turn Hex и другие игры с выбором». arXiv : math/0508580 .
  40. ^ Ауэр, Питер; Чеза-Бьянки, Николо; Фишер, Пол (2002). «Конечный анализ задачи о многоруком бандите». Машинное обучение . 47 (2/3): 235–256. doi : 10.1023/a:1013689704352 . S2CID  207609497.
  41. ^ Браун, Кэмерон Б.; Поули, Эдвард; Уайтхаус, Дэниел; Лукас, Саймон М.; Коулинг, Питер И.; Ролфшаген, Филипп; Тавенер, Стивен; Перес, Диего; Самотракис, Спиридон; Колтон, Саймон (2012). «Обзор методов поиска в дереве Монте-Карло». Труды IEEE по вычислительному интеллекту и ИИ в играх . 4 (1): 1–43. doi :10.1109/tciaig.2012.2186810. ISSN  1943-068X.
  42. ^ Альтхёфер, Инго (2012). «Игры с заполнением доски со случайным порядком хода и совершенством Монте-Карло». Достижения в области компьютерных игр . Конспект лекций по информатике. Том 7168. С. 258–269. doi :10.1007/978-3-642-31866-5_22. ISBN 978-3-642-31865-8.
  43. ^ Рамануджан, Рагурам; Сабхарвал, Ашиш; Селман, Барт (май 2010 г.). «О состязательных пространствах поиска и планировании на основе выборки». ICAPS '10: Труды двадцатой международной конференции по автоматизированному планированию и составлению расписаний . Icaps'10: 242–245.
  44. ^ Рамануджан, Рагхурам; Селман, Барт (март 2011 г.). «Компромиссы в состязательном планировании на основе выборки». Труды Международной конференции по автоматизированному планированию и составлению расписаний . 21 (1): 202–209. doi : 10.1609/icaps.v21i1.13472 . S2CID  45147586.
  45. ^ "Ли Седоль побеждает AlphaGo в мастерском возвращении - Игра 4". Go Game Guru. Архивировано из оригинала 2016-11-16 . Получено 2017-07-04 .
  46. ^ Свеховски, М.; Мандзюк, Дж., «Самоадаптация игровых стратегий в общих игровых процессах» (2010), Труды IEEE по вычислительному интеллекту и ИИ в играх , том: 6(4), стр. 367-381, doi :10.1109/TCIAIG.2013.2275163, https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
  47. ^ Дрейк, Питер (декабрь 2009 г.). «Политика последнего хорошего ответа для Monte-Carlo Go». Журнал ICGA . 32 (4): 221–227. doi :10.3233/ICG-2009-32404.
  48. ^ Сет Пеллегрино; Питер Дрейк (2010). «Исследование влияния силы игры в Монте-Карло Го». Материалы Международной конференции по искусственному интеллекту 2010 г., ICAI 2010, 12–15 июля 2010 г., Лас-Вегас, Невада, США . Хамид Р. Арабния, Дэвид де ла Фуэнте, Елена Б. Козеренко, Хосе Анхель Оливас, Руи Чанг, Питер М. ЛаМоника, Раймонд А. Люцци, Ашу М.Г. Соло (ред.). ЦСРЭА Пресс. стр. 1015–1018. ISBN 978-1-60132-148-0.
  49. ^ ab Gelly, Sylvain; Silver, David (2007). "Combining Online and Offline Knowledge in UCT" (PDF) . Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007. Zoubin Ghahramani (ред.). ACM. pp. 273–280. ISBN 978-1-59593-793-3. Архивировано из оригинала (PDF) 28.08.2017.
  50. ^ Дэвид Сильвер (2009). Обучение с подкреплением и поиск на основе моделирования в компьютерном Go (PDF) . Кандидатская диссертация, Университет Альберты.
  51. ^ Реми Кулом . «CLOP: Уверенная локальная оптимизация для настройки параметров шумного черного ящика». ACG 2011: Advances in Computer Games 13 Conference, Тилбург, Нидерланды, 20–22 ноября .
  52. ^ Guillaume MJ-B. Chaslot, Mark HM Winands, Jaap van den Herik (2008). "Parallel Monte-Carlo Tree Search" (PDF) . Computers and Games, 6th International Conference, CG 2008, Пекин, Китай, 29 сентября – 1 октября 2008 г. Труды . H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark HM Winands (ред.). Springer. стр. 60–71. ISBN 978-3-540-87607-6.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
  53. ^ Маркус Энценбергер; Мартин Мюллер (2010). «Безблокировочный многопоточный алгоритм поиска по дереву Монте-Карло». В Яапе Ван Ден Херике; Питере Шпронке (ред.). Достижения в компьютерных играх: 12-я международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г., пересмотренные документы . Springer. стр. 14–20. CiteSeerX 10.1.1.161.1984 . ISBN  978-3-642-12992-6.

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

Внешние ссылки