Можно ли научить ИИ играть в настольную игру и выигрывать в ней, если мы сами не знаем как это сделать? Да! И один из способов — использовать алгоритм Monte Carlo Tree Search (MCTS). Он актуален даже сейчас, в эпоху развития нейронных сетей.
У многих людей, в том числе и у меня, поначалу были сложности с пониманием алгоритма, как и с верой в то, что он может хорошо играть. В этой статье хочу рассказать об MCTS максимально просто и помочь разобраться в нем новичкам. В первой главе расскажу об основах, с которыми многие могут быть уже знакомы. Однако считаю, что они действительно важны для понимания. Подробности под катом!
Используйте навигацию, если не хотите читать текст полностью:
→ Выигрышные и беспроигрышные стратегии
→ MCTS
→ Применение
Выигрышные и беспроигрышные стратегии
Теория
Сид Мейер сказал: «Игра — это серия интересных решений».
В большинстве игр, не только настольных, есть «состояние игры»: расположение фигур на поле или монстров в подземелье, карты в руке, здоровье и инвентарь персонажей и т. д. Игроки своими действиями могут это состояние изменять, и цель каждого игрока — привести игру в такое состояние, где он объявляется победителем.
В рамках статьи мы рассмотрим только игры, где два игрока выполняют действия поочередно, и имеют полную информацию: шашки, шахматы, крестики-нолики и т.д.
Это не значит, что MCTS не годится для покера, преферанса или колонизаторов. Однако, в подобных сценариях есть своя специфика, на которую не следует отвлекаться на этапе изучения основ.
Итак, у нас есть возможные игровые состояния, в каждом из которых (кроме финального) есть доступные ходы, переводящие игру в другое состояние. Таким образом, игру можно описать с помощью следующего графа:
- начальное состояние. Например, пустое поле в го и крестиках-ноликах, начальная расстановка фигур в шашках и шахматах и т.д.;
- конечные состояния — те, в которых достигается условие окончания игры;
- промежуточные состояния, в которых, по сути, и проходит игра;
- доступные ходы — ребра, связывающие состояния.
Для примера, рассмотрим простой вариант игры Баше: есть 4 камня, игроки поочередно могут брать или один, или два из них, а если игрок не может сделать ход, потому что камни закончились, то он проиграл. Состояние игры здесь можно описать двумя параметрами: сколько камней осталось, и чей сейчас ход. Допустим, что мы ходим первыми.
Граф игры можно изобразить следующим образом:
- Белые узлы — состояния, в которых очередь хода за первым игроком (за нами);
- Серые узлы — состояния, в которых очередь хода за вторым игроком (оппонентом);
- Синий контур — начальное состояние;
- Зеленый контур — победное финальное состояние;
- Красный контур — проигрышное финальное состояние.
Нужно найти путь из начального состояния в победное.
Похоже на обычный поиск пути в графе, но есть нюанс — наличие оппонента, который хочет попасть совсем в другой пункт назначения. Не всегда мы можем выбрать направление хода. При этом мы предполагаем худший сценарий, в котором оппонент всегда делает наименее выгодные для нас ходы. На первый взгляд может показаться, что традиционные алгоритмы, например, поиск в глубину или в ширину, здесь неприменимы.
Давайте пройдемся по графу с конца.
Если наша очередь хода и в куче остался один камень, то есть единственный ход и он ведет к победе. Следовательно, такое состояние можно считать победным. Для оппонента ситуация симметрична: если в его ход остался один камень, то есть единственный ход, который ведет к его победе, следовательно, это проигрышное для нас состояние.[a]
Если в наш ход осталось два камня, то есть два варианта, один из которых ведет к победе, а другой — к поражению. Так как мы выберем благоприятный, то это состояние является победным. А если два камня осталось в ход оппонента, и мы считаем, что он придерживается оптимальной стратегии, то он выберет наименее желаемый для нас ход. Следовательно, это проигрышное состояние.
Если в ход оппонента осталось три камня, то у него есть два варианта, но оба ведут к нашей победе. Следовательно, это победное состояние.
В начале игры в куче четыре камня. Если взять два, то это приведет к поражению, а если один, то к победе. Тот случай, когда лучше не жадничать.
Таким образом, чтобы нивелировать наличие оппонента, нам нужно вести путь по тем игровым состояниям, где любой ход оппонента ведет к нашей победе.
Здесь и далее дочерними состояниями (или просто детьми) будем называть такие, в которые можно попасть, совершив ход из текущего, то есть те, куда ведут ребра.
Если обозначить победу как +1, поражение как -1, а ничью (в тех играх, где она есть) как 0, то ценность состояния равна максимуму (для нашего хода) или минимуму (для хода оппонента) ценности его дочерних состояний, поэтому такой алгоритм получил название минимакс.
Поиск в глубину или в ширину совместно с минимаксом позволяют определить ценность каждого игрового состояния и, как следствие, найти оптимальную стратегию…
Еще одно наблюдение: наше поведение симметрично поведению оппонента. Можно обозначать состояния не как победное или проигрышное для нас, а как победное или проигрышное для текущего игрока. В таком случае нам не нужна информация о том, чей сейчас ход, вследствие чего граф становится проще:
Зеленый контур — победное состояние для текущего игрока, красный — проигрышное.
На самом деле, игра Баше настолько проста, что граф строить не обязательно — есть формула выигрышной стратегии. Однако, в других играх не все так просто.
Теоретически, используя такой подход, можно просчитать граф для любой игры с полной информацией и найти, например, беспроигрышную (а может, и выигрышную) стратегию для шахмат.
На практике, если для классических крестиков-ноликов это еще вполне реально, то для шахмат размер графа такой, что современных вычислительных мощностей будет недостаточно.
Возможно, что в будущем написание алгоритма поиска оптимальной стратегии в шахматах станет типичной задачкой на собеседовании, но пока приходится довольствоваться эвристическими подходами.
Практика
Во-первых, граф обычно разворачивается в дерево. С одной стороны, в этом есть минусы: одно и то же состояние может присутствовать в нескольких экземплярах. При этом, у дерева есть более четкая иерархия «родитель — ребенок», так что ходить по дереву проще.
Во-вторых, рассчитывается не все дерево от начала до конца игры, а только от текущей ситуации на несколько ходов вперед.
Для каждого из листьев дерева (состояний, глубже которых мы не спускаемся) считаем некоторую оценку: насколько это состояние кажется нам выигрышным. Замечу, что эта оценка не является точным значением, гарантирующим победу или поражение, как в рассмотренном выше примере. Например, в шашках можно посчитать разницу между количеством шашек у нас и у оппонента, считая дамки за три шашки. Грубая, но оценка.
Дальше — действуем по аналогии с предыдущим примером: поднимаемся выше по дереву, считая максимум для своего хода и минимум для хода оппонента, пока не доберемся до корня, а затем выбираем ход, дающий наилучшую оценку.
Чем точнее и замысловатее будет оценочная функция, тем лучше будет играть наш ИИ. То есть, сам по себе алгоритм минимакса достаточно прост. Загвоздка именно в том, чтобы найти хорошую оценочную функцию.
А можно обойтись без нее? Можем ли мы сделать универсальную оценочную функцию, подходящую для любой игры? Это и предлагает алгоритм MCTS.
MCTS
Общая идея
Как мы можем догадаться, Monte Carlo в названии алгоритма отсылает нас к рулетке и намекает на то, что в нем используется рандом. Идея следующая: для оценки игрового состояния мы просто начинаем играть, совершая случайные (из списка разрешенных) ходы за обоих игроков, пока игра не закончится. На первый взгляд концепция выглядит странно, ведь мы хотели оптимальную стратегию для обоих игроков, а случайные ходы явно на это не похожи.
Объясню. Во-первых, оба игрока играют на равных (одинаково плохо), поэтому для того, чье состояние является выигрышным, шансы на победу выше. Во-вторых, мы прогоняем не одну симуляцию, а, скажем, несколько миллионов, после чего считаем процент побед.
В таком случае, оценка будет варьироваться от 0 (проигрышное состояние) до 1 (выигрышное состояние).
Также, мы можем начислять очки. Например, -1 за проигрыш, +1 за победу и 0 за ничью. Тогда формула будет выглядеть так:
Несколько миллионов сыгранных игр может прозвучать как нечто, требующее нескольких дней расчетов на кластере. Однако, самое затратное по времени — получить список доступных ходов. Само принятие решения максимально быстрое, так как необходимо выбрать случайный из них.
Далее — поменять состояние. Зачастую это можно сделать перезаписью в ту же память, где хранилось предыдущее состояние, тем самым минимизируя ее затраты. Ну а количество ходов в настольных играх обычно не велико.
Благодаря тому, что такая симуляция получается очень легковесной, несколько миллионов симуляций вполне возможно прогнать за секунды даже на домашнем ПК.
Рассуждаем дальше. Делая множество симуляций из определенного состояния, мы будем много раз проходить и по дочерним состояниям. Например, если у нас есть 10 доступных ходов и мы совершили миллион симуляций, то в среднем пробежались по каждому из дочерних состояний 100 000 раз. Почему бы не собрать статистику и не рассчитать оценку и для них тоже?
В свою очередь, имея оценку для дочерних состояний, вместо случайного выбора хода можно выбрать наиболее перспективное из них и чаще (а то и всегда) ходить через него. Далее можно повторить те же действия: собрать статистику на детей и вместо рандома выбирать наиболее перспективный ход.
Подытожим. У нас есть два способа выбора хода: случайный — быстрый и не требующий дополнительной памяти, но «глупый», и перспективный — медленный и требующий память для хранения статистики, но более «осмысленный». Нужен определенный баланс между ними.
Баланс достигается за счет того, что дерево строится динамически: новое состояние добавляется в дерево только в том случае, если мы считаем, что оно этого достойно. Определить достоинство просто: если мы дошли до него используя «осмысленный» отбор, то состояние можно считать достойным.
Алгоритм
Итого, мы движемся вниз по дереву, каждый раз отдавая предпочтение наиболее перспективному ходу. Разумеется, выбирая ход для оппонента, мы выбираем выигрышный для него. В конечном итоге мы достигнем листа — состояния, у которого пока нет детей.
Это может случиться по двум причинам: либо оно является финальным и это завершение игры, либо это состояние, до которого мы добрались впервые. Первый случай подробнее рассмотрим чуть позже. Если же это не финальное, но пока бездетное состояние, то нужно исправить это упущение. Создаем ему детей для каждого из разрешенных ходов:
Далее — выбираем одного из детей (можно случайным образом), из которого запускаем быструю рандомную симуляцию. Во время рандомной симуляции новые узлы уже не создаются: случайные состояния, по которым пройдём в результате симуляции, хранить не обязательно, важен только результат. Однако, нужно запомнить, из какого состояния мы начали — вернемся к нему на следующем шаге.
Когда достигнем конца игры, мы получим результат: выигрыш, проигрыш или ничью. Теперь вернемся к состоянию, с которого начинали симуляцию, и обновим статистику: добавляем одну сыгранную игру и начисляем +1, -1 или 0 очков, в зависимости от ее результата.
Далее — обновляем статистику для его родителя и движемся таким образом вверх по дереву, пока не достигнем корня. Разумеется, нужно помнить, что выигрыш для нас — это проигрыш для оппонента, и наоборот.
В результате этих операций дерево стало немного больше, а статистика правдоподобнее. Теперь мы можем пройтись по обновленному дереву еще раз, выполняя те же 4 операции:
- спуск по дереву (от корня до листа) с выбором наиболее перспективных ходов;
- добавление в дерево дочерних состояний;
- случайная симуляция из одного них;
- подъем по дереву и обновление статистики.
Повторять до бесконечности. Было доказано, что в этом случае MCTS сходится к минимаксу. Заметьте, что при этом нам не потребовалось придумывать специальную оценочную функцию.
Конечно, на практике количество итераций ограничено двумя факторами: временем, так как мы должны делать ходы не только в симуляциях, но и в игре, а также памятью, поскольку рано или поздно она закончится из-за увеличения дерева.
На этом этапе обращу внимание на интересный момент. Мы решили остановиться и выбрать ход. Интуиция подсказывает, что нужно выбрать ход с максимальной оценкой (как в том же минимаксе). Однако, выбирать стоит ход с наибольшим счетчиком посещений, так как он является самым проверенным, следовательно, его оценка наиболее точна. Другой ход может получить более высокую оценку, но так как по нему ходили реже, доверять ей не стоит.
И это все? Почти. Еще одна важная деталь — перспективный ход.
Exploitation vs Exploration
Как говорилось выше, на этапе отбора, когда мы бежим вниз по дереву, мы выбираем самый перспективный ход. И опять интуитивно кажется, что самый перспективный — это ход с наивысшей оценкой. Но не стоит забывать, что наши оценки все-таки являются случайными величинами.
Представьте, что вы в незнакомом городе ищите, где бы перекусить. Вы находите несколько ресторанчиков поблизости. У одного из них рейтинг составляет 4,5, а у другого — 4,6. Допустим, сегодня вы выбрали ресторан с рейтингом 4,6, где вам действительно понравилось и вы поставили 5 звезд. Но вдруг в ресторанчике с рейтингом 4,5 вам бы понравилось больше? Завтра вы сходите туда или остановитесь на уже проверенном варианте?
Так же и в настольной игре. Если оценка какого-то состояния -1, но по нему прошли всего один раз, то это не значит, что оно гарантированно проигрышное. Может быть, стоит дать еще один шанс?
Таким образом, мы можем рассчитать перспективность по следующей формуле:
С оценкой все понятно, но как вычислить Любопытство?
Это так называемая задача о многоруком бандите: в оригинале вместо ресторанчиков предлагалось выбирать игровые автоматы, некоторые из которых «жадные», а некоторые — «щедрые». Определить тип автомата можно только сыграв в него.
О своем выборе так или иначе мы рискуем пожалеть: здесь или упущенная возможность попробовать новое, или разочарование этим новым. Наша задача — минимизировать суммарное сожаление.
Можете подумать о том, как бы вы решали эту задачу. Обратимся за ее решением к формуле UCB1, которая была адаптирована для поиска в дереве под названием UCT:
То есть, любопытство зависит от того, как часто мы вставали перед выбором (проходили через родителя) и как часто делали выбор в пользу именно этого состояния.
Чем чаще мы выбираем какой-то ход, тем больше уверенности в правильности оценки, и тем ниже любопытство. Но если мы предпочитаем другие варианты, то любопытство растет и рано или поздно может перевесить.
Температура — некая константа. Теоретическое значение (в оригинальной формуле UCB1) составляет √2, но на практике можно поиграть и с другими, так как иногда это может повысить эффективность поиска.
Вывод и доказательство формулы вы можете найти в книге Introduction to Multi-Armed Bandits.
Game Over
Ранее упоминался особый случай: мы шли по дереву и добрались до финального состояния, но не в результате случайной симуляции. В эндшпиле это достаточно вероятное событие.
Что же делать? Дальше «монтекарлить» мы уже не сможем. Если не хочется усложнять себе жизнь, то можно считать это финалом симуляции (без фактической симуляции) и переходить к обновлению статистики.
Но есть и другой вариант. Мы нашли состояние, для которого фактически не нужно вычислять приблизительную оценку, ведь мы точно знаем его ценность (выигрыш, проигрыш или ничья). В этом случае, в дополнение к обновлению статистики, мы можем перекроить дерево, убрав из него заведомо ненужные узлы:
Если игрок своим ходом заканчивает игру и проигрывает, то ему не нужно его делать. Безжалостно удаляем его, чтобы больше сюда не возвращаться. Не забываем обновить статистику для состояний выше по дереву.
Если игрок сделал ход и выиграл, значит только этот ход ему и интересен, а все альтернативы можно не проверять. Победа для одного — это поражение для другого, поэтому оппонент вряд ли захочет, чтобы мы сюда попали. Следовательно, эту ветку можно дальше не рассматривать:
Если в результате любых из этих манипуляций у состояния удалили последний доступный ход, то оно тоже гарантированно проигрышное для нас, но выигрышное оппонента. В таком случае рекурсивно движемся вверх, применяя те же правила.
Таким образом, дерево может сокращаться при удалении из рассмотрения слишком оптимистичных или заведомо проигрышных ходов. Например, мы не будем лелеять надежду на возможность поставить «детский» мат.
С ничьей не так очевидно: с одной стороны удалять ход не стоит, так как альтернативы могут оказаться еще хуже, но и проверять его повторно нет смысла, ведь мы уже на 100% уверены в исходе. Делитесь в комментариях своими мыслями на этот счет.
Применение
Благодаря тому, что для использования MCTS достаточно реализовать только правила игры, он прекрасно подходит не только для классических игр, но и для совершенно новых настолок.
Например, можно автоматизировать плейтест для новой игры, чтобы проверить баланс. Или добавить ботов в онлайн-версии игры. К слову, опенсорсный движок boardgame.io «под капотом» использует MCTS, позволяя без особых усилий добавлять ботов даже в те игры, которые вы только что придумали.
Нужен ли MCTS сейчас, в эпоху нейросетей? Да, ведь они прекрасно дополняют друг друга. Самое простое применение — создание набора данных для обучения: можно собирать хорошо проверенные состояния и их оценки из дерева, чтобы обучать на них нейросеть.
А еще лучше они работают в тандеме. Например, в AlphaZero используется MCTS, но во время симуляции ходы выбираются не случайно, а нейросетью. При этом теряется легковесность симуляций, но хоть они не такие быстрые, зато гораздо более точные. Более подробно об этом можно прочитать в статье AlphaGo Zero совсем на пальцах.
Возможно, эти тексты тоже вас заинтересуют:
→ Китайские процессоры становятся все лучше: серверный чип 3C6000 от Loongson соревнуется с AMD Epyc на базе Zen 3
→ Новая барахолка под Валенсией: другая, но не хуже. Что можно найти на испанском блошином рынке в феврале
→ Безопасность и конфиденциальность: особенности защиты данных в сетях 6G
