Сравнение Player of Games (PoG) и AlphaZero

Привет всем, сегодня мы будем сравнивать Player of Games (PoG) с AlphaZero. PoG — это новый агент искусственного интеллекта, разработанный DeepMind, и он первый в своем роде, достигший высокого уровня производительности как в идеальных, так и в несовершенных информационных играх.

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

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

Традиционно идеальные и несовершенные информационные игровые боты использовали разные подходы. Совершенные информационные игровые ИИ, такие как AlphaZero, используют Поиск по дереву Монте-Карло (MCTS). В то время как успешные игровые ИИ с несовершенной информацией используют теоретико-игровые рассуждения. Эта разница в подходе связана с тем, что алгоритмы не подходят для другого типа игр. AlphaZero добилась современного геймплея в многочисленных совершенных информационных играх. Тем не менее, одним из самых больших критических замечаний в отношении AlphaZero была его неспособность хорошо работать в несовершенных информационных играх, что сделало PoG еще одним шагом вперед в обобщенных ИИ.

Описание AlphaZero

Для начала я дам краткое описание того, что такое AlphaZero и как он работает. Более подробное объяснение AlphaZero можно найти в другом моем сообщении в блоге здесь, где я объединяю AlphaZero и Transformers.

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

AlphaZero и несовершенные игры

AlphaZero использует комбинацию нейронных сетей (NN) и MCTS при планировании действий. Этот подход очень успешен для совершенных информационных игр, поскольку MCTS теоретически сходится с алгоритмом поиска MiniMax для этого типа игр при достаточной вычислительной мощности. MiniMax — это жадный алгоритм поиска, который ищет все возможные ходы игрового дерева и теоретически может решать все игры с идеальной информацией при наличии достаточной вычислительной мощности. AlphaZero использует MCTS вместо MiniMax, потому что современные вычислительные ограничения делают MiniMax неприменимым для игр высокой сложности, таких как шахматы и го. Однако MCTS имеет слабую производительность при несовершенных информационных играх, поскольку не может гарантировать сходимость с равновесием Нэша.

Деревья игр отлично подходят для идеальных информационных игр, поскольку вы теоретически можете знать реакцию на каждое действие, поскольку этот тип игры находится в равновесии Нэша. Однако с несовершенными играми эта логика не работает. Чтобы лучше понять, почему эта логика не работает, давайте возьмем пример с покером. В покере игроки могут блефовать, что дает им возможность выиграть, даже если их карты не лучше, чем у их оппонентов, что добавляет игре большую неопределенность. Из-за этой дополнительной неопределенности, если у вас нет наилучшей возможной руки в игре, вы никогда не будете точно уверены, выиграете вы или нет, что очень затрудняет правильное перемещение по дереву игры. Из-за этого AlphaZero плохо подходит для несовершенных информационных игр из-за противоречивости результатов при использовании MCTS.

Описание PoG

PoG использует NN и контрфактическую минимизацию сожаления о растущем дереве (GT-CFR) при планировании действий. GT-CFR — это вариант алгоритма контрфактической минимизации сожалений (CFR). GT-CFR — это двухэтапный алгоритм, использующий CFR+ для оптимизации своей политики для минимального сожаления, за которым следует фаза расширения, в которой он расширяет игровое дерево аналогично MCTS.

Фаза обновления политики

Чтобы лучше понять этот алгоритм, давайте сначала рассмотрим фазу оптимизации политики. Семейство алгоритмов CFR использует идею минимизации сожалений в качестве оптимальной стратегии. GT-CFR использует CFR+, чтобы свести к минимуму сожаление, поскольку он является предшественником ванильного алгоритма CFR и имеет более быструю сходимость равновесия Нэша. Алгоритм CFR+ определяет сожаление как;

измерение того, сколько дополнительной полезности можно было бы получить, следуя какой-либо альтернативной стратегии, а не задним числом [9]

Это означает, что он ищет предпринятые действия, в которых в среднем мог бы быть лучший результат.

Чтобы свести к минимуму сожаление, CFR+ выполняет поиск по всему общедоступному дереву, используя сожаление-сопоставление+. Regret-matching+ — это существенное обновление, сделанное в CFR+ по сравнению с ванильным алгоритмом CFR. При сопоставлении сожалений+ мы нормализуем кумулятивное значение сожаления Q, чтобы обновить политику. Обновляя политику таким образом, мы эффективно учитываем неопределенность в играх с несовершенной информацией.

Значение Q является одним из улучшений, внесенных в математику сожалений, поскольку оно позволяет вычислять кумулятивное сожаление во время прямого прохода без необходимости хранения сожалений. Чтобы определить совокупное сожаление, мы используем следующее уравнение.

Мгновенное сожаление можно найти, просмотрев все другие варианты, чтобы увидеть, существуют ли какие-либо лучшие ходы. Чтобы определить мгновенное сожаление, мы используем следующее уравнение.

ИИ PoG использует сеть ценностей и политик (CVPN) для прогнозирования контрфактических значений и политик. На листовых узлах мы делаем запрос к CVPN, позволяя ему действовать как оракул. Использование CVPN таким образом позволяет сделать фазу расширения возможной, поскольку без CVPN мы не смогли бы предсказать контрфактическое значение и политику узлов, которые ранее не были замечены.

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

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

Фаза расширения дерева

Теперь, когда мы понимаем, как CFR+ используется в этом алгоритме для оптимизации политики, мы рассмотрим этап расширения дерева. Если вы знакомы с MCTS, этап расширения дерева должен выглядеть для вас очень похоже. Лучший путь определяется с помощью следующего уравнения при обходе дерева игры.

При обходе игрового дерева мы расширяемся на k дочерних элементов при встрече с конечным узлом. Как только дерево будет развернуто, количество посещений узлов обновится для использования в уравнении pUCT.

Идея расширяющегося дерева игр является новой для GT-CFR и дает те же преимущества, что и MCTS, где мы можем играть в игры высокой сложности, управляя поиском дерева с помощью NN.

Спасибо

И вот оно. Надеюсь, теперь вы лучше понимаете различия между PoG и AlphaZero и почему PoG — это еще один шаг вперед в обобщенном ИИ.

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

Ссылка