With most information hidden, the game Stratego had stumped AI until now

Исследователи из CMU, MIT, NYU и Стэнфорда создали ИИ Ataraxos, который впервые победил лучшего человека в Stratego — Пима Нимейера, считающегося величайшим игроком в истории игры, со счётом 15:1 при четырёх ничьих. Для обучения потребовалось всего 16 GPU и несколько тысяч долларов, что резко контрастирует с масштабными ресурсами, ранее тратившимися на подобные задачи.

Stratego — игра с неполной информацией: каждый из 40 фигур имеет скрытый ранг, раскрывающийся только при столкновении. Цель — захватить флаг противника. В отличие от покера, где скрыто всего две карты (1326 комбинаций), в Stratego возможных расстановок более дециллиона, а партии могут длиться до 2000 ходов. Кроме того, ключевую роль играет блеф: слабые фигуры часто выдают себя за маршала, чтобы запугать соперника. Ранее даже DeepNash от DeepMind не справлялся с этим балансом между дезинформацией и предсказуемостью, но Ataraxos смог его освоить, доказав, что сложные игры с долгой скрытой динамикой теперь поддаются ИИ.

Комментарии (109)

Успех Ataraxos связан с эффективностью алгоритма в условиях неполной информации, а не с масштабом ресурсов. Он быстро учится предсказывать действия противника, а не перебирает варианты. Это контрастирует с предыдущими подходами и открывает путь к более экономичным решениям в подобных играх. Stratego требует психологической составляющей и блефа, но шаблоны поведения можно выявить. Существует множество вариантов правил, включая Electronic Stratego и Silent Defense, которые увеличивают неопределённость и могут быть целями для ИИ. ИИ не страдает от ограничений памяти, в отличие от людей, что даёт ему преимущество в отслеживании открытых фигур. Сравнение с DeepNash показывает, что рост мощности ИИ в Stratego произошёл за счёт улучшения алгоритмической эффективности, а не увеличения вычислительных ресурсов. Поддельная маркировка фишек (царапины) нарушает честность и демонстрирует, как люди манипулируют неполной информацией в реальной жизни. Стратегия размещения флага в углу за двумя бомбами, использованная Ataraxos, редка, но эффективна — указывает на неинтуитивные решения ИИ. Игры с неполной информацией, такие как Hanabi и Bridge, представляют аналогичные вызовы. Успех в Stratego может быть перенесён на них. Bridge особенно интересна благодаря сочетанию неполной информации, кооперации в парах и сложной системы объяснений ходов. Изменённые правила Stratego (перевёрнутые фишки, перемещение бомб) создают новые тактические возможности, которые ИИ осваивает быстрее людей. Появление ИИ, превосходящего лучших людей, вызывает ностальгическую грусть у игроков, ценящих игру как человеческий опыт. Ранее считалось, что Stratego слишком сложна для ИИ из-за неопределённости, но опыт игроков показывает, что шаблоны поведения и блеф можно систематизировать. Electronic Stratego с упрощённой системой раскрытия рангов (выше/ниже/равно) оказалась для некоторых игроков даже интереснее оригинала. Существуют онлайн-архивы и прототипы ИИ для Stratego, включая простые реализации, доступные для немедленной игры. Филлипинская игра Game of the Generals является прямым аналогом Stratego, что указывает на универсальность структуры неполной информации в настольных играх.