Объяснение сильной системы искусственного интеллекта для DouDizhu, самого популярного китайского покера

Начиная с AlphaGo и AlphaZero, искусственный интеллект (AI) за последние годы добился обнадеживающего прогресса, обойдя лучших игроков в го, шахматах, техасском холдеме, DOTA, Starcraft и т. Д. Итак, какова следующая задача? ?

В этой статье я хотел бы представить документ ICML, в котором представлена ​​новая система искусственного интеллекта для китайской игры в покер DouDizhu (斗地主 по-китайски). DouDizhu - самая популярная покерная игра в Китае, в которой ежедневно принимают участие сотни миллионов игроков, и каждый год проводится множество турниров. Легко научиться, но сложно освоить. Интересно, что DouDizhu остается серьезной проблемой для ИИ из-за конкуренции, сотрудничества и большого количества возможных ходов от хода к ходу.

Что такое ДоуДичжу и почему это сложно?

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

Короче говоря, следующие свойства делают DouDizhu очень сложной задачей для ИИ:

  1. Информация о несовершенстве. В отличие от го или шахмат, игроки в ДоуДичжу не могут наблюдать за руками других игроков. Это приводит к взрыву возможностей.
  2. И соревнование, и сотрудничество: два игрока-крестьянина должны сотрудничать, чтобы сражаться против игрока-арендодателя. Большинство предыдущих покерных ИИ были разработаны для соревновательных настроек, таких как Техасский Холдем, или для совместной работы, таких как Ханаби. Соревнование и сотрудничество - открытая задача.
  3. Большое и сложное поле действия: 27 472 возможных хода из-за комбинаций карт. Судебные действия значительно различаются от очереди к ходу. Существующие ИИ часто поддерживают только очень простые и небольшие области действия.

Освоение DouDizhu с нуля с DouZero

Несмотря на эти проблемы, я рад представить недавний проект ICML paper и DouZero. DouZero впервые реализует мощный ИИ DouDizhu, который можно обучить с нуля с помощью глубокого обучения с подкреплением для достижения производительности на уровне человека. Интересно, что магия DouZero на удивление проста, но очень эффективна. Также авторы разрабатывают онлайн-демонстрацию на основе нашего RLCard project. Вы можете попробовать демо здесь.

Давайте погрузимся в методы, лежащие в основе DouZero. Используемый основной алгоритм называется Deep Monte-Carlo (DMC), который представляет собой глубокую версию классических методов Монте-Карло (MC) для обучения с подкреплением. Целью методов MC является оптимизация значений Q Q (s, a), где s обозначает состояние, а a - действие . Ключевая идея методов MC - оптимизировать политику путем итеративного выполнения следующих процедур:

  1. Создайте серию, используя текущую политику.
  2. Для каждого s, появлялся в эпизоде, вычислите и обновите Q (s, a) с возвратом, усредненным по всем выборкам, относящимся к s , а.
  3. Для каждого s в эпизоде ​​обновите политику, указав действие, которое приводит к наибольшему Q (s, a).

Средняя доходность на Шаге 2 обычно получается из дисконтированного накопленного вознаграждения. На шаге 1 мы можем использовать epsilon-greedy для уравновешивания исследования и эксплуатации. Методы MC - это самые простые алгоритмы обучения с подкреплением. Они напрямую аппроксимируют целевые значения без начальной загрузки (т. Е. Используя значение следующего состояния для оценки значения текущего состояния, как в DQN).

Давайте посмотрим на DMC, который объединяет MC с нейронными сетями. В MC Q (s, a) представлен таблицей. Теперь мы заменяем Q-таблицу на Q-сеть, которая может быть несколькими уровнями нейронных сетей. Затем мы используем потери со среднеквадратичной ошибкой (MSE) для обновления Q-сети на шаге 2. Это приводит к так называемой DMC, то есть глубокой версии MC.

Хотя методы MC критикуются за то, что они не могут справиться с неполными эпизодами и считаются неэффективными из-за высокой дисперсии, авторы обнаружили, что DMC очень подходит для DouDizhu. С одной стороны, DouDizhu - это эпизодическая задача, поэтому нам не нужно обрабатывать неполные эпизоды. С другой стороны, DMC можно легко распараллелить, чтобы эффективно генерировать множество выборок в секунду, чтобы уменьшить проблему высокой дисперсии. Одним из преимуществ DMC является то, что его можно легко и эффективно ускорить с помощью нескольких процессов, поскольку его очень просто реализовать и запустить. DouZero дополнительно улучшает DMC с помощью нескольких процессов и кодирования действий (я расскажу позже) и, как ни удивительно, обеспечивает очень высокую производительность.

Сравнение с DQN и градиентом политики

Deep Q-Learning (DQN) и Policy Gradient (PG) - самые популярные алгоритмы обучения с подкреплением. Почему выбирают DMC, а не DQN или PG?

В PG мы часто используем аппроксиматор функций, подобный классификатору, где выходные данные линейно масштабируются с количеством действий. Однако в DouDizhu есть 27 472 возможных действия, которые делают вывод очень большим и трудным для обучения. На практике обычно не так много юридических действий на каждом ходу, и действия в DouDizhu могут быть естественным образом закодированы в матрицы карт. Таким образом, более многообещающий способ - использовать действие в качестве входных данных, чтобы мы могли избежать 27 472 действий в качестве выходных данных. Методы на основе значений могут естественно справиться с этой ситуацией, поскольку значение Q естественным образом принимает в качестве входных данных состояния и действия.

Точно так же DQN также аппроксимирует Q-значения. Однако реализовать DQN в DouDizhu сложно. У DouDizhu есть большой набор возможных действий, где разные подмножества действий будут допустимы в разные ходы. Шаг начальной загрузки в DQN основан на максимальной операции, которая требует больших вычислительных ресурсов и сложностей для реализации в переменном пространстве действий. Кроме того, DQN может страдать от переоценки, когда пространство действий велико.

Напротив, DMC очень легко реализовать и легко ускорить с помощью нескольких процессов. Хотя DMC может страдать от проблем с высокой дисперсией, авторы показали, что он хорошо работает в DouDizhu с параллельными актерами.

Внедрение DMC в DouDizhu

Состояние в DouDizhu включает в себя карты рук, исторические ходы, количество карт рук для других игроков, а действие представляет собой набор карт. DouZero кодирует каждую комбинацию карт в матрицу 15 x 4. Это представление является очень общим и может использоваться для представления любых карт. DouZero кодирует как состояния, так и действия в такие матрицы карт.

Для нейронной сети DouZero использует нейронную сеть, которая кодирует исторические ходы с помощью сети LSTM. Затем выходные данные LSTM объединяются с другими функциями, которые передаются вместе на шесть уровней MLP для генерации значений Q. На каждом этапе нам просто нужно ввести состояние и все юридические действия. Сеть будет прогнозировать Q-значения для всех юридических действий. и мы можем выбрать самый крупный.

DouZero использует три разные сети для трех позиций в DouDizhu с небольшими различиями в функциях. Затем авторы запускают 45 акторов параллельно на сервере с 4 GPU для моделирования. После нескольких дней обучения DMC неожиданно может изучить очень сильные политики. Официальная реализация находится здесь. Мы также поддержали DMC в проекте RLCard. RLCard - это набор инструментов для обучения с подкреплением в карточных играх, который в настоящее время поддерживает 8 сред, включая DouDizhu, и 4 алгоритма, включая DouZero.

Резюме

Успех DouZero предполагает, что классические методы Монте-Карло с некоторыми улучшениями могут иметь очень хорошие результаты в жесткой области - DouDizhu. Методы Монте-Карло легко реализовать и использовать с очень небольшим количеством гиперпараметров, но они очень эффективны. Надеюсь, вам понравится чтение, и эта информация поможет вам разработать агентов ИИ и решить другие проблемы. В следующих статьях я рассмотрю кодовую базу DMC и DouZero.