Теория игр
Игры с нулевой суммой
1928. Фон Нейман. 25 лет. Minimax theorem за три страницы. Через 75 лет Гудфеллоу переоткрывает тот же принцип как GAN - и называет его 'minimax game'. Nash equilibrium GAN = оптимальный генератор. Теорема фон Неймана гарантирует существование этого равновесия. На практике GAN нестабилен. Теория и практика расходятся - и это само по себе отдельная наука.
- **GAN (Goodfellow 2014):** min_G max_D - буквально формула фон Неймана. Nash equilibrium = идеальный генератор. Проблема: gradient descent не гарантирует Nash equilibrium - отсюда mode collapse и training instability
- **AlphaGo / AlphaZero:** дерево игры = minimax дерево. MCTS - стохастическая апроксимация minimax вместо полного перебора $250^{150}$ узлов Go
- **Poker AI (Libratus, CFR):** Counterfactual Regret Minimization - итеративный алгоритм сходимости к Nash equilibrium. Sandholm 2017 - первый AI, победивший лучших покеристов мира в no-limit poker
- **Stockfish / шахматные движки:** Alpha-Beta pruning даёт $O(b^{d/2})$ вместо $O(b^d)$. Разница между вычислимым и невычислимым
Предварительные знания
Что значит нулевая сумма
1928. Джон фон Нейман. 25 лет. Три страницы - и теория стратегии получает математический фундамент. Через 75 лет Гудфеллоу переоткроет тот же принцип как архитектуру нейросетей и назовёт его GAN.
Игра с нулевой суммой - антагонистическая структура: каждый доллар, который выигрывает один, теряет другой. Матрица выплат $A$: строки - стратегии игрока 1, столбцы - игрока 2. Выплата игрока 2 всегда $-A$. Шахматы, покер, Matching Pennies, и - что незакономерно - обучение GAN.
| Игра | Тип антагонизма | ML-аналог |
|---|---|---|
| Шахматы | Один побеждает, другой проигрывает | AlphaZero, Stockfish (minimax tree) |
| Покер | Банк перераспределяется между игроками | Libratus, Pluribus (CFR) |
| Matching Pennies | Чистая рандомизация оптимальна | GAN без Nash equilibrium |
| GAN training | G минимизирует, D максимизирует log-prob | Minimax game (Goodfellow 2014) |
Парадокс: в игре с нулевой суммой кажется, что лучшая стратегия - непредсказуемость. Но теорема фон Неймана 1928 доказывает: существует единственная оптимальная смешанная стратегия. Случайность - не отчаяние, а математически оптимальный выбор.
GAN сходится к оптимуму потому что теорема фон Неймана гарантирует Nash equilibrium
Теорема гарантирует существование равновесия, но не сходимость алгоритма обучения к нему. Именно поэтому GAN нестабилен на практике.
Gradient descent в minimax игре не обязан сходиться к Nash equilibrium. Теория и практика расходятся: существование не равно достижимости за разумное время. WGAN частично решает это через изменение метрики.
В GAN-обучении генератор G минимизирует функцию потерь, дискриминатор D максимизирует. Это пример:
Теорема минимакса и седловая точка
Ключевой вопрос: что происходит, если каждый игрок предполагает, что противник знает его стратегию и действует оптимально? Игрок 1: максимизирует минимально гарантированный выигрыш. Игрок 2: минимизирует максимально возможные потери. Фон Нейман показал: при смешанных стратегиях эти два значения совпадают.
**Теорема минимакса (фон Нейман, 1928):** для любой матрицы $A \in \mathbb{R}^{m \times n}$: $$\max_{p \in \Delta_m} \min_{q \in \Delta_n} p^\top A q = \min_{q \in \Delta_n} \max_{p \in \Delta_m} p^\top A q = v$$ где $\Delta_m, \Delta_n$ - симплексы вероятностных распределений. Число $v$ называется **ценой игры**. Доказательство - теорема о неподвижной точке Брауэра или двойственность LP.
**Седловая точка** - геометрический образ равновесия. Элемент $a_{ij}$ матрицы является седловой точкой, если он минимален в строке $i$ и максимален в столбце $j$. Как перевал в горах: минимум вдоль одного направления, максимум вдоль другого. Если такая точка есть - равновесие достигается в чистых стратегиях.
| Условие | Тип равновесия | Пример |
|---|---|---|
| Седловая точка есть | Чистые стратегии | Некоторые шахматные позиции |
| Седловой точки нет | Смешанные стратегии | Matching Pennies, Камень-Ножницы-Бумага |
| Несколько сед. точек | Любая оптимальна | Взаимозаменяемые равновесия |
Минимаксная стратегия - это стратегия для трусов, которые боятся рисковать
Минимакс - математически оптимальная стратегия против рационального противника. Любое отклонение эксплуатируемо.
В zero-sum игре против рационального противника отклонение от минимакса предоставляет противнику гарантированное улучшение результата. Минимакс - единственная неэксплуатируемая стратегия.
Что гарантирует теорема минимакса фон Неймана?
Алгоритмы: от Alpha-Beta до CFR
Вычисление минимакса наивно требует полного обхода дерева игры: $O(b^d)$, где $b$ - ветвление, $d$ - глубина. Шахматы: $b \approx 35$, $d \approx 80$ - вселенная не хватит. Alpha-Beta pruning срезает это до $O(b^{d/2})$ за счёт одного наблюдения: ветвь, которая заведомо хуже уже найденной, можно не смотреть.
**Alpha-Beta pruning:** поддерживаются два порога - $\alpha$ (лучшее для MAX) и $\beta$ (лучшее для MIN). Ветвь отсекается когда $\alpha \geq \beta$. При идеальном порядке ходов - $O(b^{d/2})$ вместо $O(b^d)$. Используется в Stockfish, Komodo, Fritz. Именно поэтому ноутбук 1990-х обыгрывал гроссмейстеров.
Покер - другой зверь. Неполная информация: противник не знает карты. CFR (Counterfactual Regret Minimization, Sandholm 2017) - итеративный алгоритм, который сходится к Nash equilibrium через накопление сожалений. Libratus выиграл у лучших покеристов мира в 2017. CFR - по сути gradient descent на игровом многообразии.
| Алгоритм | Сложность | Применение |
|---|---|---|
| Minimax наивный | $O(b^d)$ | Игрушечные задачи |
| Alpha-Beta pruning | $O(b^{d/2})$ | Stockfish, все шахматные движки |
| MCTS + нейросеть | Стохастический | AlphaGo, AlphaZero |
| CFR | Итеративный | Libratus, Pluribus (покер) |
AlphaGo использует чистый minimax - просто с лучшей оценочной функцией
AlphaGo использует MCTS - стохастическую апроксимацию minimax с нейросетью для оценки позиций. Полный minimax для Go физически невычислим.
Go: $b \approx 250, d \approx 150$. $250^{150}$ узлов - число, несравнимо большее числа атомов во вселенной. MCTS сэмплирует траектории и оценивает их нейросетью вместо точного перебора.
Alpha-Beta pruning даёт $O(b^{d/2})$ вместо $O(b^d)$. Что это означает для шахмат ($b=35, d=80$)?
GAN как игра с нулевой суммой
Гудфеллоу 2014 описал GAN через формулу фон Неймана напрямую. Генератор $G$ минимизирует, дискриминатор $D$ максимизирует:
**GAN как minimax game (Goodfellow et al., 2014):** $$\min_G \max_D \; \mathbb{E}_{x \sim p_{\text{data}}}[\log D(x)] + \mathbb{E}_{z \sim p_z}[\log(1 - D(G(z)))]$$ Nash equilibrium этой игры: $D(x) = 1/2$ везде, $G$ воспроизводит $p_{\text{data}}$. Теорема фон Неймана гарантирует существование этого равновесия. Практика: GAN часто не сходится - gradient descent не гарантирует Nash equilibrium.
Нестабильность GAN - прямое следствие теоретического разрыва. Gradient descent на minimax задаче может осциллировать, а не сходиться. WGAN (Arjovsky 2017) меняет игру: вместо JS-дивергенции использует расстояние Вассерштейна - Lipschitz-ограниченные дискриминаторы дают более стабильную динамику.
| Версия GAN | Метрика | Стабильность |
|---|---|---|
| GAN (Goodfellow 2014) | JS-дивергенция | Нестабильно, mode collapse |
| WGAN (Arjovsky 2017) | Wasserstein-1 | Значительно стабильнее |
| WGAN-GP | W-1 + gradient penalty | Стандарт де-факто |
WGAN решает проблему GAN через лучшую архитектуру сети
WGAN меняет саму игру: JS-дивергенция заменяется расстоянием Вассерштейна, которое обеспечивает лучшие градиенты и более стабильную динамику.
JS-дивергенция может быть постоянной (не давать градиентов) когда распределения не пересекаются. W-расстояние всегда даёт ненулевой сигнал. Это изменение в теоретико-игровой постановке, не в архитектуре.
Nash equilibrium GAN - это состояние, когда $D(x) = 1/2$ везде. Почему GAN редко его достигает на практике?
Ключевые идеи
- **Zero-sum:** выплаты антагонистичны - шахматы, покер, GAN. Матрица $A$ и $-A$ одновременно
- **Теорема фон Неймана (1928):** $\max_p \min_q p^\top Aq = \min_q \max_p p^\top Aq = v$ - в любой конечной игре существует цена и оптимальные смешанные стратегии
- **Случайность оптимальна:** Matching Pennies, Камень-Ножницы-Бумага - равновесие только в смешанных стратегиях. Рандомизация 50/50 математически необходима
- **Alpha-Beta:** $O(b^{d/2})$ вместо $O(b^d)$ - разница между ноутбуком и тепловой смертью вселенной для шахмат
- **GAN = minimax game:** теорема гарантирует Nash equilibrium. Gradient descent не гарантирует его достижения - отсюда нестабильность
Связанные темы
Zero-sum игры - фундамент теории игр, открывающий путь к более богатым структурам:
- Равновесие Нэша — Нэш обобщил минимакс фон Неймана на игры без нулевой суммы
- Теория игр в ML — GAN, adversarial examples, multi-agent RL - прямые приложения zero-sum minimax
- Algorithmic Game Theory — Price of Anarchy - сколько теряет общество в не-zero-sum равновесиях
Вопросы для размышления
- GAN нестабилен несмотря на теорему фон Неймана. Что это говорит о разрыве между существованием равновесия и алгоритмической его достижимостью?
- Покер - zero-sum с неполной информацией. Почему CFR сложнее Alpha-Beta, и что значит 'counterfactual regret' с точки зрения минимакса?
- AlphaGo использует MCTS вместо точного minimax. Какую гарантию теоремы фон Неймана при этом теряют - и почему это допустимо на практике?
Связанные уроки
- gt-02 — Равновесие Нэша - обобщение минимакса на игры без нулевой суммы
- gt-12 — GAN - прямая реализация минимаксной игры: G минимизирует, D максимизирует
- gt-11 — Алгоритмическая теория игр строится поверх минимакса и LP-эквивалентности
- mt-05 — Доказательство теоремы фон Неймана использует теорему о неподвижной точке из теории меры
- la-05-matrices-intro