Поиск в дереве Монте-Карло - Monte Carlo tree search

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

Учебный класс	Алгоритм поиска

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

MCTS был введен в 2006 году для компьютер Go.^[1] Он использовался в других настольных играх, таких как шахматы и сёги,^[2] игры с неполной информацией, например мост^[3] и покер,^[4] а также в видеоиграх с пошаговыми стратегиями (например, Total War: Rome II реализация в кампании высокого уровня AI^[5]).

История

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

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

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

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

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

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

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

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

Алгоритм MCTS также использовался в программах, играющих другие настольные игры (Например Hex,^[25] Гаванна,^[26] Игра амазонок,^[27] и Аримаа^[28]), видеоигры в реальном времени (например, Г-жа Пак-Ман^[29][30] и Сказочные легенды^[31]) и недетерминированные игры (например, скат,^[32] покер,^[4] Магия: Сбор,^[33] или же Поселенцы Катана^[34]).

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

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

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

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

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

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

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

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

Поиск игр в чистом Монте-Карло

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

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

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

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

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

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

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

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

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

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

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

Недостатком является то, что в критической позиции против опытного игрока может быть одна ветвь, которая приводит к проигрышу. Поскольку это нелегко найти наугад, поиск может не «увидеть» это и не будет принимать во внимание. Считается, что это могло быть частью причины Поражение AlphaGo в четвертой игре против Ли Седола. По сути, поиск пытается отсечь менее релевантные последовательности. В некоторых случаях игра может привести к очень специфической линии игры, которая имеет большое значение, но которую упускают из виду, когда дерево обрезается, и поэтому этот результат "вне поля зрения поиска".^[41]

Улучшения

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

Для поиска по дереву Монте-Карло можно использовать либо свет или же тяжелый воспроизведения. Легкие игры состоят из случайных ходов, в то время как тяжелые игры используют различные эвристики, чтобы повлиять на выбор ходов.^[42] Эта эвристика может использовать результаты предыдущих воспроизведений (например, эвристика Last Good Reply^[43]) или экспертное знание данной игры. Например, во многих программах игры в го определенные каменные узоры в части доски влияют на вероятность перехода в эту область.^[17] Парадоксально, но неоптимальная игра в симуляциях иногда делает программу поиска по дереву Монте-Карло более эффективной в целом.^[44]

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

Знания о предметной области могут быть использованы при построении дерева игры, чтобы помочь в использовании некоторых вариантов. Один из таких методов присваивает ненулевое значение приоры к количеству выигранных и сыгранных имитаций при создании каждого дочернего узла, что приводит к искусственно завышенному или пониженному среднему проценту выигрышей, из-за чего узел выбирается более или менее часто на этапе выбора соответственно.^[45] Связанный метод, называемый прогрессивный уклон, заключается в добавлении к формуле UCB1 a ${\displaystyle {\frac {b_{i}}{n_{i}}}}$ элемент, где б_я это эвристическая оценка я-й ход.^[35]

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

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

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

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

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

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

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

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

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

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

1. Сильвер, Дэвид; Хуанг, Аджа; Мэддисон, Крис Дж .; Гез, Артур; Сифре, Лоран; Дрише, Джордж ван ден; Шриттвизер, Джулиан; Антоноглоу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нхам, Джон; Кальхбреннер, Нал; Суцкевер Илья; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грэпель, Тор; Хассабис, Демис (28 января 2016 г.). «Освоение игры го с глубокими нейронными сетями и поиском по дереву». Природа. 529 (7587): 484–489. Bibcode:2016Натура.529..484S. Дои:10.1038 / природа16961. ISSN  0028-0836. PMID  26819042. S2CID  515925.
2. Серебро, Дэвид (2017). «Освоение шахмат и сёги путем самостоятельной игры с использованием общего алгоритма обучения с подкреплением». arXiv:1712.01815v1 [cs.AI ].
3. Стюарт Дж. Рассел, Питер Норвиг (2009). Искусственный интеллект: современный подход (3-е изд.). Prentice Hall.
4. Джонатан Рубин; Ян Уотсон (апрель 2011 г.). «Компьютерный покер: обзор» (PDF). Искусственный интеллект. 175 (5–6): 958–987. Дои:10.1016 / j.artint.2010.12.005. Архивировано из оригинал (PDF) на 13.08.2012.
5. "Поиск дерева Монте-Карло в TOTAL WAR: ИИ кампании ROME II". AI Game Dev. Архивировано из оригинал 13 марта 2017 г.. Получено 25 февраля 2017.
6. Абрамсон, Брюс (1987). Модель ожидаемого результата игр для двух игроков (PDF). Технический отчет, Департамент компьютерных наук, Колумбийский университет. Получено 23 декабря 2013.
7. Вольфганг Эртель; Иоганн Шуман; Кристиан Саттнер (1989). «Обучение эвристике для средства доказательства теорем с использованием обратного распространения».. У Дж. Ретти; К. Лейдлмайр (ред.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208, стр. 87-95. Springer.
8. Кристиан Саттнер; Вольфганг Эртель (1990). «Автоматическое получение поисковой эвристики».. CADE90, 10-й межд. Конф. on Automated Deduction.стр. 470-484. LNAI 449. Springer.
9. Кристиан Суттнер; Вольфганг Эртель (1991). «Использование сетей обратного распространения для поиска средства доказательства теорем». Журнал исследований и приложений нейронных сетей. 2 (1): 3–16.
10. Брюгманн, Бернд (1993). Монте-Карло Го (PDF). Технический отчет, физический факультет, Сиракузский университет.
11. Чанг, Хён Су; Фу, Майкл С .; Ху, Цзяцяо; Маркус, Стивен И. (2005). «Адаптивный алгоритм выборки для решения марковских процессов принятия решений» (PDF). Исследование операций. 53: 126–139. Дои:10.1287 / opre.1040.0145. HDL:1903/6264.
12. Хён Су Чанг; Майкл Фу; Цзяцяо Ху; Стивен И. Маркус (2016). "Alphago Google DeepMind: неожиданная роль О.Р. в новаторском достижении". ИЛИ / MS сегодня. 45 (5): 24–29.
13. «Библиотека сенсея: KGSBotRatings». Получено 2012-05-03.
14. Реми Кулом (2008). "Революция Монте-Карло в го" (PDF). Японско-французский симпозиум "Границы науки".
15. Реми Кулом (2007). «Операторы эффективной селективности и резервного копирования в поиске по дереву Монте-Карло». Компьютеры и игры, 5-я Международная конференция, CG 2006, Турин, Италия, 29–31 мая 2006 г. Исправленные статьи. Х. Яап ван ден Херик, Паоло Чанкарини, Х. Х. Л. М. Донкерс (ред.). Springer. С. 72–83. CiteSeerX  10.1.1.81.6817. ISBN  978-3-540-75537-1.
16. Кочиш, Левенте; Сепешвари, Чаба (2006). «Планирование Монте-Карло на основе бандитов». В Фюрнкранце, Йоханнес; Схеффер, Тобиас; Spiliopoulou, Myra (ред.). Машинное обучение: ECML 2006, 17-я Европейская конференция по машинному обучению, Берлин, Германия, 18–22 сентября 2006 г., Труды. Конспект лекций по информатике. 4212. Springer. С. 282–293. CiteSeerX  10.1.1.102.1296. Дои:10.1007/11871842_29. ISBN  3-540-45375-X.
17. Сильвен Гелли; Изао Ван; Реми Муньос; Оливье Тейто (ноябрь 2006 г.). Модификация UCT с паттернами в Монте-Карло Go (PDF). Технический отчет, INRIA.
18. Чанг-Шинг Ли; Мэй-Хуэй Ван; Гийом Шасло; Жан-Батист Хук; Арпад Риммель; Оливье Тейто; Шан-Ронг Цай; Шун-Чин Сюй; Цунг-Пей Хун (2009). «Вычислительный интеллект MoGo выявлен в тайваньских компьютерных турнирах по го» (PDF). IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх. 1 (1): 73–89. CiteSeerX  10.1.1.470.6018. Дои:10.1109 / tciaig.2009.2018703. S2CID  15266518.
19. Маркус Энценбергер; Мартин Муллер (2008). Fuego - фреймворк с открытым исходным кодом для настольных игр и движка Go на основе поиска по дереву Монте-Карло (PDF). Технический отчет, Университет Альберты.
20. "Ставка на Шодан". Получено 2012-05-02.
21. «Блог исследований: AlphaGo: освоение древней игры го с помощью машинного обучения». Блог Google Research. 27 января 2016 г.
22. «Google совершил« прорыв »в области ИИ, победив чемпиона по го». Новости BBC. 27 января 2016 г.
23. «Матч 1 - Матч Google DeepMind Challenge: Ли Седол против AlphaGo». YouTube. 9 марта 2016.
24. "Google AlphaGo AI чисто зачищает чемпион Европы по го". ZDNet. 28 января 2016 г.
25. Бродерик Арнесон; Райан Хейворд; Филип Хендерсон (июнь 2009 г.). «MoHex выигрывает турнир по игре Hex» (PDF). Журнал ICGA. 32 (2): 114–116. Дои:10.3233 / ICG-2009-32218.
26. Тимо Эвальдс (2011). Играть и разгадывать Хаванна (PDF). Магистерская диссертация, Университет Альберты.
27. Ричард Дж. Лоренц (2008). «Амазонки открывают Монте-Карло». Компьютеры и игры, 6-я международная конференция, CG 2008, Пекин, Китай, 29 сентября - 1 октября 2008 г. Материалы. Х. Яап ван ден Херик, Синьхэ Сюй, Цзунмин Ма, Марк Х. М. Винандс (ред.). Springer. С. 13–24. ISBN  978-3-540-87607-6.
28. Томаш Козелек (2009). Методы MCTS и игры Arimaa (PDF). Магистерская работа, Карлов университет в Праге.
29. Сяоцун Ган; Юнь Бао; Чжананг Хан (декабрь 2011 г.). «Метод поиска в режиме реального времени в недетерминированной игре - мисс Пак-Ман». Журнал ICGA. 34 (4): 209–222. Дои:10.3233 / ICG-2011-34404.
30. Том Пепельс; Марк Х. М. Винандс; Марк Ланкто (сентябрь 2014 г.). «Поиск дерева Монте-Карло в реальном времени в Ms Pac-Man». IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх. 6 (3): 245–257. Дои:10.1109 / tciaig.2013.2291577.
31. Гора, Гваредд (2015). «Тактическое планирование и MCTS в реальном времени в Fable Legends». Получено 2019-06-08. .. Мы реализовали подход, основанный на моделировании, который включал моделирование игрового процесса и использование MCTS для поиска потенциального пространства плана. В целом это сработало, ...
32. Майкл Буро; Джеффри Ричард Лонг; Тимоти Фуртак; Натан Р. Стертевант (2009). «Улучшение оценки состояния, вывода и поиска в карточных играх с трюками». IJCAI 2009, Труды 21-й Международной совместной конференции по искусственному интеллекту, Пасадена, Калифорния, США, 11–17 июля 2009 г.. Крейг Бутилье (ред.). С. 1407–1413. CiteSeerX  10.1.1.150.3077.
33. CD. Сторожить; ЧИСЛО ПИ. Капюшон (2009). «Применение поиска по методу Монте-Карло для выбора карт в Magic: The Gathering» (PDF). CIG'09 Труды 5-й международной конференции по вычислительному интеллекту и играм. IEEE Press. Архивировано из оригинал (PDF) на 2016-05-28.
34. Иштван Сита; Гийом Шасло; Питер Спронк (2010). "Монте-Карло поиск деревьев в поселенцах Катана" (PDF). В Яапе Ван Ден Херике; Питер Спронк (ред.). Достижения в компьютерных играх, 12-я международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г. Пересмотренные документы. Springer. С. 21–32. ISBN  978-3-642-12992-6.
35. G.M.J.B. Часло; М.Х.М. Winands; J.W.H.M. Uiterwijk; Х. Дж. Ван ден Херик; Б. Бузи (2008). "Прогрессивные стратегии поиска по дереву Монте-Карло" (PDF). Новая математика и естественные вычисления. 4 (3): 343–359. Дои:10.1142 / с1793005708001094.
36. Брэдберри, Джефф (07.09.2015). "Введение в поиск по дереву Монте-Карло".
37. Перес, Юваль; Шрамм, Одед; Шеффилд, Скотт; Уилсон, Дэвид Б. (2006). «Хекс со случайным ходом и другие игры с выбором». arXiv:математика / 0508580.
38. Ауэр, Питер; Чеза-Бьянки, Николо; Фишер, Пол (2002). "Конечный анализ проблемы многорукого бандита" (PDF). Машинное обучение. 47 (2/3): 235–256. Дои:10.1023 / а: 1013689704352. S2CID  207609497. Архивировано из оригинал (PDF) на 2014-05-12.
39. Бузи, Бруно. «Старомодный Computer Go против Monte-Carlo Go» (PDF). Симпозиум IEEE по вычислительному интеллекту и играм, 1–5 апреля 2007 г., Hilton Hawaiian Village, Гонолулу, Гавайи.
40. Альтхёфер, Инго (2012). «Настольные игры с произвольным порядком хода и совершенство Монте-Карло». Достижения в компьютерных играх. Конспект лекций по информатике. 7168. С. 258–269. Дои:10.1007/978-3-642-31866-5_22. ISBN  978-3-642-31865-8.
41. «Ли Седол побеждает AlphaGo в мастерском камбэке - Игра 4». Go Game Guru. Архивировано из оригинал на 2016-11-16. Получено 2017-07-04.
42. Wiechowski, M .; Мандзюк, Дж., «Самоадаптация игровых стратегий в общей игре» (2010), IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх, том: 6 (4), стр. 367-381, DOI: 10.1109 / TCIAIG.2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
43. Дрейк, Питер (декабрь 2009 г.). «Политика последнего хорошего ответа для Monte-Carlo Go». Журнал ICGA. 32 (4): 221–227. Дои:10.3233 / ICG-2009-32404.
44. Сет Пеллегрино; Питер Дрейк (2010). «Исследование влияния силы воспроизведения в Монте-Карло го». Материалы Международной конференции по искусственному интеллекту 2010 г., ICAI 2010, 12–15 июля 2010 г., Лас-Вегас, Невада, США. Хамид Р. Арабния, Давид де ла Фуэнте, Елена Б. Козеренко, Хосе Анхель Оливас, Руи Чанг, Питер М. Ламоника, Раймонд А. Льюцци, Ашу М. Г. Соло (ред.). CSREA Press. С. 1015–1018. ISBN  978-1-60132-148-0.
45. Сильвен Гелли; Дэвид Сильвер (2007). «Объединение онлайн- и офлайн-знаний в UCT» (PDF). Машинное обучение, Материалы двадцать четвертой международной конференции (ICML 2007), Корваллис, Орегон, США, 20–24 июня 2007 г.. Зубин Гахрамани (ред.). ACM. С. 273–280. ISBN  978-1-59593-793-3.
46. Дэвид Сильвер (2009). Обучение с подкреплением и поиск на основе моделирования в Computer Go (PDF). Кандидатская диссертация, Университет Альберты.
47. Реми Кулом. "CLOP: уверенная локальная оптимизация для настройки параметров черного ящика с шумом". ACG 2011: 13-я конференция «Достижения компьютерных игр», Тилбург, Нидерланды, 20–22 ноября.
48. Гийом М.Дж.-Б. Часло, Марк Х. Винандс, Яап ван ден Херик (2008). «Параллельный поиск по дереву Монте-Карло» (PDF). Компьютеры и игры, 6-я международная конференция, CG 2008, Пекин, Китай, 29 сентября - 1 октября 2008 г. Материалы. Х. Яап ван ден Херик, Синьхэ Сюй, Цзунмин Ма, Марк Х. М. Винандс (ред.). Springer. С. 60–71. ISBN  978-3-540-87607-6.
49. Маркус Энценбергер; Мартин Мюллер (2010). "Беспоточный многопоточный алгоритм поиска по дереву Монте-Карло". В Яапе Ван Ден Херике; Питер Спронк (ред.). Достижения в компьютерных играх: 12-я международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г., исправленные статьи. Springer. стр.14 –20. CiteSeerX  10.1.1.161.1984. ISBN  978-3-642-12992-6.

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

• Кэмерон Браун; Эдвард Паули; Дэниел Уайтхаус; Саймон Лукас; Петр I. Коулинг; Филипп Рольфсхаген; Стивен Тавенер; Диего Перес; Спиридон Самофракис; Саймон Колтон (март 2012 г.). "Обзор методов поиска по дереву Монте-Карло". IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх. 4 (1): 1–43. CiteSeerX  10.1.1.297.3086. Дои:10.1109 / tciaig.2012.2186810. S2CID  9316331.

внешняя ссылка

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