Не все возможные миры равны: адаптивный MCTS для игр со скрытой информацией

В играх с неполной информацией и случайностью классический Monte Carlo Tree Search спотыкается: дерево строится на догадках о скрытых картах противника. Стандартный приём — Ensemble Determinization MCTS — генерирует несколько «возможных миров» (determinizations) и запускает поиск в каждом. Проблема в том, что все эти миры обычно получают одинаковый вычислительный бюджет, хотя их информативность может отличаться на порядки.

Статья arXiv:2607.13007 предлагает два механизма, которые ломают это допущение.

Dynamic Number of Determinizations меняет количество активных деревьев на лету. Если текущий поиск стабилизируется — деревьев становится меньше; если результаты противоречивы — больше. Это простая идея: не фиксировать число гипотез заранее, а реагировать на то, что показывает поиск.

Dynamic Simulation Allocation распределяет симуляции неравномерно. Вместо того чтобы делить бюджет поровну между всеми determinization-деревьями, алгоритм использует решение «симуляция за симуляцией», чтобы направлять ресурсы в дерево с наибольшим потенциальным приростом знаний. По сути — multi-armed bandit поверх самих возможных миров.

Бенчмарки — три популярных настольные игры: Jaipur, Lost Cities и Splendor. Все три содержат скрытую информацию и случайность, что делает их хорошим стресс-тестом для determinization-подходов. Тестирование проводилось в двух режимах: по числу итераций и по времени — и в обоих случаях определённые конфигурации дали статистически значимый прирост силы алгоритма.

Что здесь важно для практика. Оба механизма — это не новая архитектура, а надстройка над существующим Ensemble MCTS. Это значит, что их можно внедрить в уже работающий код без переписывания ядра. Но статья не даёт универсального рецепта: «particular configurations» означает, что выигрыш зависит от подбора параметров, и перенос настроений между доменами не гарантирован.

Более широкая мысль выходит за пределы настольных игр. Любая система, которая перебирает гипотезы о скрытом состоянии — будь то планирование в условиях неопределённости, моделирование поведения агентов или робастный поиск в частично наблюдаемых средах, — сталкивается с тем же выбором: тратить ресурсы поровну или адаптивно. Эта работа показывает, что адаптивность окупается, но цена — дополнительная логика управления бюджетом и необходимость тюнинга под конкретный домен.

Источник: cs.AI updates on arXiv.org