Моделирование противников для обучения моделей на основе метода Монте-Карло для деревьев решений в настольной игре Citadels

1. Введение

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

Однако его применение сталкивается с существенными ограничениями в средах с несколькими игроками, скрытой информацией и временными ограничениями, где высокая вычислительная стоимость симуляций и сложность адаптации ставят под угрозу оперативность и качество решений (POWLEY et al., 2014).

В этом контексте гибридные подходы, интегрирующие MCTS и обучение с подкреплением (RL), показали свою перспективность, позволяя отделить фазу планирования от выполнения. Построение постоянных структур принятия решений с предварительным сохранением поиска обеспечивает мгновенный выбор действий во время игры, снижая потребность в онлайн-симуляциях и сохраняя стратегическую глубину (BROWNE, 2012; SWIECHOWSKI, 2023).

В этом исследовании была протестирована и разработана гибридная модель MCTS с методами обучения с подкреплением вне сети. Модель обучалась и тестировалась с использованием различных противников в среде симуляции настольной игры «Цитадели» (FAIDUTTI, 2016).

2. Общая цель

Общая цель этого исследования — разработать гибридную структуру MCTS-RL, способную эффективно работать в многопользовательских настольных играх со скрытой информацией, используя «Цитадели» в качестве примера.

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

3. Методология

Это исследование характеризуется как прикладное экспериментальное исследование с качественно-количественным анализом.

Первый этап включал разработку и адаптацию цифровой среды моделирования для настольной игры «Цитадели». Затем последовала разработка пяти экспертных агентов с настраиваемыми стратегиями, созданных для имитации реальных стратегий, используемых игроками-людьми, и разработка базового агента, который выбирает действия случайным образом. После валидации среды и разработанных агентов началась разработка гибридного фреймворка MCTS-RL.

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

Однако предложение хранить все дерево и сохранять его для будущих решений неосуществимо из-за огромного коэффициента ветвления. Чтобы сделать это возможным, необходимо абстрагировать дерево: состояние игры делится на фундаментальные характеристики (например, золото игрока, количество карт в руке), и каждая характеристика сопоставляется с независимой таблицей данных.

В этой структуре строки таблицы представляют возможные значения характеристики состояния, а столбцы — возможные действия, которые может предпринять агент (например, получить золото, взять карты). В каждой ячейке хранятся два значения: количество побед (n), достигнутых после выполнения этого действия в данном состоянии, и общее количество раз, когда эта комбинация была исследована (m). Эти таблицы, заполняемые в ходе симуляций партий в «Цитадели», формируют обученную модель агента.

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

4. Результаты и обсуждение

Для оценки производительности предложенной модели MCTS было важно понять динамику сил между базовыми стратегиями (экспертные агенты и случайный агент). Для этого каждая из них была подвергнута раунду из 10 000 матчей против четырех одинаковых противников.

Тепловая карта, представленная на рисунке 1, иллюстрирует производительность каждой стратегии (ось Y) против различных противников (ось X). Стратегии обладают различными сильными и слабыми сторонами: эксперты 1, 2 и 3 оказываются компетентными в большинстве сценариев, в то время как эксперты 4 и 5 значительно менее эффективны. Как и ожидалось, полностью случайная стратегия показывает очень низкую производительность против любого минимально структурированного противника.

Рисунок 1: Сравнение стратегий.

Следующим шагом была оценка модели MCTS-RL. Было проведено несколько тренировочных сессий, каждая из которых была сосредоточена на одном из противников, в общей сложности 100 000 тренировочных матчей для каждой версии модели. Затем производительность каждой обученной модели измерялась против всех типов противников по той же предыдущей тестовой модели и против случайно выбранных разнообразных противников.

Тепловая карта, показанная на рисунке 2, представляет совокупный процент побед каждой модели. Наиболее значимым результатом была модель, обученная в разнообразной среде, которая показала стабильную производительность, превзойдя другие версии модели почти во всех тестовых сценариях. Это говорит о том, что воздействие разнообразия стратегий во время обучения было фундаментальным для развития более надежной и универсальной игровой способности.

Рисунок 2: Сравнение обученных моделей.

Модели, обученные против экспертов 4 и 5, считавшихся самыми слабыми противниками, стали удивительно эффективными агентами. И наоборот, обучение против экспертов 1 и 3, считавшихся сильными противниками, привело к созданию моделей с очень низкой общей производительностью.

Возможное объяснение этого контраста заключается в том, что продвинутые стратегии экспертов, как правило, являются узкоспециализированными, тогда как модель MCTS-RL в начале обучения ведет себя почти случайно. Против сильных противников даже потенциально выгодные действия могут не привести к достаточному количеству побед, чтобы модель распознала закономерности успеха; тогда как против менее специализированных противников победы происходят чаще, что способствует обучению. Тем не менее, это остается гипотезой, требующей подтверждения.

5. Заключение

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

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

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