Исследовать
DeepNash учится играть в Stratego с нуля, сочетая теорию игр и глубокое RL без моделей.
Системы игрового искусственного интеллекта (ИИ) вышли на новый уровень. Стратего, классическая настольная игра, более сложная, чем шахматы и го, и более хитрая, чем покер, теперь освоена. Опубликовано в Наукамы представляем ДипНэшИИ-агент, который изучил игру с нуля до уровня эксперта-человека, играя против самого себя.
DeepNash использует новый подход, основанный на теории игр и глубоком обучении с подкреплением без использования моделей. Его стиль игры приближается к равновесию Нэша, а это означает, что противнику очень сложно использовать его игру. Настолько сложно, что DeepNash вошел в тройку лучших за всю историю среди экспертов-людей на крупнейшей в мире онлайн-платформе Stratego Gravon.
Настольные игры исторически были мерилом прогресса в области искусственного интеллекта, позволяя нам изучать, как люди и машины разрабатывают и реализуют стратегии в контролируемой среде. В отличие от шахмат и го, «Стратего» — игра с несовершенной информацией: игроки не могут напрямую наблюдать за фигурами своего противника.
Эта сложность привела к тому, что другие системы Stratego на базе искусственного интеллекта изо всех сил пытались выйти за пределы любительского уровня. Это также означает, что очень успешный метод искусственного интеллекта под названием «поиск в дереве игры», ранее использовавшийся для освоения многих игр с идеальной информацией, недостаточно масштабируем для Stratego. По этой причине DeepNash выходит далеко за рамки поиска в дереве игр.
Ценность освоения Stratego выходит за рамки игр. Выполняя нашу миссию по решению проблемы интеллекта для развития науки и приношения пользы человечеству, нам необходимо создать передовые системы искусственного интеллекта, которые смогут работать в сложных реальных ситуациях с ограниченной информацией о других агентах и людях. В нашей статье показано, как DeepNash можно применять в ситуациях неопределенности и успешно сбалансировать результаты, чтобы помочь решить сложные проблемы.
Знакомство со Стратего
Stratego — это пошаговая игра с захватом флага. Это игра блефа и тактики, сбора информации и тонкого маневрирования. И это игра с нулевой суммой, поэтому любой выигрыш одного игрока представляет собой потерю такой же величины для его противника.
Stratego представляет собой сложную задачу для ИИ отчасти потому, что это игра с несовершенной информацией. Оба игрока начинают с того, что расставляют свои 40 игровых фишек в любом стартовом порядке, который им нравится, изначально скрытом друг от друга в начале игры. Поскольку оба игрока не имеют доступа к одним и тем же знаниям, им необходимо сбалансировать все возможные результаты при принятии решения, что обеспечивает сложный ориентир для изучения стратегических взаимодействий. Типы фигур и их рейтинг показаны ниже.
Левый: Рейтинг произведений. В сражениях побеждают фигуры более высокого ранга, за исключением того, что 10 (Маршал) проигрывает при атаке Шпиона, а Бомбы всегда побеждают, за исключением случаев, когда их захватывает Шахтер.
Середина: Возможная стартовая формация. Обратите внимание, как флаг надежно спрятан сзади, окруженный защитными бомбами. Две бледно-голубые области — это «озера», в которые никогда не заходят.
Верно: Игра в игре, показывающая, как Шпион Синего захватывает 10-ку Красного.
В Stratego информацию добывают с большим трудом. Личность фигуры противника обычно раскрывается только тогда, когда она встречается с другим игроком на поле битвы. Это резко контрастирует с играми с полной информацией, такими как шахматы или го, в которых расположение и идентичность каждой фигуры известны обоим игрокам.
Подходы машинного обучения, которые так хорошо работают в идеальных информационных играх, таких как AlphaZero от DeepMind, нелегко перенести в Stratego. Необходимость принимать решения в условиях неполной информации и возможность блефа делают Stratego более похожим на техасский холдем-покер и требуют человеческих способностей, как однажды заметил американский писатель Джек Лондон: «Жизнь – это не всегда вопрос удержания денег». хорошие карты, но иногда хорошо разыгрывает плохую руку».
Однако методы искусственного интеллекта, которые так хорошо работают в таких играх, как техасский холдем, не переносятся в Stratego из-за огромной продолжительности игры – часто до победы игрока приходится делать сотни ходов. Рассуждения в Stratego должны осуществляться на основе большого количества последовательных действий без очевидного понимания того, как каждое действие способствует конечному результату.
Наконец, количество возможных состояний игры (выраженное как «сложность игрового дерева») зашкаливает по сравнению с шахматами, го и покером, что делает решение этой задачи невероятно трудным. Это то, что нас волновало в Stratego и почему он на протяжении десятилетий представлял собой вызов для сообщества искусственного интеллекта.
Масштаб различий между шахматами, покером, Го и Стратего.
В поисках равновесия
DeepNash использует новый подход, основанный на сочетании теории игр и глубокого обучения с подкреплением без использования моделей. «Без моделей» означает, что DeepNash не пытается явно моделировать частное игровое состояние своего оппонента во время игры. В частности, на ранних стадиях игры, когда DeepNash мало что знает о фигурах своего противника, такое моделирование будет неэффективным, если не невозможным.
А поскольку сложность дерева игры в Stratego настолько велика, DeepNash не может использовать надежный подход к играм на основе искусственного интеллекта — поиск по дереву Монте-Карло. Поиск по дереву стал ключевым компонентом многих знаковых достижений в области искусственного интеллекта для менее сложных настольных игр и покера.
Вместо этого DeepNash основан на новой теоретико-игровой алгоритмической идее, которую мы называем регуляризованной динамикой Нэша (R-NaD). Работая в беспрецедентных масштабах, R-NaD направляет процесс обучения DeepNash к так называемому равновесию Нэша (подробнее о технических деталях см. наша газета).
Игровое поведение, приводящее к равновесию Нэша, со временем становится непригодным для использования. Если бы человек или машина играли в совершенно непригодный для эксплуатации Стратего, худший процент побед, которого они могли бы достичь, составил бы 50%, и только если они столкнулись с таким же идеальным противником.
В матчах против лучших ботов Stratego, в том числе нескольких победителей чемпионата мира по компьютерным стратегиям, процент побед DeepNash превышал 97%, а зачастую достигал 100%. Против лучших опытных игроков на игровой платформе Gravon DeepNash достиг показателя побед 84%, что позволило ему войти в тройку лучших за всю историю.
Ожидать неожидаемое
Для достижения этих результатов DeepNash продемонстрировал несколько замечательных моделей поведения как на начальном этапе развертывания частей, так и на этапе игрового процесса. Чтобы его было трудно эксплуатировать, DeepNash разработал непредсказуемую стратегию. Это означает, что первоначальные расстановки должны быть достаточно разнообразными, чтобы противник не мог обнаружить закономерности в серии игр. А на этапе игры DeepNash рандомизирует между, казалось бы, эквивалентными действиями, чтобы предотвратить склонность к использованию.
Игроки-стратеги стремятся быть непредсказуемыми, поэтому имеет смысл скрывать информацию. DeepNash весьма поразительно демонстрирует, как он ценит информацию. В приведенном ниже примере против игрока-человека ДипНэш (синий) пожертвовал, среди прочего, 7 (майор) и 8 (полковник) в начале игры и в результате смог найти 10 противника (маршал). 9 (Общий), 8 и две семерки.
В этой ранней игровой ситуации DeepNash (синий) уже обнаружил многие из самых мощных фигур своего противника, сохраняя при этом свои ключевые фигуры в секрете.
Эти усилия поставили DeepNash в существенное материальное положение; он потерял 7 и 8, в то время как его противник-человек сохранил все свои фигуры рангом 7 и выше. Тем не менее, имея надежную информацию о высшем руководстве своего оппонента, DeepNash оценил свои шансы на победу в 70% – и победил.
Искусство блефа
Как и в покере, хороший игрок-стратег иногда должен представлять силу, даже когда он слаб. DeepNash изучил множество таких тактик блефа. В приведенном ниже примере DeepNash использует 2 (слабый разведчик, неизвестный его противнику), как если бы это была фигура высокого ранга, преследующая известную 8 противника. чтобы заманить его в засаду своим шпионом. Эта тактика DeepNash, рискующая лишь незначительной фигурой, позволяет смыть и уничтожить шпиона противника, критическую фигуру.
Игрок-человек (красный) убежден, что неизвестная фигура, преследующая его 8, должна быть 10 DeepNash (примечание: DeepNash уже потерял свою единственную 9).
Узнайте больше, посмотрев эти четыре видео полнометражных игр, в которые DeepNash играет против (анонимных) экспертов-людей: Игра 1, Игра 2, Игра 3, Игра 4.
Уровень игры DeepNash меня удивил. Я никогда не слышал об искусственном игроке-стратеге, который был бы близок к уровню, необходимому для победы в матче против опытного игрока-человека. Но после того, как я сам сыграл против DeepNash, я не был удивлен тем, что он позже попал в топ-3 на платформе Gravon. Я ожидаю, что было бы очень хорошо, если бы ему разрешили участвовать в чемпионате мира среди людей.
Винсент де Бур, соавтор статьи и бывший чемпион мира по Stratego
Будущие направления
Хотя мы разработали DeepNash для четко определенного мира Stratego, наш новый метод R-NaD может быть непосредственно применен к другим играм с нулевой суммой для двух игроков, как с совершенной, так и с несовершенной информацией. R-NaD имеет потенциал, позволяющий выйти далеко за рамки игровых настроек для двух игроков и решить крупномасштабные проблемы реального мира, которые часто характеризуются несовершенной информацией и астрономическими пространствами состояний.
Мы также надеемся, что R-NaD поможет открыть новые приложения ИИ в областях, в которых участвует большое количество людей или участников ИИ с разными целями, которые могут не иметь информации о намерениях других или о том, что происходит в их среде, например, в больших масштабах. Масштабная оптимизация управления дорожным движением для сокращения времени поездки водителя и связанных с этим выбросов транспортных средств.
Создавая обобщаемую систему ИИ, устойчивую перед лицом неопределенности, мы надеемся расширить возможности ИИ по решению проблем в нашем по своей сути непредсказуемом мире.
Узнайте больше о DeepNash, прочитав наша статья в Science.
Для исследователей, заинтересованных в том, чтобы попробовать R-NaD или поработать с нашим новым предложенным методом, мы открыли исходный код. наш код.