Новый искусственный интеллект под названием "DeepNash" освоил игру Stratego, одну из немногих культовых настольных игр, в которой компьютеры не регулярно побеждают человеческих игроков, говорится в статье, опубликованной на этой неделе. Это огромный и неожиданный результат - по крайней мере, для сообщества игроков в "Стратего".
Stratego - это игра с двумя различными задачами: она требует долгосрочного стратегического мышления (как шахматы), а также требует от игроков работы с неполной информацией (как покер). Цель игры - перемещение по доске и захват фигуры с флагом другого игрока. Каждая партия проходит на доске размером 10 x 10 с двумя квадратными озерами размером 2 x 2, блокирующими середину доски. У обоих игроков есть по 40 фигур с различными тактическими значениями, которые можно расставить в начале игры. Загвоздка в том, что вы не видите, какие фигуры у вашего противника, а он не видит, какие у вас. Когда вы планируете атаку, вы не знаете, является ли защитник высокоранговым маршалом, который побьет почти все ваши фигуры, или низкорослым сержантом, которого может уничтожить лейтенант или капитан. Некоторые из других игровых фигур включают бомбы (мощные, но неподвижные), разведчиков (которые могут перемещаться более чем на одну клетку одновременно) и шахтеров (которые могут обезвреживать бомбы), которые добавляют тактической сложности. Игра заканчивается только тогда, когда захвачен флаг одного из игроков или когда они больше не могут делать никаких законных ходов.
Все это говорит о том, что Stratego создает уникальную задачу для компьютеров. Шахматы относительно просты, потому что вся информация видна всем - в теории игр это называется "игрой с совершенной информацией". Компьютер может посмотреть на вашу защиту, смоделировать 10 или около того ходов вперед для нескольких различных вариантов и выбрать лучший из них. Это дает им серьезное стратегическое преимущество даже перед лучшими человеческими игроками. Помогает и то, что шахматы - это игра, в которой, как правило, выигрывают или проигрывают в несколько ключевых моментов, а не под постепенным давлением. Средняя шахматная партия занимает около 40 ходов, в то время как в Stratego - более 380. Это означает, что каждый ход в шахматах гораздо важнее (и для человека требует гораздо большего внимания), в то время как Stratego - более быстрая и гибкая игра.
Stratego, с другой стороны, это "игра с несовершенной информацией". Пока фигура противника не нападет или не будет атакована, вы не можете знать, что это за фигура. В покере, игре с несовершенной информацией, в которую компьютеры уже много лет могут играть на высоком уровне, существует 10^164 возможных состояний игры, и у каждого игрока есть только 10^3 возможных двухкарточных стартовых рук. В Stratego существует 10^535 возможных состояний и более 10^66 возможных развертываний - это означает, что нужно учитывать гораздо больше неизвестной информации. И это помимо стратегических задач.
В совокупности эти две проблемы делают игру Stratego особенно сложной для компьютеров (или исследователей ИИ). По словам команды, "невозможно использовать ни современные методы планирования на основе моделей совершенной информации, ни современные методы поиска несовершенной информации, которые разбивают игру на независимые ситуации". Компьютер должен уметь строить стратегические планы с учетом имеющейся у него несовершенной информации.
Но компании DeepNash удалось справиться с этой задачей. Исследователи использовали новый метод, который позволил ИИ научиться играть в "Стратего" самостоятельно, разрабатывая собственные стратегии. Он использовал алгоритм обучения на модели с усилением под названием "Регуляризованная динамика Нэша" (R-NaD) в сочетании с архитектурой глубокой нейронной сети, которая ищет равновесие Нэша - "неиспользуемую стратегию в играх с нулевой суммой для двух игроков", таких как Stratego - и, делая это, он может научиться "качественному поведению, которое можно было бы ожидать от лучшего игрока". Такой подход уже использовался в простых играх типа "дилеммы заключенного", но никогда не применялся в таких сложных играх, как эта.
DeepNash была протестирована в сравнении с лучшими существующими ботами Stratego и экспертами-людьми. Он обошел всех остальных ботов и был очень конкурентоспособен против людей-экспертов на Gravon, онлайн-платформе для настольных игр. Что еще лучше, с качественной точки зрения, он был способен играть хорошо. Он мог находить компромиссы между взятием материала и сокрытием личности своих фигур, блефовать и даже принимать расчетливые азартные решения. (Хотя исследователи также считают, что такие термины, как "обман" и "блеф", вполне могут относиться к психическим состояниям, на которые DeepNash не способен).
В целом, это захватывающая демонстрация нового способа обучения моделей ИИ для игр (и, возможно, для выполнения других подобных задач в будущем) - и она не опирается на вычислительно тяжелые стратегии глубокого поиска, которые ранее использовались для других игр, таких как шахматы, го и покер.