Ataraxos от MIT обыграл лучших игроков в Stratego

Исследователи MIT, Carnegie Mellon University, New York University и Stanford University создали систему Ataraxos для игры в Stratego с неполной информацией. Она победила сильнейшего игрока мира с рекордным счётом 15:1:4 и завершила встречи с ведущими участниками чемпионата мира результатом 39:2.

Работа опубликована в журнале Nature. Авторы сообщают, что Ataraxos превзошёл прежние модели по силе игры и потребовал существенно меньше вычислительных ресурсов для обучения.

Почему Stratego сложна для алгоритмов

Stratego — настольная военная игра для двух участников, в которой каждый расставляет 40 фигур. Цель — захватить флаг противника, но типы фигур скрыты до столкновения. В ходе партии приходится строить решения, не зная полного состояния доски и намерений соперника.

Число возможных конфигураций фигур превышает 10 в 66-й степени. Это больше пространства вариантов в шахматах и делает прямой перебор непрактичным. Как отмечают авторы, методы, разработанные для игр наподобие покера, в такой постановке не масштабировались.

Самообучение и планирование во время хода

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

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

По оценке команды, модель достигла более высокой игровой силы, чем DeepNash от Google DeepMind, использовав менее одной сотой объёма обучающих примеров и менее одной тридцатой числа партий самообучения. Авторы также адаптировали подход к Barrage Stratego, Hanabi и Dou dizhu; во всех трёх играх система показала сверхчеловеческий уровень.

Где метод может быть полезен

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

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