Разбор популярного ИИ-исследователя Янника Килчера посвящен революционному алгоритму ReBeL от команды Facebook AI Research. Эта технология успешно переносит принципы работы знаменитых систем AlphaGo и AlphaZero, объединяющих глубокое обучение с подкреплением и поиск по дереву, в сферу игр с несовершенной информацией. На примере покера и теоретических моделей автор объясняет, как искусственному интеллекту удалось достичь сверхчеловеческого уровня, используя минимальные экспертные знания.
✂️ Модифицированные «камень, ножницы, бумага» как микрокосм теории игр 0:01
Для демонстрации фундаментальных проблем игр с несовершенной информацией Янник Килчер предлагает рассмотреть модифицированную версию классической игры «камень, ножницы, бумага». Правила здесь остаются прежними, за исключением одного важного нюанса: если любой из игроков выбирает «ножницы», то финальный выигрыш или проигрыш в этом раунде удваивается.
В стандартном варианте игры оптимальная стратегия очевидна — играть каждый элемент с равной вероятностью в одну треть. Однако в модифицированной версии, из-за изменения веса одной из опций, математически оптимальная стратегия кардинально смещается. Как объясняет ведущий, теперь игрокам выгодно выбирать «камень» и «бумагу» с вероятностью 0,4, а «ножницы» — лишь с вероятностью 0,2.
Интуитивно может показаться, что игроки должны чаще выбирать «ножницы» ради удвоенной награды, но они забывают про риск аналогично удвоенного проигрыша. Если один из участников начнет отклоняться от оптимума и выбирать «ножницы» чаще (например, в трети случаев), оппонент быстро заметит эту аномалию. Путем логического вывода соперник поймет, что слишком часто оказывается в ситуации, где противник ставит на уязвимые «ножницы», и скорректирует свой баланс в сторону «камня», максимизируя выигрыш и жестко наказывая инициатора за отклонение от баланса Нэша.
Янник Килчер подчеркивает, что эта простая модель наглядно иллюстрирует природу последовательного анализа подигр. В играх с несовершенной информацией стратегия каждого участника неразрывно связана с действиями и скрытыми предположениями его оппонента, что создает серьезные вычислительные препятствия для традиционного искусственного интеллекта.
🃏 Почему алгоритмы уровня AlphaZero бессильны в покере 9:46
Традиционные подходы в глубоком обучении с подкреплением, такие как deep Q-learning или архитектуры actor-critic, полагаются на нейросеть, которая оценивает текущее состояние и напрямую указывает наилучшее действие. В отличие от них, алгоритм AlphaZero просчитывает дерево игры вперед на определенную глубину, используя симулятор, а затем заменяет все последующие ходы единой численной оценкой ценности узла. Подобный гибрид обучения и поиска показал абсолютную эффективность в шахматах и го, но полностью пасует перед покером.
В играх с несовершенной информацией, где присутствует скрытая от игрока информация, прямолинейный поиск AlphaZero бесполезен. Если ограничить глубину просмотра дерева и спросить нейросеть о ценности узлов вслепую, она выдаст среднее значение, близкое к нулю, что никак не поможет найти истинно оптимальное решение.
Главная проблема заключается в фундаментальном различии природы ценности игровых состояний:
- Для алгоритма AlphaZero ценность любого узла в дереве игры зависит исключительно от того, что произойдет дальше по течению (downstream).
- В играх с несовершенной информацией ценность узла критически зависит от того, что происходило ранее по течению (upstream), то есть от предыстории и скрытых стратегий игроков.
Стоит игроку изменить свою стратегию на верхних этатах дерева, как все ценности нижележащих узлов мгновенно изменятся, требуя полной перестройки процесса поиска. По мнению Янника Килчера, именно этот барьер успешно преодолевает новый алгоритм под названием ReBeL.
🧩 Анатомия скрытых данных: от мирового состояния к информационному 18:30
Для понимания архитектуры ReBeL необходимо четко разграничить базовые теоретико-игровые понятия, которые вводит ведущий. Первым из них является «мировое состояние» (world state) — абсолютно полная картина игры, включающая скрытые карты оппонента, собственные карты игрока и общие карты на столе. В реальной игре ни один участник не обладает доступом к полному мировому состоянию, однако оно объективно существует и фиксировано в пространстве.
Взаимодействие в игре строится на основе следующих компонентов:
- Пространство действий (action space): набор легальных ходов, таких как пасс (fold), колл (call) или рейз (raise).
- Функция перехода (transition function): математическая модель, которая на основе текущего мирового состояния и выбранного действия формирует следующее состояние мира.
- Наблюдения (observations): разделяются на публичные (доступные всем, например, общие карты на столе) и приватные (доступные только конкретному игроку, например, его карманные карты).
На основе наблюдений формируется «информационное состояние» (info state) — последовательность всех действий и личных наблюдений конкретного агента во времени. Одному информационному состоянию игрока может соответствовать огромное множество реальных скрытых траекторий развития событий и чужих карт.
Янник Килчер напоминает, что классическая «стратегия» (policy) в теории игр представляет собой функцию, которая принимает на вход информационное состояние и выдает распределение вероятностей по доступным действиям. Финальной целью алгоритма ReBeL является поиск равновесия Нэша — такого профиля стратегий, при котором ни один из игроков не может увеличить свой выигрыш, в одностороннем порядке изменив собственное поведение.
🤝 Магический трюк ReBeL: переход к совершенной информации 32:54
Основная концептуальная идея авторов ReBeL заключается в том, чтобы трансформировать игру с несовершенной информацией в эквивалентную игру с совершенной информацией. Для объяснения этого парадокса Янник Килчер предлагает мысленный эксперимент с участием беспристрастного судьи.
Представьте игру, где участники вообще не видят собственных карт. Вместо этого они обязаны публично объявить судье свою полную матрицу стратегий: что они будут делать с каждой возможной картой на руках и с какой вероятностью. Судья, обладая абсолютным знанием о розданных картах, берет таблицу игрока, находит строку с его реальной картой и случайным образом разыгрывает действие на основе заявленных вероятностей.
В такой конфигурации игра радикально меняется:
- Игроки больше не принимают дискретные решения вроде «поставить $100» вслепую.
- Их действием становится отправка гигантской таблицы распределения вероятностей для всех возможных исходов.
- На основе публичных действий судьи игроки обновляют свои представления о картах друг друга по правилу Байеса.
В результате распределение вероятностей того, какую карту держит каждый из игроков, становится абсолютно общим знанием (common knowledge) для всех участников в любой момент времени. Янник Килчер обращает внимание на критически важный вывод авторов исследования: две эти игры стратегически абсолютно идентичны. ReBeL переводит процесс в так называемое «публичное состояние убеждений» (public belief state, PBS), превращая сложнейший покер в игру с полной информацией в непрерывном пространстве состояний и действий.
📉 Как победить проклятие размерности с помощью Теоремы 1 44:41
Несмотря на теоретическую изящность, прямое построение дерева поиска поверх публических состояний убеждений (PBS) вычислительно невозможно. Пространство PBS обладает колоссальной размерностью, а передача огромных таблиц стратегий в качестве действий порождает «проклятие размерности», делая алгоритмы вроде AlphaZero неприменимыми в лоб.
Однако авторы ReBeL нашли математическую лазейку. По словам Янника Килчера, в играх для двух игроков с нулевой суммой эти высокоразмерные представления сводятся к задачам выпуклой оптимизации. Алгоритм задействует это свойство, осуществляя поиск с помощью итеративного градиентного спуска.
Ключевым прорывом работы стала «Теорема 1». Она математически связывает колоссальную по размерности ценность глобального публичного состояния убеждений с ценностями индивидуальных информационных состояний отдельных игроков. Информационные состояния имеют несопоставимо меньшую размерность.
Благодаря этому открытию отпала необходимость обучать нейросеть оценивать громоздкие PBS целиком. Вместо этого ReBeL обучает компактную нейросеть аппроксимировать ценность конкретных информационных состояний. Обучение происходит в режиме бутстраппинга (самообучения), аналогично тому, как это реализовано в AlphaZero.
⚙️ Пошаговый разбор работы алгоритма ReBeL 55:24
Архитектурный гений ReBeL заключается в том, что он выполняет итерационный поиск в дискретном (исходном) представлении игры, используя ценности информационных состояний, полученные от нейросети.
Процесс работы алгоритма состоит из следующих шагов:
- Инициализация подигры: В любой точке игры, где оказывается агент, на основе текущего публичного состояния убеждений (PBS) генерируется подигра с ограниченной глубиной просмотра.
- Установка начальных значений: Ценности терминальных (листовых) узлов этой подигры временно запрашиваются у обученной нейросети с учетом текущих параметров.
- Запуск внутреннего солвера: Запускается алгоритм декомпозиции минимизации контрфактического регрета (CFRD) — специальная версия классического метода CFR для подигр ограниченной глубины.
- Итеративное обновление стратегии: CFRD формирует оптимальный профиль стратегий на основе текущих оценок ценности узлов.
- Корректировка ценностей: Поскольку ценность листовых узлов в покере динамически зависит от выбранной на верхних уровнях стратегии, нейросеть заново пересчитывает ценности листьев с учетом свежего профиля политик.
- Циклический повтор: Процедура «обновление стратегии — пересчет ценностей» повторяется фиксированное число раз $T$ до момента схождения.
Накопленная и усредненная за $T$ итераций стратегия является математически доказанным приближением к истинному равновесию Нэша. По словам Янника Килчера, многократное решение одной и той же подигры — это вынужденная вычислительная плата за возможность работать в компактном дискретном пространстве вместо бесконечного пространства убеждений.
🏆 Триумф над человеком и этика открытого кода 1:05:05
В ходе практических экспериментов ReBeL продемонстрировал сверхчеловеческий уровень игры в хедз-ап безлимитный техасский холдем. При этом система задействовала на порядок меньше специфических экспертных знаний о покере, чем ее знаменитые предшественники Libratus или DeepStack. Из заложенных человеком ограничений в ReBeL присутствовал лишь фиксированный набор размеров ставок для дискретизации дерева.
Важнейшее преимущество алгоритма раскрывается на этапе инференса (тестирования). ReBeL способен вычислять эффективную стратегию для абсолютно любых произвольных размеров стека и ставок за считанные секунды прямо во время матча. Предыдущие ИИ требовали для адаптации к изменившимся размерам чипов колоссальных многочасовых перевычислений.
Именно этот технологический прорыв заставил команду Facebook AI Research проявить предельную осторожность при публикации результатов. В Broader Impact statement (заявлении о более широком воздействии) авторы открыто признали, что главный риск их технологии — мгновенное появление коммерческих ботов для мошенничества в онлайн-покере. Если бы обученная нейросеть попала в открытый доступ, это могло бы разрушить индустрию интернет-покера.
По этой причине разработчики приняли беспрецедентное решение: они полностью закрыли код покерной реализации ReBeL. Вместо этого в open-source была выложена версия алгоритма для игры Liar's Dice («Кости лжеца») — сугубо развлекательной дисциплины, в которую люди не играют на реальные деньги. Янник Килчер выразил искреннее восхищение таким ответственным и прагматичным подходом академического сообщества.
