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

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

Класс	Алгоритм поиска

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

MCTS был объединен с нейронными сетями в 2016 году для компьютерного Go . Он использовался в других настольных играх, таких как шахматы и сёги , играх с неполной информацией, таких как бридж и покер , а также в пошаговых стратегических видеоиграх (таких как реализация Total War: Rome II в кампании высокого уровня. AI). MCTS также использовался в беспилотных автомобилях, например, в программном обеспечении Tesla Autopilot.

История

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

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

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

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

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

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

В 2006 году, вдохновленный этими предшественниками, Реми Кулом описал применение метода Монте-Карло к поиску по дереву игр и придумал название «Поиск по дереву Монте-Карло», L. Kocsis and Cs. Сепешвари разработал алгоритм UCT (верхние границы достоверности, применяемые к деревьям), а S. Gelly et al. реализовали UCT в своей программе MoGo. В 2008 году MoGo достиг уровня дан (мастер) в 9x9 Go, а программа Fuego начала побеждать сильных игроков-любителей в 9x9 Go.

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

Алгоритм MCTS также использовался в программах, играющих в другие настольные игры (например, Hex , Havannah , Game of the Amazons и Arimaa ), видеоиграх в реальном времени (например, Ms. Pac-Man и Fable Legends ) и недетерминированных играх. (например, скат , покер , Magic: The Gathering или Settlers of Catan ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Улучшения

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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

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

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

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