Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Поиск в дереве Монте-Карло
Учебный классАлгоритм поиска
Алгоритмы поиска по графам и деревьям
Списки
похожие темы

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

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

История [ править ]

Метод Монте-Карло [ править ]

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

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

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

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

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

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

В январе 2012 года программа Дзен выиграла 3: 1 в матче по го на доске 19 × 19 с любителем 2 дан . [20] Google Deepmind разработал программу AlphaGo , которая в октябре 2015 года стала первой программой Computer Go, которая победила профессионального игрока в го без каких-либо затруднений на полноразмерной доске 19x19. [1] [21] [22] В марте 2016 года AlphaGo была удостоена почетного уровня 9 дан (мастер) в игре 19 × 19 Go за победу над Ли Седолом в матче из пяти игр с финальным счетом четыре игры к одному. [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] покер , [4] Magic: The Gathering , [33] или Settlers of Catan [34] ). .

Принцип работы [ править ]

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

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

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

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

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

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

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

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

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

Основная трудность при выборе дочерних узлов - это поддержание некоторого баланса между использованием глубоких вариантов после ходов с высоким средним процентом выигрышей и исследованием ходов с небольшим количеством симуляций. Первая формула для балансировки эксплуатации и исследования в играх, получившая название UCT ( верхняя граница уверенности 1, применяемая к деревьям ), была предложена Левенте Кочишем и Чаба Сепешвари . [16] UCT основан на формуле UCB1, полученной Auer, Cesa-Bianchi и Fischer [38], и доказуемо конвергентном алгоритме AMS (Adaptive Multi-stage Sampling), впервые примененном к многоэтапным моделям принятия решений (в частности,Марковские процессы принятия решений ) Чанг, Фу, Ху и Маркус. [11] Кочиш и Сепешвари рекомендуют выбирать в каждом узле игрового дерева ход, для которого выражение имеет наибольшее значение. В этой формуле:

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

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

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

Преимущества и недостатки [ править ]

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

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

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

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

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

Улучшения [ править ]

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ а б Сильвер, Дэвид ; Хуанг, Аджа ; Мэддисон, Крис Дж .; Гез, Артур; Сифре, Лоран; Дрише, Джордж ван ден; Шриттвизер, Джулиан; Антоноглоу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нхам, Джон; Кальхбреннер, Нал; Суцкевер Илья ; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грэпель, Тор; Хассабис, Демис (28 января 2016 г.). «Освоение игры го с глубокими нейронными сетями и поиском по дереву». Природа . 529 (7587): 484–489. Bibcode : 2016Natur.529..484S . DOI : 10,1038 / природа16961 . ISSN 0028-0836 . PMID  26819042 . S2CID  515925 .
  2. ^ a b Сильвер, Дэвид (2017). «Освоение шахмат и сёги путем самостоятельной игры с использованием общего алгоритма обучения с подкреплением». arXiv : 1712.01815v1 [ cs.AI ].
  3. ^ Стюарт Дж. Рассел , Питер Норвиг (2009). Искусственный интеллект: современный подход (3-е изд.). Прентис Холл .CS1 maint: uses authors parameter (link)
  4. ^ a b Джонатан Рубин; Ян Уотсон (апрель 2011 г.). «Компьютерный покер: обзор» (PDF) . Искусственный интеллект . 175 (5–6): 958–987. DOI : 10.1016 / j.artint.2010.12.005 . Архивировано из оригинального (PDF) 13 августа 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. ^ a b Брюгманн, Бернд (1993). Монте-Карло Го (PDF) . Технический отчет, физический факультет, Сиракузский университет.
  11. ^ a b c Чанг, Хён Су; Фу, Майкл С .; Ху, Цзяцяо; Маркус, Стивен И. (2005). «Адаптивный алгоритм выборки для решения марковских процессов принятия решений» (PDF) . Исследование операций . 53 : 126–139. DOI : 10.1287 / opre.1040.0145 . hdl : 1903/6264 .
  12. ^ а б Хён Су Чанг; Майкл Фу; Цзяцяо Ху; Стивен И. Маркус (2016). «Alphago Google DeepMind: неожиданная роль OR в новаторском достижении» . ИЛИ / MS Сегодня . 45 (5): 24–29.
  13. ^ «Библиотека сенсея: KGSBotRatings» . Проверено 3 мая 2012 .
  14. ^ Рой Coulom (2008). «Революция Монте-Карло в го» (PDF) . Японско-французский симпозиум "Границы науки" .
  15. ^ Рой Coulom (2007). «Операторы эффективной селективности и резервного копирования в поиске по дереву Монте-Карло». Компьютеры и игры, 5-я международная конференция, CG 2006, Турин, Италия, 29–31 мая 2006 г. Исправленные статьи . Х. Яап ван ден Херик, Паоло Чанкарини, HHLM Donkers (ред.). 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 . DOI : 10.1007 / 11871842_29 . ISBN  3-540-45375-X.
  17. ^ a b c Сильвен Гелли; Изао Ван; Реми Муньос; Оливье Тейто (ноябрь 2006 г.). Модификация UCT с паттернами в Монте-Карло Go (PDF) . Технический отчет, INRIA.
  18. ^ Чанг-Шинг Ли; Мэй-Хуэй Ван; Гийом Шасло; Жан-Батист Хук; Арпад Риммель; Оливье Тейто; Шан-Ронг Цай; Шун-Чин Сюй; Цунг-Пей Хун (2009). «Вычислительный интеллект MoGo, раскрытый в тайваньских компьютерных турнирах по го» (PDF) . IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх . 1 (1): 73–89. CiteSeerX 10.1.1.470.6018 . DOI : 10.1109 / tciaig.2009.2018703 . S2CID 15266518 .   
  19. ^ Маркус Энценбергер; Мартин Муллер (2008). Fuego - фреймворк с открытым исходным кодом для настольных игр и движка Go на основе поиска по дереву Монте-Карло (PDF) . Технический отчет, Университет Альберты.
  20. ^ "Ставка Shodan Go" . Проверено 2 мая 2012 .
  21. ^ «Исследовательский блог: AlphaGo: освоение древней игры го с машинным обучением» . Блог Google Research . 27 января 2016 г.
  22. ^ «Google достигает« прорыва »ИИ, победив чемпиона го» . BBC News . 27 января 2016 г.
  23. ^ «Матч 1 - Google DeepMind Challenge Match: Ли Седол против AlphaGo» . Youtube . 9 марта 2016.
  24. ^ "Google AlphaGo AI чисто зачищает чемпион Европы по го" . ZDNet . 28 января 2016 г.
  25. ^ Бродерик Арнесон; Райан Хейворд; Филип Хендерсон (июнь 2009 г.). «MoHex выигрывает турнир по игре Hex» (PDF) . Журнал ICGA . 32 (2): 114–116. DOI : 10.3233 / МКГ-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. DOI : 10.3233 / МКГ-2011-34404 .
  30. ^ Том Пепелс; Марк Х. М. Винандс; Марк Ланкто (сентябрь 2014 г.). «Поиск дерева Монте-Карло в реальном времени в Ms Pac-Man» . IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх . 6 (3): 245–257. DOI : 10.1109 / tciaig.2013.2291577 .
  31. ^ Mountain, Gwaredd (2015). «Тактическое планирование и MCTS в реальном времени в Fable Legends» . Проверено 8 июня 2019 . .. мы реализовали подход, основанный на моделировании, который включал моделирование игрового процесса и использование 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) 28 мая 2016 года.
  34. ^ Иштван Сита; Гийом Шасло; Питер Спронк (2010). «Поиск деревьев методом Монте-Карло в поселенцах Катана» (PDF) . В Яапе Ван Ден Херике; Питер Спронк (ред.). Достижения в компьютерных играх, 12-я Международная конференция, ACG 2009, Памплона, Испания, 11–13 мая 2009 г. Исправленные статьи . Springer. С. 21–32. ISBN  978-3-642-12992-6.
  35. ^ a b G.MJB Chaslot; MHM Winands; JWHM Uiterwijk; HJ ван ден Херик; Б. Бузи (2008). «Прогрессивные стратегии поиска по дереву Монте-Карло» (PDF) . Новая математика и естественные вычисления . 4 (3): 343–359. DOI : 10.1142 / s1793005708001094 .
  36. ^ Брэдберри, Джефф (07.09.2015). «Введение в поиск по дереву Монте-Карло» .
  37. ^ Перес, Юваль; Шрамм, Одед; Шеффилд, Скотт; Уилсон, Дэвид Б. (2006). «Хекс со случайным ходом и другие игры с выбором». arXiv : math / 0508580 .
  38. ^ Ауэр, Питер; Чеза-Бьянки, Николо; Фишер, Пол (2002). "Конечный анализ проблемы многорукого бандита" (PDF) . Машинное обучение . 47 (2/3): 235–256. DOI : 10.1023 / а: 1013689704352 . S2CID 207609497 . Архивировано из оригинального (PDF) 12 мая 2014 года.  
  39. ^ Bouzy, Бруно. «Старомодный Computer Go против Монте-Карло Go» (PDF) . Симпозиум IEEE по вычислительному интеллекту и играм, 1–5 апреля 2007 г., Hilton Hawaiian Village, Гонолулу, Гавайи .
  40. ^ Althöfer, Инго (2012). «Настольные игры с произвольным порядком хода и совершенство Монте-Карло». Достижения в компьютерных играх . Конспект лекций по информатике. 7168 . С. 258–269. DOI : 10.1007 / 978-3-642-31866-5_22 . ISBN 978-3-642-31865-8.
  41. ^ "Ли Седол побеждает AlphaGo в мастерском камбэке - Игра 4" . Go Game Guru. Архивировано из оригинала на 2016-11-16 . Проверено 4 июля 2017 .
  42. ^ Wiechowski, M .; Мандзюк, Дж., «Самоадаптация игровых стратегий в общих игровых процессах» (2010), Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх , том: 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. DOI : 10.3233 / МКГ-2009-32404 .
  44. ^ Сет Пеллегрино; Питер Дрейк (2010). «Исследование влияния силы воспроизведения в Монте-Карло го». Материалы Международной конференции по искусственному интеллекту 2010 г., ICAI 2010, 12–15 июля 2010 г., Лас-Вегас, Невада, США . Хамид Р. Арабния, Давид де ла Фуэнте, Елена Б. Козеренко, Хосе Анхель Оливас, Руи Чанг, Питер М. Ламоника, Раймонд А. Лиуцци, Ашу М.Г. Соло (ред.). CSREA Press. С. 1015–1018. ISBN 978-1-60132-148-0.
  45. ^ a b Сильвен Гелли; Дэвид Сильвер (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. ^ Гийом MJ-B. Часло, Марк Х. М. Винандс, Яап ван ден Херик (2008). «Параллельный поиск по дереву Монте-Карло» (PDF) . Компьютеры и игры, 6-я Международная конференция, CG 2008, Пекин, Китай, 29 сентября - 1 октября 2008 г. Материалы . Х. Яап ван ден Херик, Синьхэ Сюй, Цзунмин Ма, Марк Х.М. Винандс (ред.). Springer. С. 60–71. ISBN  978-3-540-87607-6.CS1 maint: multiple names: authors list (link)
  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 . DOI : 10.1109 / tciaig.2012.2186810 . S2CID  9316331 .

Внешние ссылки [ править ]

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