Информатика и искусственный интеллект: учебник для 10–11 классов

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

Камень, ножницы, бумага уже предупреждают

Пусть строковый игрок выбирает смешанную стратегию $p$ , столбцовый — $q$ , а матрица выигрыша первого

A= \begin{pmatrix} 0&-1&1\\ 1&0&-1\\ -1&1&0 \end{pmatrix}.

Ожидаемый выигрыш равен $p^\top Aq$ . Равновесие Нэша — равномерная смесь $(1/3,1/3,1/3)$ . У неё нет единственного «лучшего хода»; ценна непредсказуемость.

Если обучать лучший ответ только против последнего соперника, стратегии вращаются: бумага побеждает камень, ножницы — бумагу, камень — ножницы. Новая версия сильнее предыдущей и всё же уязвима для более старой. Поэтому граф «версия 8 победила версию 7» не задаёт линейную шкалу мастерства.

Матрица результатов трёх стратегий и циклический граф доминирования — Рис. 72.1. Победа над предшественником скрывает цикл
Слева дана матрица win rate, справа стрелки показывают отношение «побеждает чаще 50%». Упорядочить вершины сверху вниз невозможно: граф содержит цикл. Серый столбец «против смеси» даёт другой, более устойчивый итог.

Игра как минимакс

В конечной игре с нулевой суммой первый игрок решает

\max_p\min_q p^\top Aq,

второй —

\min_q\max_p p^\top Aq.

Теорема фон Неймана утверждает равенство значений. Смешанные стратегии нужны не из-за слабости игрока, а потому, что чистый ход может быть эксплуатируем.

В последовательной игре состояние $s$ содержит позицию, действие — допустимый ход, терминальная награда $z\in\{-1,0,1\}$ . Это MDP с особой частью состояния: очередью хода соперника. Для симметричной игры ценность позиции с точки зрения текущего игрока меняет знак после перехода.

Почему self-play создаёт данные

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

(s_t,\pi_t,z),

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

\mathcal L=(z-v_\theta(s))^2 -\pi^\top\log p_\theta(\cdot\mid s) +\lambda\|\theta\|^2.

Цель policy берётся не из человеческой записи, а из поиска. Цель value приходит только после конца партии и переносится ко всем посещённым состояниям. Это длинный credit assignment, знакомый по actor–critic, но с терминальным исходом.

Поиск MCTS и правило PUCT

Monte Carlo Tree Search многократно проходит дерево:

выбирает перспективные рёбра;
расширяет новую позицию;
оценивает её сетью;
переносит значение назад;
после бюджета ходов строит policy из счётчиков посещений.

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

a=\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$ использует найденные результаты, prior $P_\theta$ направляет поиск, дробь поощряет мало посещённые ветви. Это локальная версия обмена между исследованием и использованием из задачи о бандитах: каждый узел решает её заново для собственных действий. В начале prior силён; с ростом $N$ фактические оценки получают больший вес.

Дерево игры с этапами selection expansion evaluation backup — Рис. 72.2. Одна итерация дерева MCTS по шагам
Красный путь показывает selection по PUCT, новый узел обведён, рядом сеть выдаёт value и priors. Синие стрелки backup возвращают значение с чередующимся знаком. У рёбер подписаны $(N,Q,P)$ до и после итерации.

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

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

Поменяйте правило допуска чемпиона: одна серия из 20 игр даёт шумный вывод. Сравните его с 400 играми и перестановкой цвета/первого хода. Не принимайте процент побед без доверительного интервала.

Лига вместо зеркала

Архив хранит прошлые policy и специализированных соперников. Новая версия играет не только с собой, но и со смесью архива. Распределение соперников можно повышать для тех, против кого win rate около 50%: они дают информативные партии.

В population-based training несколько агентов развиваются параллельно. Meta-game строит матрицу результатов между ними, а затем выбирает смесь, устойчивую к лучшим ответам. Это ближе к равновесию, чем лестница одного рейтинга.

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

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

Если кандидат участвовал в выборе тестовых соперников, результат оптимистичен. Нужен замороженный evaluation pool, не влияющий на обучение. Цвета и начальные позиции балансируют; seed фиксируют; повторяющиеся дебюты учитывают как зависимые наблюдения.

Для пары игроков можно оценить Elo:

\Pr(i\text{ побеждает }j)= \frac1{1+10^{(R_j-R_i)/400}}.

Но Elo предполагает транзитивную одномерную силу. При циклах матрица попарных результатов содержит больше информации, чем рейтинг. Полезны exploitability, Nash averaging и performance profiles.

Связь с моделью Брэдли–Терри прямая: обе превращают разность скрытых баллов в вероятность победы, обе ломаются на систематической нетранзитивности.

Попарная матрица восьми агентов, Elo-рейтинг и остатки модели — Рис. 72.3. Рейтинг сжимает матрицу и теряет циклы
Слева показаны win rates всех пар. В центре — одномерный Elo. Справа — остатки «наблюдаемая минус предсказанная вероятность»: треугольный рисунок выявляет цикл стилей, невидимый в одном числе.

От AlphaGo к AlphaZero

AlphaGo сочетала обучение на человеческих партиях, reinforcement learning и поиск. AlphaGo Zero начинала только с правил и self-play, а AlphaZero распространила схему на шахматы и сёги. Это не означает «данные не нужны»: партии self-play и вычисления поиска сами являются огромным набором данных, созданным системой.

Правила должны быть точными, симулятор — быстрым, результат — объективным. В открытом мире нет удобного терминального $z$ , а действия могут иметь необратимые последствия. Поэтому перенос self-play на диалог, экономику или безопасность требует модели оппонента и очень осторожной постановки.

Практика с OpenSpiel

OpenSpiel содержит реализации игр, алгоритмы и метрики. Для школьного исследования подойдут крестики-нолики, Kuhn poker или Leduc poker. У крестиков-ноликов можно вычислить точный minimax, поэтому это хороший unit test. Kuhn poker требует смешанных стратегий и скрытой информации.

Сравните три режима: self-play против последней версии, равномерный архив и лига с приоритетом соперников около 50% win rate. Одинаковый бюджет измеряйте не эпохами, а числом симуляций или позиций. Итогом должна быть полная матрица игр, а не одна победная серия.

Мини-исследование: стратегия, которая проходит турнир, но проигрывает лиге

Сконструируйте четыре агента для расширенной игры камень–ножницы–бумага. Первый играет равномерно, второй в 70% выбирает камень, третий является лучшим ответом ко второму, четвёртый — лучшим ответом к третьему. Проведите полную round-robin матрицу минимум по 10 000 партий на пару.

Теперь сравните три правила выбора чемпиона: win rate против непосредственного предшественника, средний win rate против всех и worst-case win rate против любого соперника. Рейтинги разойдутся. Участник, созданный как лучший ответ, может выглядеть великолепно в одной колонке и быть хрупким в остальных.

Составьте evaluation mixture из архива и вычислите expected win rate каждого агента. Затем найдите такую смесь, которая максимизирует минимальный результат против чистых соперников. Для маленькой матрицы это линейная программа. Полученная смесь может не включать агента с лучшим средним.

Этот опыт подготавливает попарные модели предпочтений: одномерный score удобен, но полная матрица хранит нетранзитивную структуру. На защите показывайте обе, если residual рейтинговой модели систематичен.

Повторите tournament после ограничения каждой пары лишь двадцатью играми. Bootstrap-ом пересэмплируйте исходы и получите распределение выбора чемпиона. Циклическая структура останется, но sampling noise добавит нестабильность. Разделите эти эффекты: uncertainty уменьшается новыми партиями, нетранзитивность — нет.

Для sequential games дополнительно меняйте первый ход и начальные позиции. Иначе агент может получить рейтинг за преимущество стороны. Матрица должна хранить paired results при обоих цветах, как блокированный эксперимент.

Лига сильнее последней версии

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

Задачи

3баллов

Для строкового игрока в порядке (камень,ножницы,бумага) и того же порядка столбцов используйте матрицу выигрыша $A=\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}.$ Вычислите $e_1^\mathsf Au$ и $u^\mathsf Ae_j$ для $u=(1/3,1/3,1/3)^\mathsf T$ и всех $j=1,2,3$ . Случайности, начального состояния и единиц измерения нет; зачёт требует четыре точных ожидания и объяснение, почему смесь не обязана выигрывать отдельный ход, но не даёт положительного ожидания сопернику.

4баллов

В узле MCTS два действия имеют $(Q_a,P_a,N_a)$ : $(0{,}20;0{,}7;20)$ и $(0{,}35;0{,}3;5)$ , число посещений родителя $N=25$ , $c_{\mathrm{puct}}=1$ . Используйте ровно $\operatorname{PUCT}(a)=Q_a+c_{\mathrm{puct}}P_a\sqrt N/(1+N_a)$ и при равенстве выбирайте действие 1. Вычислите оба индекса и выбор. Затем положите $N=400$ , $(N_1,N_2)=(320,80)$ при прежних $Q,P$ и повторите расчёт. Случайности и единиц измерения нет; четыре индекса нужны с точностью $10^{-4}$ .

5баллов

У стратегий нет ничьих: $p(A>B)=0{,}7$ , $p(B>C)=0{,}7$ , $p(C>A)=0{,}7$ . Модель Elo задаёт $p(i>j)=1/(1+10^{(R_j-R_i)/400})$ . Докажите противоречие, сложив три требуемые разности рейтингов. Затем для каждого агента задайте соперника как равномерную смесь двух остальных и вычислите средний win rate, используя $p(j>i)=1-p(i>j)$ . Случайности и начального рейтинга нет; зачёт требует три численных средних и явное объяснение цикла.

6баллов

Играйте в обычные крестики-нолики $3\times3$ : X ходит первым, три знака в ряду завершают игру, заполненная доска без линии даёт ничью. Minimax точен, ценности для игрока на ходе равны $+1,0,-1$ , ничьи ходов разрешаются по строкам сверху вниз и слева направо. MCTS начинает каждый ход с пустого дерева; selection для посещённых детей максимизирует $Q_a+1{,}4\sqrt{\ln N/N_a}$ , непосещённый ход выбирается первым в том же порядке, expansion добавляет одного ребёнка, rollout выбирает допустимые ходы равномерно, backprop меняет знак ценности на каждом уровне. Для бюджетов 10, 50, 200, 1 000 симуляций сыграйте по 500 партий против minimax, по 250 для каждой стороны; PCG64 seed равен $724000+B$ . Финальный ход MCTS имеет максимум посещений, ничья разрешается тем же порядком. Зачёт требует доли побед, ничьих и поражений и три позиции, где бюджет 10 чаще всего выбирает ход с minimax-ценностью ниже оптимальной.

7баллов

Используйте open_spiel==1.5, игру kuhn_poker(players=2) и табличную REINFORCE-policy по information state. Все логиты и baseline начинаются с нуля; после партии с выигрышем $z\in\{-1,1\}$ обновляйте каждое посещение $\theta_s\leftarrow\theta_s+0{,}02(z-b_s) (\operatorname{onehot}(a)-\operatorname{softmax}\theta_s)$ и $b_s\leftarrow0{,}99b_s+0{,}01z$ , где каждый игрок использует собственный выигрыш. В каждом режиме поддерживайте две текущие policy A и B. В режиме latest в нечётной партии A занимает позицию 0, в чётной — позицию 1; A и B играют друг против друга и после партии обновляются обе. В режиме league нечётная партия ставит A на позицию 0 и обновляет только A, чётная ставит B на позицию 1 и обновляет только B. Вторую позицию занимает policy, равновероятно выбранная из замороженного пула; она не обновляется. Пул начинается двумя копиями равномерной policy. Каждые 25 000 партий сохраняйте отдельно обе текущие policy A и B и добавляйте обе в пул; после превышения 16 элементов удаляйте две самые старые. Используйте PCG64 seeds 7251 и 7252 для двух режимов и ровно 200 000 партий в каждом. Итоговый набор режима состоит из 16 policy: A и B с восьми контрольных моментов 25 000, 50 000, ..., 200 000. Для каждой пары различных policy сыграйте 50 000 новых партий, чередуя их позиции через партию, с PCG64 seed 7290; обучение при оценке запрещено. Зачёт требует матрицу win rate, Elo-fit, residual, найденный ориентированный цикл длины не менее трёх или проверку всех троек и отчёт об отсутствии цикла.

Self-play: от AlphaGo к AlphaZero