Self-play: от AlphaGo к AlphaZero

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

Чемпион, которого некому проверить

Обычное обучение с учителем начинается с набора правильных ответов. В игре такого набора нет: правильный ход зависит от того, кто сидит напротив. Соблазнительный выход — сделать соперником самого себя. Тогда сложность задачи автоматически подстраивается под текущий уровень: слабый агент играет со слабым, сильный — с сильным, и учебная программа рождается сама.

Ловушка прячется в слове «чемпион». Возьмём три стратегии в обычной игре камень–ножницы–бумага и посчитаем их попарные результаты точно, без всякого моделирования. Пусть строковый игрок держит смесь $p$, столбцовый — смесь $q$, а матрица выигрыша первого игрока в порядке ходов (камень, бумага, ножницы) равна

$$A= \begin{pmatrix} 0&-1&1\\ 1&0&-1\\ -1&1&0 \end{pmatrix}, \qquad A_{ij}=+1,\ \text{если ход }i\text{ бьёт ход }j.$$

Ожидаемый счёт первого игрока есть $p^\top Aq$. Если ничью считать половиной очка, то доля набранных очков (win rate) выражается через тот же счёт:

$$\mathrm{WR}(p,q)=\Pr(\text{победа})+\tfrac12\Pr(\text{ничья}) =\frac12+\frac12\,p^\top Aq .$$

Никакой случайности здесь уже нет — формула точная. Возьмём агента $K$, который в $70\%$ случаев играет камень, а бумагу и ножницы выбирает по $15\%$. Лучший ответ на него — чистая бумага $P$; она даёт

$$\mathrm{WR}(P,K)=\tfrac12+\tfrac12(0{,}70-0{,}15)=0{,}775 .$$

Лучший ответ на бумагу — чистые ножницы $S$, и они выигрывают всё: $\mathrm{WR}(S,P)=1{,}000$. А теперь замкнём круг: против исходного камнелюбивого $K$ ножницы проигрывают, $\mathrm{WR}(K,S)=0{,}775$. Каждая версия честно побеждает свою предшественницу, и всё же ни одну нельзя назвать лучшей.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Минимакс: почему смесь — не слабость

Формально мы находимся в конечной антагонистической игре. Первый игрок максимизирует гарантированный результат,

$$\underline v=\max_{p}\min_{q}\;p^\top Aq,$$

второй минимизирует то, что противник может себе гарантировать,

$$\overline v=\min_{q}\max_{p}\;p^\top Aq .$$

Всегда верно $\underline v\le\overline v$, и главная теорема теории антагонистических игр утверждает, что при разрешённых смешанных стратегиях эти числа совпадают:

$$\max_{p}\min_{q}p^\top Aq=\min_{q}\max_{p}p^\top Aq=v .$$

Для симметричной игры $A^\top=-A$, откуда $v=0$: никакая стратегия не может гарантировать себе положительный перевес. Смешивание нужно не от слабости, а потому, что любой чистый ход читается и наказывается. Мы уже встречали эту конструкцию как седловую задачу: $p$ поднимает функцию, $q$ опускает её, и решением служит точка, где ни одному не выгодно двигаться в одиночку.

Эксплуатируемость — честная линейка

Win rate против одного соперника — плохая мера силы: он зависит от того, кого позвали в соперники. Правильная линейка в антагонистической игре одна.

Посчитаем её для чистой бумаги в камень–ножницы–бумага. Наилучший ответ — чистые ножницы, поэтому

$$\mathrm{expl}(P)=\max_a(AP)_a=1, \qquad \mathrm{expl}(u)=\max_a(Au)_a=0 .$$

Эксплуатируемость не зависит от того, кого мы позвали на турнир. Она отвечает на вопрос «сколько отберёт у нас самый неприятный соперник, какого только можно придумать». Разница с win rate видна сразу: чистая бумага набирает $0{,}775$ против камнелюбивого $K$ и при этом эксплуатируема на единицу — то есть теряет максимум возможного против правильно подобранного противника.

Зеркало вращается

Теперь запустим настоящий self-play. Простейшая схема: очередная версия обучается как наилучший ответ на предыдущую,

$$p_{t+1}=\arg\max_{p}\;p^\top A\,p_t .$$

Возьмём для наглядности расширенную игру камень–ножницы–бумага–ящерица–Спок, где у каждого действия ровно два побеждённых и два победителя. Матрица $A$ снова кососимметрична, равновесие — равномерная смесь по $0{,}2$.

Запустив итерацию из чистого камня и разрешая ничьи в пользу меньшего номера действия, мы получаем последовательность

$$\text{камень}\to\text{бумага}\to\text{ножницы}\to\text{камень}\to\cdots$$

— чистый цикл периода $3$ внутри пятидействной игры. Каждая новая версия уверенно бьёт предыдущую и остаётся полностью читаемой: её эксплуатируемость равна ровно $1{,}000$ на каждом шаге, сколько итераций ни делай. График «версия $t+1$ побеждает версию $t$» рисует уверенный прогресс, которого нет.

Архив останавливает вращение

Поменяем одну строчку. Пусть новая версия отвечает не на последнюю версию, а на среднюю стратегию всего архива:

$$\bar p_t=\frac1t\sum_{k=1}^{t}p_k, \qquad p_{t+1}=\arg\max_{p}\;p^\top A\,\bar p_t .$$

Наилучший ответ по-прежнему чист, потому что линейная функция достигает максимума в вершине симплекса:

$$\arg\max_{p\in\Delta}\;p^\top A\bar p_t=e_{a^\star}, \qquad a^\star=\arg\max_a\,(A\bar p_t)_a .$$

Это классическая фиктивная игра. Отдельная версия по-прежнему остаётся чистой и эксплуатируемой на единицу — а вот средняя стратегия архива уверенно едет вниз:

$$\mathrm{expl}(\bar p_{10})=0{,}273,\qquad \mathrm{expl}(\bar p_{200})=0{,}065,\qquad \mathrm{expl}(\bar p_{2000})=0{,}018 .$$

Скорость примерно как $C/t$: за две тысячи итераций эксплуатируемость упала почти в пятнадцать раз относительно десятой итерации. Заметьте, что архив ничего не добавил к вычислениям обучения — он изменил только цель.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Откуда self-play берёт данные

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

$$(s_t,\ \pi_t,\ z),$$

где $s_t$ — позиция, $\pi_t$ — улучшенное поиском распределение ходов, $z$ — итог партии с точки зрения игрока, ходившего в $s_t$. Сеть учится предсказывать сразу и политику, и ценность:

$$\mathcal L(\theta)= \underbrace{(z-v_\theta(s))^2}_{\text{ценность}} \;-\; \underbrace{\pi^\top\log p_\theta(\cdot\mid s)}_{\text{политика}} \;+\;\lambda\|\theta\|^2 .$$

Первое слагаемое — обычная квадратичная ошибка регрессии, второе — кросс-энтропия между целевым распределением поиска и предсказанием сети, третье — знакомая $L^2$-регуляризация. Существенно, что цель политики берётся не из человеческой записи, а из собственного поиска: сеть догоняет то, что дерево нашло лучше неё.

Ценность приходит только в конце партии и переносится на все посещённые позиции — это длинное распределение заслуг, знакомое по actor–critic, но с терминальным исходом вместо пошаговой награды. Формально мы имеем дело с марковским процессом принятия решений, у которого в состояние включена очередь хода, а награда сосредоточена в терминальных вершинах.

Поиск как учитель: MCTS по шагам

Monte Carlo Tree Search многократно повторяет один и тот же цикл из четырёх действий:

1. selection — спуск от корня по уже построенным рёбрам, каждый раз выбирая ребро по индексу, сочетающему оценку и новизну;
2. expansion — добавление одной новой вершины на границе дерева;
3. evaluation — оценка новой вершины: либо случайной доигровкой, либо значением $v_\theta$ из сети;
4. backup — возврат значения по пройденному пути со сменой знака на каждом уровне, потому что ход переходит к сопернику.

После исчерпания бюджета политика строится не из оценок, а из счётчиков посещений:

$$\pi(a\mid s)=\frac{N(s,a)^{1/\tau}}{\sum_bN(s,b)^{1/\tau}} .$$

При $\tau\to0$ это чистый выбор самого посещаемого хода, при $\tau=1$ — пропорциональный. Счётчики устойчивее самих оценок $Q$: одна счастливая доигровка поднимет $Q$, но не успеет набрать посещений.

Шеннон противопоставлял полный перебор фиксированной глубины (тип A) и избирательный поиск (тип B). MCTS — это тип B, у которого избирательность не задана вручную, а вытекает из статистики: чем чаще ветвь оправдывала себя, тем больше симуляций она получает.

PUCT: бандит внутри каждого узла

В AlphaZero-подобной схеме на шаге selection действие выбирают по правилу

$$a^\star=\arg\max_a\left[ Q(s,a)+c_{\mathrm{puct}}\,P_\theta(a\mid s)\, \frac{\sqrt{\sum_bN(s,b)}}{1+N(s,a)} \right].$$

Здесь $Q$ — средняя ценность, найденная поиском, $P_\theta$ — приор от сети, а дробь поощряет мало посещённые ветви. Это в точности задача о бандитах, решаемая заново в каждом узле дерева: узел не знает истинных ценностей своих детей и должен распределить между ними ограниченный бюджет симуляций.

Проследим за числами. Пусть у корня два действия с параметрами $(Q_1,P_1,N_1)=(0{,}20;\,0{,}70;\,20)$ и $(Q_2,P_2,N_2)=(0{,}35;\,0{,}30;\,5)$, суммарное число посещений $\sum_bN=25$, $c_{\mathrm{puct}}=1$. Тогда

$$\mathrm{PUCT}(1)=0{,}20+0{,}70\cdot\frac{5}{21}=0{,}3667, \qquad \mathrm{PUCT}(2)=0{,}35+0{,}30\cdot\frac{5}{6}=0{,}6000 .$$

Выбрано второе действие: несмотря на вдвое меньший приор, у него выше оценка и гораздо меньше посещений. При $\sum_bN=400$ и $(N_1,N_2)=(320,80)$ те же формулы дают

$$\mathrm{PUCT}(1)=0{,}2436,\qquad \mathrm{PUCT}(2)=0{,}4241,$$

и выбор снова за вторым. Бонус за новизну усох (знаменатель вырос быстрее числителя $\sqrt{N}$), но разрыв в $Q$ никуда не делся.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Сколько стоит поиск

Крестики-нолики $3\times3$ удобны тем, что для них известна абсолютная истина: полный минимакс считается за доли секунды, а при безошибочной игре обеих сторон партия кончается ничьёй. Значит, играя против идеального соперника, MCTS не может выиграть ни разу — только свести вничью или проиграть. Доля поражений становится прямой мерой качества поиска.

Сыграем по $200$ партий на каждый бюджет, чередуя стороны:

$$\begin{array}{c|cccc} \text{бюджет симуляций}&10&50&200&800\\\hline \text{доля поражений}&0{,}770&0{,}425&0{,}240&0{,}020 \end{array}$$

Победных партий у MCTS не случилось ни одной — как и обещает теория. Зато доля поражений упала с $0{,}770$ до $0{,}020$: при восьмистах симуляциях на ход случайные доигровки почти всегда находят ничейную защиту.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Elo сжимает турнир до одного числа

Рейтинговая модель предполагает, что у каждого игрока есть скрытое число силы $R_i$, а вероятность победы зависит только от разности:

$$\Pr(i\ \text{побеждает}\ j)=\frac1{1+10^{(R_j-R_i)/400}} =\sigma\!\left(\frac{\ln10}{400}\,(R_i-R_j)\right).$$

Это ровно модель Брэдли–Терри в другой шкале. У неё есть жёсткое следствие. Обозначив $d_{ij}=R_i-R_j$, получаем для любой тройки

$$d_{ij}+d_{jk}+d_{ki}=0,$$

то есть логит-разности обязаны складываться по циклу в ноль. Результаты обязаны быть транзитивными. Если $i$ сильнее $j$, а $j$ сильнее $k$, то $i$ обязан быть сильнее $k$.

Проверим на восьми агентах в игре камень–ножницы–бумага–ящерица–Спок. Их попарные win rate вычислены точно и лежат в диапазоне от $0{,}250$ до $0{,}750$ — разброс огромный. А вот подогнанный методом максимума правдоподобия Elo разложил всех восьмерых на отрезке шириной $43{,}6$ очка, то есть счёл их практически равными. Остатки «наблюдение минус предсказание» при этом достигают $0{,}281$, а их среднеквадратичное значение равно

$$R_{ij}=\mathrm{WR}_{ij}-\sigma(r_i-r_j), \qquad \sqrt{\frac1{n(n-1)}\sum_{i\ne j}R_{ij}^2}=0{,}135 .$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Три правила выбора чемпиона

Возьмём тех же восьмерых и спросим, кого объявить победителем. Три разумных правила дадут три разных ответа.

По среднему win rate лидирует смешанный агент «камень+Спок» с результатом $0{,}536$. По худшему случаю он же проваливается: против своего худшего соперника он набирает всего $0{,}250$, то есть проигрывает три партии из четырёх. По этому критерию побеждает равномерный агент с гарантией ровно $0{,}500$ — он и есть равновесие игры.

Третье правило — не выбирать одного. Уберём равновесного агента из лиги и поищем смесь остальных семи, максимизирующую гарантию:

$$\max_{w\ge0,\ \sum_iw_i=1}\;\min_{j}\;\sum_iw_i\,\mathrm{WR}_{ij}.$$

Это линейная программа, и её решение даёт гарантию $0{,}499$ при том, что лучший одиночный участник из тех же семи гарантирует лишь $0{,}375$. Ни один агент лиги не был устойчив — а их смесь оказалась.

$$\underbrace{0{,}536}_{\text{лучший по среднему}} \quad\text{против}\quad \underbrace{0{,}250}_{\text{его худший случай}} \quad\text{против}\quad \underbrace{0{,}499}_{\text{гарантия смеси}}$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лаборатория лиги

Начните с архива размера $1$: это и есть игра с зеркалом. Красная линия эксплуатируемости последней версии стоит на месте, а лента чемпионов справа показывает ровный цикл. Теперь увеличьте архив до нескольких десятков — синяя кривая, эксплуатируемость средней стратегии всего прогона, поедет вниз, и столбцы состава смеси подтянутся к равновесным $0{,}2$.

Затем испортите оценку: поставьте пять партий на действие. Лучший ответ станет выбираться по шуму, лента чемпионов растеряет регулярность, сходимость замедлится. Это ровно та ситуация, когда чемпиона назначает серия из двух десятков партий. И, наконец, покрутите $\varepsilon$: небольшая примесь равномерной игры делает каждую версию менее читаемой, но вращения не отменяет — лечит именно архив, а не шум.

Оценка без утечки

Если кандидат участвовал в подборе тестовых соперников, его результат оптимистичен по той же причине, по которой оптимистична ошибка на обучающей выборке. Правило то же, что в уроке 32: пул для оценки должен быть заморожен и не влиять на обучение.

Дальше — балансировка. Право первого хода само по себе стоит дорого: в крестиках-ноликах при полностью случайной игре обеих сторон X выигрывает $58{,}6\%$ партий, O — $28{,}7\%$, ничьи составляют $12{,}7\%$. Разрыв в $29{,}9$ процентных пункта не имеет никакого отношения к мастерству. Поэтому каждую пару играют дважды со сменой сторон, а результаты хранят как связанные наблюдения — это блокированный эксперимент, а не два независимых.

Наконец, точность. Интервал Уилсона для доли побед $\hat p=k/n$ имеет вид

$$\frac{\hat p+\dfrac{z^2}{2n}\pm z\sqrt{\dfrac{\hat p(1-\hat p)}{n}+\dfrac{z^2}{4n^2}}} {1+\dfrac{z^2}{n}} .$$

Одна серия из двадцати партий даёт интервал Уилсона шириной почти $0{,}40$ — он накрывает и «сильнее», и «слабее». Четыреста партий сжимают интервал до $0{,}097$. Ту же арифметику мы разбирали в уроке 46: случайность оценки убывает как $1/\sqrt n$, и никакой красивый график этого не обойдёт.

Русская линия: Воробьёв, Брудно и «Каисса»

Николай Николаевич Воробьёв (1925–1995) построил в Ленинграде школу теории игр и первым в СССР систематически изложил теорию бескоалиционных игр — того самого класса, к которому относится и наш self-play. В его монографиях ситуация равновесия определяется не как «лучшая стратегия», а как набор стратегий, от которого никому не выгодно отклоняться в одиночку; именно эта формулировка объясняет, почему в камень–ножницы–бумага не существует чемпиона, зато существует равновесие. Воробьёв же настойчиво отделял вопрос существования решения от вопроса его вычисления — различие, которое мы наблюдали буквально: значение игры известно точно и равно нулю, а фиктивной игре понадобилось две тысячи итераций, чтобы подойти к нему на $0{,}018$.

Вторая нить — поиск. В 1963 году А. Л. Брудно опубликовал работу «Границы и ветви в задачах о наименьшей стоимости», где независимо от западных авторов описал процедуру отсечения ветвей, известную сегодня как альфа-бета. Идея прямо родственна PUCT: не тратить вычисления на ветви, которые уже не могут изменить решение. А в 1974 году программа «Каисса», созданная в Институте проблем управления Г. М. Адельсоном-Вельским, В. Л. Арлазаровым и М. В. Донским, выиграла первый чемпионат мира среди шахматных программ в Стокгольме. «Каисса» была именно системой поиска с отсечениями и словарём дебютов — предельно далёкой от нейросетей и предельно близкой к ним по духу: основное качество игры создавалось не заложенным знанием, а вычислением вариантов.

От AlphaGo к AlphaZero

AlphaGo (2016) сочетала три источника: обучение на человеческих партиях, обучение с подкреплением и поиск. AlphaGo Zero (2017) убрала человеческие партии полностью, оставив только правила и self-play; AlphaZero перенесла ту же схему на шахматы и сёги без изменения архитектуры.

Формулу «данные не нужны» из этого делать нельзя. Партии self-play и симуляции поиска сами являются гигантским набором данных — просто произведённым системой, а не собранным людьми. Заменены не данные, а их источник; и заменить его можно только там, где выполнены три условия: правила известны точно, симулятор достаточно быстр, а исход объективен.

Где self-play ломается

Симулятор становится законом мира. Агент найдёт всё, что разрешено кодом, включая ошибки реализации: победа через баг физического движка математически безупречна и предметно бесполезна. Красная команда должна искать такие стратегии до масштабного обучения, а не после.

Второе — необратимость. В играх партию можно переиграть, в экономике и безопасности — нет. Self-play предполагает дешёвые последствия ошибки; там, где они дороги, схема неприменима без модели оппонента и жёстких ограничений.

Третье — определение соперника. В шахматах соперник играет в ту же игру. В открытом мире «соперник» может менять саму постановку задачи, и равновесие, найденное в узкой модели, ничего не гарантирует за её пределами.

Практика с OpenSpiel

Библиотека OpenSpiel содержит реализации десятков игр, алгоритмы и готовые метрики, включая точный расчёт эксплуатируемости для небольших игр. Для школьного исследования подойдут крестики-нолики (есть точный минимакс — значит, есть модульный тест), Kuhn poker и Leduc poker (нужны смешанные стратегии и появляется скрытая информация).

Сравните три режима при одинаковом бюджете, измеренном в числе сыгранных позиций: self-play против последней версии, равномерный архив и лига с приоритетом соперников, у которых win rate близок к $0{,}5$. Итогом должна быть полная матрица попарных игр, а не одна победная серия. Затем подгоните к матрице Elo и посмотрите на остатки: если они систематичны, как на рис. 72.5, защищайте работу обеими картинками сразу.

Что остаётся в руках

Self-play — генератор задач, который сам подстраивается под уровень ученика, и в этом его сила. MCTS превращает текущие оценки сети в улучшенные цели, сеть возвращает поиску обобщение, и цикл замыкается. Но нетранзитивность разрушает уютную идею «новее — значит сильнее»: цикл лучших ответов вращается бесконечно, оставаясь на месте.

Лекарство не в архитектуре, а в постановке эксперимента. Архив вместо зеркала. Смесь вместо единственного чемпиона. Эксплуатируемость вместо win rate против предшественника. Замороженный пул для оценки, сбалансированные стороны и доверительные интервалы вместо одной победной серии. Всё это входит в алгоритм ничуть не меньше, чем функция потерь.

Задачи