![](https://habrastorage.org/files/6f6/095/ca2/6f6095ca2a5a4b69b97155a325f90351.jpg)
Метод Монте-Карло это алгоритм принятия решений, часто используемый в играх в качестве основы искусственного интеллекта. Сильное влияние он оказал на программы для игры в Го, хотя находит свое применение и в других играх, как настольных, так и обычных компьютерных (например Total War: Rome II). Так же, стоит отметить, что метод Монте-Карло используется в нашумевшей программе AlphaGo, победившей го-профессионала 9-го дана Ли Седоля в серии из 5 игр.
В данной статье хотелось бы рассказать про версию алгоритма Монте-Карло под названием Upper Confidence bound applied to Trees (UCT). Именно после публикации этого алгоритма в 2006-м году, программы для игры в Го сильно усилили свои позиции и достигли значительных успехов в игре против человека.
Основой алгоритма UCT является решение задачи многоруких бандитов. В частности используется алгоритм Upper-Confidence-Bound (UCB). Он уже был описан на хабре здесь, но я все же повторю основные моменты.
Задача звучит так: есть набор игровых автоматов, каждый со своей вероятностью выигрыша. Требуется определить автомат, который принесет больший выигрыш.
Алгоритм UCB:
1. Инициализация. Сыграть на каждой машине один раз
2. На каждой следующей итерации выбрать машину с максимальным значением величины
![](https://habrastorage.org/files/32b/14d/c7e/32b14dc7ef6646c4b21232219976ecc3.png)
![](https://habrastorage.org/files/1bb/25c/a6f/1bb25ca6fbbd491ea1ec25d5e0da5413.png)
![](https://habrastorage.org/files/cf2/916/daa/cf2916daae934164b5137aa5d59eeddd.png)
![](https://habrastorage.org/files/413/6fb/1c3/4136fb1c3f6c47ec91413cf8f9dc30fa.png)
На практике для поиска в дереве ходов настольных игр часто используется модификация формулы UCB.
Например, такая:
![](https://habrastorage.org/files/f99/904/a9a/f99904a9a1114879badf0992eb0d339b.png)
здесь
![](https://habrastorage.org/files/14a/a58/38d/14aa5838d2b9494882173e6da0a94796.png)
![](https://habrastorage.org/files/413/6fb/1c3/4136fb1c3f6c47ec91413cf8f9dc30fa.png)
![](https://habrastorage.org/files/cf2/916/daa/cf2916daae934164b5137aa5d59eeddd.png)
Как видно из названия, алгоритм UCT (Upper Confidence bound applied to Trees) использует подход UCB для поиска по дереву. Рассмотрим пошагово каждую фазу алгоритма:
![](https://habrastorage.org/files/845/732/8d8/8457328d86ed4c7290e5acb7584acec7.png)
Первая фаза, выбор. Каждую позицию мы рассматриваем как задачу многорукого бандита. Узлы на каждом этапе выбираются согласно алгоритму UCB. Эта фаза действует до тех пор, пока не будет найден узел в котором еще не все дочерние узлы имеют статистику побед. На рисунке первое значение в узле это количество побед, второе общее количество игр в этом узле.
![](https://habrastorage.org/files/fe1/040/ad2/fe1040ad20844976a1b0faa0f1585d22.png)
Вторая фаза, расширение. Когда алгоритм UCB больше не может быть применим, добавляется новый дочерний узел.
![](https://habrastorage.org/files/ee0/126/16d/ee012616dca84a56ab3d8e48bd911114.png)
Третья фаза, симуляция. Из созданного на предыдущем этапе узла запускается игра со случайными или, в случае использования эвристик, не совсем случайными ходами. Игра идет до конца партии. Здесь важна только информация о победителе, оценка позиции не имеет значения.
![](https://habrastorage.org/files/6c1/073/8ae/6c10738ae8b74c0f9cc3190d60a96ed9.png)
Четвертая фаза, обратное распространение. На этом этапе информация о сыгранной партии распространяется вверх по дереву, обновляя информацию в каждом из ранее пройденных узлов. Каждый из этих узлов увеличивает показатель количества игр, а узлы, совпадающие с победителем, увеличивают также и количество побед. В конце алгоритма выбирается узел, посещенный наибольшее количество раз.
UCT не всегда выбирает только самый лучший ход, но так же периодически исследует и менее успешные узлы. Второй параметр формулы медленно растет для тех узлов, которые посещаются не так часто. И в итоге на каком-то этапе алгоритм выберет именно такой ход в качестве предпочтительного. Если ход оправдал ожидания, в следующий раз он будет выбран с большей вероятностью.
По сравнению с другими алгоритмами для поиска оптимальных ходов, UCT обладает следующими преимуществами:
- UCT может быть безболезненно остановлен на любом этапе работы. И на момент остановки он просчитает равномерно все варианты ходов из корневого узла
Пример остановки алгоритма альфа-бета. Видно, что узлы со знаком «?» так и не были исследованы
- Дерево растет асимметрично, исследуя предпочтительные ходы глубже остальных. Таким образом, достигается большая эффективность в сравнении с другими алгоритмами в играх со значительным количеством вариантов для перебора.
Т.к. ходы, выбранные случайно в большинстве своем бессмысленны и не имеют какого-то общего направления, то для улучшения работы алгоритма используются различные эвристические методы, основанные на информации о конкретной игре. Один из таких методов это применение шаблонов.
Вот пример шаблона 3x3 для разрезания камней в Го:
![](https://habrastorage.org/files/78b/d27/556/78bd27556aae441c8faa1d8cc0ad049b.jpg)
Ход будет расценен как интересный, когда первый шаблон совпадает, а второй и третий нет. То есть белую группу можно «разрезать». Квадратиком изображена интересующая нас позиция.
Шаблоны могут использоваться как на этапе выбора хода в дереве, так и на этапе симуляции. Зачастую такие шаблоны ищутся где-то в окрестностях последнего сделанного хода. Это делается, потому, что текущий ход не редко является ответом на предыдущий и скорее всего, будет сделан где-то поблизости.
Пример из серии до и после. Слева игровая ситуация с использованием обычного UCT, справа UCT c применением шаблонов:
![](https://habrastorage.org/files/4e0/611/c7c/4e0611c7c8e24f8db79ecaf3c3d6a85c.jpg)
Видно, что на первом рисунке камни бессистемно расставлены по всей доске.
В большинстве случаев шаблоны пишутся вручную, но есть так же и примеры автоматической генерации.
Для того чтобы не распылятся на всю доску и не тратить время на просчет лишних вариантов. Можно выделить наиболее важную область, в которой уже и исследовать ходы. Очевидно, что если в данный момент вся борьба сосредоточена вокруг одной группы в определенном углу доски, то не имеет смысла рассматривать пустующие области вокруг. Алгоритмы определения таких областей выходят за рамки статьи, но те, кому интересно могут почитать подробно здесь: Common Fate Graph.
Алгоритм UCT может быть одновременно запущен в нескольких потоках. Вот некоторые способы параллелизации вычислений:
- Распараллеливание узлов, одновременная симуляция игр из одного и того же узла.
- Распараллеливание корня, построение независимых деревьев.
- Распараллеливание дерева, совместное построение одного дерева несколькими потоками.
Это наверное все, что хотелось бы сказать про алгоритм Монте-Карло и в частности UCT. В целом алгоритм с учетом дополнительных модификаций показывает неплохие результаты игры. В пользу этого утверждения говорит, то, что все современные Го-программы используют именно его. Надеюсь, что для кого-то из вас он тоже окажется полезен.
Комментарии (5)
SeptiM
26.04.2016 19:11Не пробовали к какой-нибудь пошаговой игрушке прикрутить?
galvanom
26.04.2016 22:13Если имеете в виду пошаговую игру типа Heroes of Might and Magic, то думаю, что не составит проблем использовать такой алгоритм в ней. Но я не пробовал =)
SeptiM
26.04.2016 22:32Я скорее про игрушки типа реверси, шашки, клоподавки и т.п. На самом деле может составить. У голых MCTS есть проблема с оценкой действий. Это дорого. Я пытался прикрутить их к войнам вирусов, и скажем так, они с большим трудом чуть-чуть отличались от рандома, при этом жрали секунды процессорного времени.
Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.galvanom
26.04.2016 22:53Вот ссылка на статью с описанием того как работает программа MoGo и собственно те эвристики, о которых вы интересуетесь. С нее в 2006-м и началось активное использование UCT в Го-программах. Про обучение там конечно ничего не сказано, но на эту тему есть наглядный пример — AlphaGo, информацию о том как эта программа устроена можно найти на хабре.
gena_glot
Почему вы не хотите сыграть на двух уровнях сразу? Или на трех. Вы же уже дерево «предварительное» имеете. Осталось сыграть. Вот и новый алгоритм-болгаритм.