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

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 (NTBEA) (GOODMAN; PEREZ‑LIEBANA; LUCAS, 2024).

Друге обмеження відповідає сліпим зонам тактичного міркування. Оскільки MCTS оцінює середнє значення вибіркових продовжень, алгоритм може зазнавати невдачі в позиціях, які вимагають розпізнавання конкретних тактичних послідовностей, довгострокових загроз або рідкісних конфігурацій. У Go такі ситуації, як драбини та семеай, ілюструють сценарії, в яких тактична структура, очевидна для досвідчених гравців, може не бути ідентифікована пошуком.

Третя обмеженість стосується моделювання супротивника. У іграх з трьома або більше учасниками процес пошуку повинен представляти не лише рішення гравця, що знаходиться в корені дерева, а й можливі відповіді кожного супротивника. Моделі, які зберігають незалежні структури для кожного опонента, зазвичай краще відображають стратегічну поведінку, хоча вони значно збільшують обчислювальні витрати. У протилежність цьому, спрощені підходи, такі як Параноїдний пошук і узагальнені політики, зменшують ці витрати, але можуть не відображати відповідні поведінки. Література вказує, що підходи, що базуються на селективному фокусі, узагальненні реакцій супротивників і розкладі дерев, є перспективними альтернативами, хоча вони досі мало оцінюються у іграх з великою кількістю учасників (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 в автоматичному балансуванні, плейтестуванні та процедурній генерації контенту.