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

1. Введение

Поиск в дереве Монте-Карло (MCTS) — это семейство алгоритмов поиска, которое строит дерево решений в четырёх этапах: выбор, расширение, симуляция и обратное распространение. Вместо того чтобы требовать полной функции оценки для каждого состояния, метод оценивает качество действий на основе многочисленных симуляций, балансируя исследование редко посещаемых альтернатив с эксплуатацией известных действий. Эта характеристика способствовала выдающимся результатам в таких играх, как Go, шахматы и шоги, особенно в двухигровых средах с полной информацией (BROWNE et al., 2012).

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

2. Цели

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

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

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

Был проведён обзор литературы по исследованиям, опубликованным в период с 2013 по 2025 год, с поисками в базах данных IEEE Xplore, HAL Science Ouverte и Google Scholar. Стратегии поиска сочетали термины «Monte Carlo Tree Search» и «MCTS» с выражениями, относящимися к цифровым играм, настольным играм и многопользовательским играм. При отборе учитывались работы, в заголовке или аннотации которых упоминался MCTS, его прямой вариант или гибридный метод, применённый к конкурентным или кооперативным играм. Исследования, выходящие за рамки темы, документы без доступа к полному тексту и работы, чья сфера не соответствовала целям обзора, были исключены.

Поиск привёл к 24 записям, из которых две были дублированы между запросами, в итоге получено 22 уникальных потенциально релевантных работы (17 на английском и пять на французском). После отсева 18 исследований были выбраны для полного анализа, а четыре были исключены. Финальный корпус включал 13 исследований из IEEE Xplore, три из HAL и два найденных через Google Scholar, и среди выбранных 15 текстов были на английском, а три — на французском. Работы классифицировались по типу игры, использованному алгоритму, ограничениям среды, заявленным результатам и стратегиям смягчения. Тематический анализ был организован в три структурные категории: ограничения, пределы производительности, тактические слепые зоны и компромиссы в моделировании противника, а также два доменно-зависимых усилителя: несовершенная информация и решения в реальном времени.

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

Анализируемые исследования показывают, что MCTS проявляет наибольшую стабильность в играх с хорошо определёнными состояниями, умеренным фактором ветвления и вычислительным бюджетом, достаточным для большого количества симуляций. Среди 18 выбранных работ восемь касались цифровых игр, шесть исследовали настольные или настольные игры, а остальные анализировали карточные игры, среды общего игрового взаимодействия или связанные приложения. Алгоритмы на основе MCTS использовались в 14 исследованиях, часто в сочетании с нейронными сетями, абстракциями пространства действий, политиками симуляции и техниками настройки параметров.

Первая выявленная ограниченность касается производительности поиска. Хотя увеличение количества симуляций обычно улучшает качество решений, маргинальные выгоды стремятся уменьшаться, поскольку новые симуляции начинают повторно исследовать траектории, которые уже достаточно изучены. Результаты, полученные в игре Go, в играх в реальном времени и настольных играх, показывают, что удвоение вычислительного бюджета может привести к снижению или отсутствию преимуществ после определённого момента. Кроме того, исследования глубины навыков показывают, что этот предел зависит как от сложности игры, так и от конфигурации агента. Стратегии смягчения включают абстракцию пространства действий, упрощение симуляций и автоматическую настройку политик, констант исследования и стратегий развертывания через алгоритм эволюции N‑Tuple Bandit (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

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

Третье ограничение связано с моделированием противника. В играх с тремя и более участниками процесс поиска должен представлять не только решения игрока, находящегося в корне дерева, но и возможные ответы каждого противника. Модели, которые сохраняют независимые структуры для каждого противника, обычно лучше представляют стратегическое поведение, хотя они значительно увеличивают вычислительные затраты. В отличие от них, упрощенные подходы, такие как Paranoid Search и обобщенные политики, снижают эти затраты, но могут не представлять релевантные поведения. Литература предполагает, что подходы, основанные на селективном фокусе, обобщении ответов противников и разложении дерева, являются перспективными альтернативами, хотя они до сих пор мало оценены в играх с большим числом участников (BAIER; KAISERS, 2020).

Неполная информация усиливает эти ограничения. В карточных играх, таких как Pokémon и других средах с скрытыми состояниями, детерминизация, которая состоит в предположении одной возможной конфигурации неизвестной информации и поиске, как будто она истинна, может привести к слиянию несовместимых стратегий. Information Set MCTS, разновидность поиска по дереву Монте-Карло, разработанная для работы с неопределенностью, снижает эту проблему, группируя состояния, которые игрок не может различить, сохраняя только информацию, действительно доступную в момент принятия решения (COWLING; POWLEY; WHITEHOUSE, 2012). Тем не менее, случайность, присущая среде, и необходимость выводить поведение противников продолжают ограничивать надёжность получаемых оценок.

В реальных временных средах, таких как стратегии, MOBA и шутеры от первого лица, временные ограничения становятся критическим фактором. MCTS должен выбирать действия в очень коротких интервалах, одновременно управляя комбинаторными пространствами действий, несколькими юнитами и частичными наблюдениями. В этом контексте иерархические абстракции, макро-акции, отбрасывание действий и политики, полученные с помощью обучения с учителем или обучения с подкреплением, появляются как повторяющиеся стратегии (ONTAÑÓN, 2013). В некоторых ситуациях альтернативные методы могут работать лучше. Алгоритм Rolling Horizon Evolutionary Algorithm (RHEA), например, развивает короткие последовательности действий и выполняет непрерывное перепланирование, что особенно подходит для кооперативных игр и высоко стохастических сред, в которых дерево поиска быстро меняется (SFIKAS; LIAPIS, 2022).

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

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

Обзор также выявил пять актуальных возможностей для будущих исследований: (i) принятие и стандартизация общих бенчмарков для многопользовательских игр с несовершенной информацией; (ii) систематическая оценка техник моделирования противника в играх с большим числом участников; (iii) исследование взаимосвязи между сложностью, воспринимаемой игроками, и эффективной глубиной поиска; (iv) изучение серий «лучший из трех» и «лучший из пяти» с учётом истории выборов и банов; и (v) расширение применения MCTS в автоматическом балансировании, тестировании игр и процедурной генерации контента.