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

Алгоритм эвристического поиска для оценки игровых деревьев

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная трудность при выборе дочерних узлов заключается в поддержании некоторого баланса между использованием глубоких вариантов после ходов с высоким средним процентом выигрышей и исследованием ходов с небольшим количеством симуляций. Первую формулу балансировки эксплуатации и исследования в играх, получившую название UCT ( верхняя доверительная граница 1, применяемая к деревьям ), представили Левенте Кочиш и Чаба Сепешвари. ^[16] UCT основан на формуле UCB1, выведенной Ауэром, Чезой-Бьянки и Фишером ^[39] и вероятно конвергентном алгоритме AMS (адаптивной многоэтапной выборки), впервые примененном к многоэтапным моделям принятия решений (в частности, Марковской модели принятия решений). Процессы принятия решений ) Чанга, Фу, Ху и Маркуса. ^[11] Кочиш и Сепешвари рекомендуют выбирать в каждом узле дерева игры ход, для которого выражение имеет наибольшее значение. В этой формуле: ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$

• w _i обозначает количество побед рассматриваемого узла после i -го хода
• n _i обозначает количество симуляций для узла, рассматриваемого после i -го хода
• Ni обозначает общее количество симуляций после i -го _хода , выполненного родительским узлом рассматриваемого узла.
• c – параметр разведки, теоретически равный √ 2 ; на практике обычно выбирают эмпирически

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

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

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

Хотя было доказано, что оценка ходов при поиске по дереву Монте-Карло сходится к минимаксу при использовании UCT, ^{[16] [40]} базовая версия поиска по дереву Монте-Карло сходится только в так называемых «Идеальных играх Монте-Карло». ^[41] Однако поиск по дереву Монте-Карло действительно предлагает значительные преимущества по сравнению с альфа-бета-обрезкой и аналогичными алгоритмами, которые минимизируют пространство поиска.

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

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

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

Улучшения

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

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

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

Знания, специфичные для предметной области, могут использоваться при построении дерева игры, чтобы помочь в использовании некоторых вариантов. Один из таких методов присваивает ненулевые априорные значения количеству выигранных и сыгранных симуляций при создании каждого дочернего узла, что приводит к искусственному повышению или понижению среднего показателя выигрыша, что приводит к более или менее частому выбору узла на этапе выбора соответственно. ^[48] ​​Родственный метод, называемый прогрессивным смещением , заключается в добавлении к формуле UCB1 элемента, где b _i — эвристическая оценка i -го хода. ^[36] ${\displaystyle {\frac {b_{i}}{n_{i}}}}$

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

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

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

При использовании RAVE на этапе выбора выбирается узел, для которого модифицированная формула UCB1 имеет наибольшее значение. В этой формуле и обозначают количество выигранных розыгрышей, содержащих ход i , и количество всех розыгрышей, содержащих ход i , причем функция должна быть близка к единице и нулю для относительно малых и относительно больших n _i и соответственно. Одна из многих формул для , предложенная Д. Сильвером ^[49], говорит, что в сбалансированных положениях можно взять , где b — эмпирически выбранная константа. ${\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}}}}}$ ${\displaystyle {\tilde {w}}_{i}}$ ${\displaystyle {\tilde {n}}_{i}}$ ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ ${\displaystyle {\tilde {n}}_{i}}$ ${\displaystyle \beta (n_{i},{\tilde {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}}}}$

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

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

• Распараллеливание листьев , т.е. параллельное выполнение множества плейаутов из одного листа игрового дерева.
• Корневое распараллеливание , то есть параллельное построение независимых игровых деревьев и выполнение хода на основе ветвей корневого уровня всех этих деревьев.
• Распараллеливание дерева , т.е. параллельное построение одного и того же игрового дерева, защита данных от одновременной записи либо с одним, глобальным мьютексом , с большим количеством мьютексов, либо с неблокирующей синхронизацией . ^[52]

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

• AlphaGo — программа Go, использующая поиск по дереву Монте-Карло, обучение с подкреплением и глубокое обучение .
• AlphaGo Zero — обновленная программа Go, использующая поиск по дереву Монте-Карло, обучение с подкреплением и глубокое обучение .
• AlphaZero — обобщенная версия AlphaGo Zero, использующая поиск по дереву Монте-Карло, обучение с подкреплением и глубокое обучение .
• Leela Chess Zero — бесплатная программная реализация методов AlphaZero в шахматах, которая в настоящее время входит в число ведущих программ для игры в шахматы.

Рекомендации

1. Сильвер, Дэвид ; Хуанг, Аджа ; Мэддисон, Крис Дж.; Гез, Артур; Сифре, Лоран; Дрессе, Джордж ван ден; Шритвизер, Джулиан; Антоноглу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нэм, Джон; Кальхбреннер, Нал; Суцкевер, Илья ; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грепель, Торе; Хассабис, Демис (28 января 2016 г.). «Освоение игры в го с помощью глубоких нейронных сетей и поиска по дереву». Природа . 529 (7587): 484–489. Бибкод : 2016Natur.529..484S. дои : 10.1038/nature16961. ISSN  0028-0836. PMID  26819042. S2CID  515925.
2. Сильвер, Дэвид (2017). «Освоение шахмат и сёги путем самостоятельной игры с помощью общего алгоритма обучения с подкреплением». arXiv : 1712.01815v1 [cs.AI].
3. Раджкумар, Прахалад. «Обзор методов Монте-Карло в играх» (PDF) . cs.umd.edu . Архивировано (PDF) из оригинала 7 апреля 2023 г.
4. «Поиск дерева Монте-Карло в AI кампании TOTAL WAR: ROME II» . Разработчик игр с искусственным интеллектом . Архивировано из оригинала 13 марта 2017 года . Проверено 25 февраля 2017 г. .
5. Николас, Метрополис; Станислав, Улам (1949). «Метод Монте-Карло». Журнал Американской статистической ассоциации . 44 (247): 335–341. дои : 10.1080/01621459.1949.10483310. ПМИД  18139350.
6. Абрамсон, Брюс (1987). Модель ожидаемого результата игр для двух игроков (PDF) . Технический отчет, факультет компьютерных наук, Колумбийский университет . Проверено 23 декабря 2013 г.
7. Вольфганг Эртель; Иоганн Шуман; Кристиан Саттнер (1989). «Изучение эвристики для средства доказательства теорем с использованием обратного распространения ошибки». У Дж. Ретти; К. Лейдлмайр (ред.). 5. Österreichische Искусственный интеллект-Tagung. Информатик-Фахберихте 208, стр. 87-95 . Спрингер. Архивировано из оригинала 15 апреля 2021 г. Проверено 14 августа 2016 г.
8. Кристиан Саттнер; Вольфганг Эртель (1990). «Автоматическое получение эвристики, направляющей поиск». CADE90, 10-й Международный. Конф. на Автоматизированном Вычете.стр. 470-484. ЛНАИ 449 . Спрингер. Архивировано из оригинала 15 апреля 2021 г. Проверено 14 августа 2016 г.
9. Кристиан Саттнер; Вольфганг Эртель (1991). «Использование сетей обратного распространения ошибки для поиска средства доказательства теорем». Журнал исследований и приложений нейронных сетей . 2 (1): 3–16. Архивировано из оригинала 15 апреля 2021 г. Проверено 14 августа 2016 г.
10. Брюгманн, Бернд (1993). Монте-Карло Го (PDF) . Технический отчет, факультет физики Сиракузского университета.
11. Чанг, Хён Су; Фу, Майкл С.; Ху, Цзяцяо; Маркус, Стивен И. (2005). «Адаптивный алгоритм выборки для решения марковских процессов принятия решений» (PDF) . Исследование операций . 53 : 126–139. дои : 10.1287/opre.1040.0145. hdl : 1903/6264 . Архивировано из оригинала (PDF) 20 апреля 2021 г. Проверено 25 февраля 2016 г.
12. Хён Су Чанг; Майкл Фу; Цзяцяо Ху; Стивен И. Маркус (2016). «Alphago Google DeepMind: необъявленная роль OR в новаторском достижении». ОР/МС сегодня . 45 (5): 24–29.
13. «Библиотека сэнсэя: KGSBotRatings» (PDF) . Архивировано из оригинала 25 июня 2009 г. Проверено 3 мая 2012 г.
14. Реми Кулом (2008). «Революция Монте-Карло в го» (PDF) . Симпозиум «Японо-французские границы науки» .
15. Реми Кулом (2007). «Эффективные операторы избирательности и резервного копирования в поиске по дереву Монте-Карло». Компьютеры и игры, 5-я Международная конференция, CG 2006, Турин, Италия, 29–31 мая 2006 г. Пересмотренные статьи . Х. Яап ван ден Херик, Паоло Чианкарини, HHLM Донкерс (ред.). Спрингер. стр. 72–83. CiteSeerX 10.1.1.81.6817 . ISBN  978-3-540-75537-1.
16. Кочиш, Левенте; Сепешвари, Чаба (2006). «Бандитское планирование Монте-Карло». В Фюрнкранце, Йоханнес; Шеффер, Тобиас; Спилиопулу, Майра (ред.). Машинное обучение: ECML 2006, 17-я Европейская конференция по машинному обучению, Берлин, Германия, 18–22 сентября 2006 г., Труды . Конспекты лекций по информатике. Том. 4212. Спрингер. стр. 282–293. CiteSeerX 10.1.1.102.1296 . дои : 10.1007/11871842_29. ISBN  3-540-45375-Х.
17. Сильвен Гелли; Ицзао Ван; Реми Мунос; Оливье Тейто (ноябрь 2006 г.). Модификация UCT с помощью шаблонов в Monte-Carlo Go (PDF) . Технический отчет, ИНРИА.
18. Чанг-Шинг Ли; Мэй-Хуэй Ван; Гийом Шасло; Жан-Батист Хук; Арпад Риммель; Оливье Тейто; Шан-Ронг Цай; Шун-Чин Сюй; Цунг-Пей Хонг (2009). «Вычислительный интеллект MoGo, показанный на тайваньских турнирах по компьютерному го» (PDF) . Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 1 (1): 73–89. CiteSeerX 10.1.1.470.6018 . дои : 10.1109/tciaig.2009.2018703. S2CID  15266518. 
19. Маркус Энценбергер; Мартин Мюллер (2008). Fuego — платформа с открытым исходным кодом для настольных игр и движка Go, основанная на поиске по дереву Монте-Карло (PDF) . Технический отчет, Университет Альберты.
20. "Ставка на Шодан Го" . Проверено 2 мая 2012 г.
21. «Исследовательский блог: AlphaGo: освоение древней игры го с помощью машинного обучения» . Блог исследований Google . 27 января 2016 г.
22. «Google совершает прорыв в области искусственного интеллекта, победив чемпиона по го» . Новости BBC . 27 января 2016 г.
23. «Матч 1 — Матч Google DeepMind Challenge: Ли Седол против AlphaGo» . YouTube . 9 марта 2016 г.
24. "Google AlphaGo AI побеждает чемпиона Европы по го" . ЗДНет . 28 января 2016 г.
25. Бродерик Арнесон; Райан Хейворд; Филип Хендерсон (июнь 2009 г.). «MoHex выигрывает гексагональный турнир» (PDF) . Журнал ICGA . 32 (2): 114–116. doi : 10.3233/ICG-2009-32218.
26. Тимо Эвальдс (2011). Игра и решение Гаванны (PDF) . Магистерская диссертация, Университет Альберты.
27. Ричард Дж. Лоренц (2008). «Амазонки открывают Монте-Карло». Компьютеры и игры, 6-я Международная конференция CG 2008, Пекин, Китай, 29 сентября – 1 октября 2008 г. Труды . Х. Яап ван ден Херик, Синьхэ Сюй, Цзунмин Ма, Марк Х.М. Винандс (ред.). Спрингер. стр. 13–24. ISBN 978-3-540-87607-6.
28. Томаш Козелек (2009). Методы MCTS и игра Аримаа (PDF) . Магистерская диссертация, Карлов университет в Праге.
29. Сяокун Ган; Юн Бао; Чжанган Хан (декабрь 2011 г.). «Метод поиска в реальном времени в недетерминированной игре - г-жа Пак-Ман». Журнал ICGA . 34 (4): 209–222. doi : 10.3233/ICG-2011-34404.
30. Том Пепелс; Марк Х.М. Винандс; Марк Ланкто (сентябрь 2014 г.). «Поиск по дереву Монте-Карло в реальном времени в Ms Pac-Man». Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 6 (3): 245–257. дои : 10.1109/tciaig.2013.2291577 .
31. Гора, Гвардд (2015). «Тактическое планирование и MCTS в реальном времени в Fable Legends». Архивировано из оригинала 8 июня 2019 г. Проверено 8 июня 2019 г. ... мы реализовали подход, основанный на моделировании, который включал моделирование игрового процесса и использование MCTS для поиска потенциального пространства плана. В целом это сработало хорошо,...
32. Майкл Буро; Джеффри Ричард Лонг; Тимоти Фуртак; Натан Р. Стертевант (2009). «Улучшение оценки состояния, вывода и поиска в карточных играх, основанных на трюках». IJCAI 2009, Материалы 21-й Международной совместной конференции по искусственному интеллекту, Пасадена, Калифорния, США, 11–17 июля 2009 г. Крейг Бутилье (ред.). стр. 1407–1413. CiteSeerX 10.1.1.150.3077 . 
33. Джонатан Рубин; Ян Уотсон (апрель 2011 г.). «Компьютерный покер: Обзор». Искусственный интеллект . 175 (5–6): 958–987. дои : 10.1016/j.artint.2010.12.005 .
34. CD Уорд; ПИ Коулинг (2009). «Поиск по Монте-Карло применительно к выбору карт в Magic: The Gathering» (PDF) . CIG'09 Материалы 5-й международной конференции по вычислительному интеллекту и играм . IEEE Пресс. Архивировано из оригинала (PDF) 28 мая 2016 г.
35. Иштван Сита; Гийом Шасло; Питер Спронк (2010). «Поиск деревьев в Монте-Карло у поселенцев Катана» (PDF) . В Яапе Ван Ден Херике; Питер Спронк (ред.). Достижения в компьютерных играх, 12-я Международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г. Пересмотренные статьи . Спрингер. стр. 21–32. ISBN 978-3-642-12992-6. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 30 ноября 2015 г.
36. GMJB Часло; МХМ Винандс; JWHM Уитервейк; Х.Дж. ван ден Херик; Б. Бузи (2008). «Прогрессивные стратегии поиска в дереве Монте-Карло» (PDF) . Новая математика и естественные вычисления . 4 (3): 343–359. дои : 10.1142/s1793005708001094.
37. Брэдберри, Джефф (07 сентября 2015 г.). «Введение в поиск по дереву Монте-Карло».
38. Перес, Юваль; Шрамм, Одед; Шеффилд, Скотт; Уилсон, Дэвид Б. (2006). «Гекс со случайным ходом и другие игры на выбор». arXiv : math/0508580 .
39. Ауэр, Питер; Чеза-Бьянки, Николо; Фишер, Пол (2002). «Анализ задачи многорукого бандита за конечное время». Машинное обучение . 47 (2/3): 235–256. дои : 10.1023/а:1013689704352 . S2CID  207609497.
40. Браун, Кэмерон Б.; Паули, Эдвард; Уайтхаус, Дэниел; Лукас, Саймон М.; Коулинг, Питер I; Рольфсхаген, Филипп; Тавенер, Стивен; Перес, Диего; Самофракис, Спиридон; Колтон, Саймон (2012). «Обзор методов поиска по дереву Монте-Карло». Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 4 (1): 1–43. doi : 10.1109/tciaig.2012.2186810. ISSN  1943-068X.
41. Альтёфер, Инго (2012). «Об играх по заполнению доски со случайным порядком хода и совершенством Монте-Карло». Достижения в области компьютерных игр . Конспекты лекций по информатике. Том. 7168. стр. 258–269. дои : 10.1007/978-3-642-31866-5_22. ISBN 978-3-642-31865-8.
42. Рамануджан, Рагурам; Сабхарвал, Ашиш; Селман, Барт (май 2010 г.). «О состязательных пространствах поиска и планировании на основе выборки». ICAPS '10: Материалы двадцатой Международной конференции по автоматизированному планированию и составлению графиков . Икапс'10: 242–245.
43. Рамануджан, Рагурам; Селман, Барт (март 2011 г.). «Компромиссы в состязательном планировании на основе выборки». ICAPS '11: Материалы Международной конференции по автоматизированному планированию и составлению графиков . 21 (1): 202–209. дои : 10.1609/icaps.v21i1.13472 . S2CID  45147586.
44. «Ли Седоль побеждает AlphaGo в мастерском возвращении - игра 4» . Иди, гуру игры. Архивировано из оригинала 16 ноября 2016 г. Проверено 4 июля 2017 г.
45. Свеховский, М.; Мандзюк, Дж., «Самоадаптация игровых стратегий в обычных играх» (2010), Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх , том: 6 (4), стр. 367-381, номер документа : 10.1109/TCIAIG. 2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
46. Дрейк, Питер (декабрь 2009 г.). «Политика последнего хорошего ответа для Monte-Carlo Go». Журнал ICGA . 32 (4): 221–227. doi : 10.3233/ICG-2009-32404.
47. Сет Пеллегрино; Питер Дрейк (2010). «Исследование влияния силы игры в Монте-Карло Го». Материалы Международной конференции по искусственному интеллекту 2010 г., ICAI 2010, 12–15 июля 2010 г., Лас-Вегас, Невада, США . Хамид Р. Арабния, Дэвид де ла Фуэнте, Елена Б. Козеренко, Хосе Анхель Оливас, Руи Чанг, Питер М. ЛаМоника, Раймонд А. Люцци, Ашу М.Г. Соло (ред.). ЦСРЭА Пресс. стр. 1015–1018. ISBN 978-1-60132-148-0.
48. Гелли, Сильвен; Сильвер, Дэвид (2007). «Объединение онлайн- и офлайн-знаний в UCT» (PDF) . Машинное обучение, материалы двадцать четвертой международной конференции (ICML 2007), Корваллис, Орегон, США, 20–24 июня 2007 г. Зубин Гахрамани (ред.). АКМ. стр. 273–280. ISBN 978-1-59593-793-3. Архивировано из оригинала (PDF) 28 августа 2017 г.
49. Дэвид Сильвер (2009). Обучение с подкреплением и поиск на основе моделирования в Computer Go (PDF) . Докторская диссертация, Университет Альберты.
50. Реми Кулом . «CLOP: уверенная локальная оптимизация для настройки параметров черного ящика с шумом». ACG 2011: Advance in Computer Games 13 Conference, Тилбург, Нидерланды, 20–22 ноября .
51. Гийом MJ-B. Часло, Марк Х. М. Винандс, Яап ван ден Херик (2008). «Параллельный поиск в дереве Монте-Карло» (PDF) . Компьютеры и игры, 6-я Международная конференция CG 2008, Пекин, Китай, 29 сентября – 1 октября 2008 г. Труды . Х. Яап ван ден Херик, Синьхэ Сюй, Цзунмин Ма, Марк Х.М. Винандс (ред.). Спрингер. стр. 60–71. ISBN 978-3-540-87607-6.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
52. Маркус Энценбергер; Мартин Мюллер (2010). «Блокировочный многопоточный алгоритм поиска в дереве Монте-Карло». В Яапе Ван Ден Херике; Питер Спронк (ред.). Достижения в области компьютерных игр: 12-я Международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г., Пересмотренные статьи . Спрингер. стр. 14–20. CiteSeerX 10.1.1.161.1984 . ISBN  978-3-642-12992-6.

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

• Кэмерон Браун; Эдвард Паули; Дэниел Уайтхаус; Саймон Лукас; Питер I. Коулинг; Филипп Рольфсхаген; Стивен Тавенер; Диего Перес; Спиридон Самофракий; Саймон Колтон (март 2012 г.). «Обзор методов поиска по дереву Монте-Карло». Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 4 (1): 1–43. CiteSeerX  10.1.1.297.3086 . doi : 10.1109/tciaig.2012.2186810. S2CID  9316331.
• Мацей Свеховский; Конрад Годлевский; Бартош Савицкий; Яцек Мандзюк (июль 2022 г.). «Поиск в дереве Монте-Карло: обзор последних модификаций и приложений». Обзор искусственного интеллекта Springer Nature . 56 (3): 497–2562 (66 страниц). arXiv : 2103.04931 . doi : 10.1007/s10462-022-10228-y. S2CID  232147848.

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

• Руководство для начинающих по поиску в дереве Монте-Карло