# Теория игр и обучение с подкреплением: от алгоритма TD-learning до равновесия Нэша

Источник: https://www.youtube.com/watch?v=9CKRoKFdS5Y
Канал: Stanford Online
Опубликовано: 09.03.2026

---

В рамках курса Stanford CS221 «Искусственный интеллект: принципы и методы» прошла лекция, посвященная продвинутым аспектам теории игр. Преподаватель Стэндфордского университета подробно разобрал, как объединить обучение с подкреплением (Reinforcement Learning) с игровыми сценариями, а также объяснил математическую природу игр с одновременными ходами и ненулевой суммой.

## 🤖 Обучение функций оценки: от эвристик к ИИ
[[JUMP:00:05]]

В классических играх, таких как шахматы, поиск по дереву решений часто ограничивается из-за его колоссального размера. Вместо полного перебора веками использовались функции оценки (evaluation functions), которые помогали примерно определить, насколько хороша та или иная позиция [02:11]. Раньше эти функции писались вручную экспертами, но современный подход подразумевает их автоматическое обучение.

Для решения этой задачи применяется алгоритм **TD-learning** (Temporal Difference learning). Основные принципы:

*   **V-значения против Q-значений:** В отличие от алгоритма SARSA, который оценивает действия (Q-значения), TD-learning фокусируется на оценке состояний (V-значения) [14:42].
*   **Использование модели мира:** Поскольку в играх правила (переходы из состояния в состояние) обычно известны, агенту достаточно знать ценность следующего состояния, чтобы выбрать оптимальное действие [11:27].
*   **Бутстрапинг (Bootstrapping):** Агент обновляет свою текущую оценку состояния, основываясь на не на полном исходе игры, а на оценке следующего шага («предсказание на основе предсказания») [04:47].

По словам лектора, использование обучения с подкреплением в играх обосновано не отсутствием знаний о правилах (MDP нам известен), а экспоненциальным количеством состояний, которые невозможно пересчитать простыми итерациями [13:04].

## 🎲 Self-Play и исторические вехи ИИ
[[JUMP:25:19]]

Одной из самых элегантных концепций в обучении игровых агентов является **Self-Play** (самоучительство). Агент и его противник используют одну и ту же функцию ценности: агент стремится максимизировать её, а оппонент — минимизировать [25:33].

Лектор выделил три ключевых этапа в истории игрового ИИ:

1.  **Checkers (Артур Самуэль, 1959):** Программа для шашек, работавшая на компьютере с 9 Кб памяти. Она использовала линейные функции и ручные признаки, достигнув любительского уровня [33:18].
2.  **TD-Gammon (Джеральд Тезауро, 1992):** Агент для нард, который обучался через Self-Play (1 млн партий). Он использовал нейронные сети и достиг уровня эксперта-человека, предложив новые стратегии в дебютах [35:06].
3.  **AlphaGo Zero (2016-2017):** Пик технологии. Агент обучался «с нуля», имея лишь позиции камней на доске без промежуточных наград или экспертных знаний. Система победила всех предшественников и кардинально изменила понимание стратегии го людьми [36:06].

## 🖐️ Игры с одновременными ходами и теорема фон Неймана
[[JUMP:38:04]]

В играх типа «Камень, ножницы, бумага» или «Двухпальцевая Мора» игроки ходят одновременно. Это рушит структуру обычного дерева игры [39:40]. 

Для анализа таких ситуаций вводятся понятия стратегий:

*   **Чистая стратегия:** Детерминированный выбор одного действия.
*   **Смешанная стратегия:** Распределение вероятностей между возможными действиями (например, выбрасывать «камень» в 30% случаев) [43:22].

Лектор подробно разобрал игру **«Двухпальцевая Мора»**: если оба игрока показывают одинаковое количество пальцев (1 или 2), выигрывает игрок А, если разное — игрок Б. Математический анализ показывает, что в чистых стратегиях второй игрок всегда имеет преимущество, так как может подстроиться под первого [51:23].

Однако ситуация меняется, когда мы переходим к смешанным стратегиям. Согласно **теореме минимакса Джона фон Неймана (1928)**, в любой конечной игре с нулевой суммой для двух игроков значение игры при использовании оптимальных смешанных стратегий будет одинаковым, независимо от того, кто «объявляет» свою стратегию первым [1:02:43]. 

> «Раскрытие вашей оптимальной смешанной стратегии не вредит вам. Вы можете заранее объявить друзьям свои вероятности, и они всё равно не смогут на этом заработать», — подчеркивает лектор [1:04:03].

## ⚖️ Равновесие Нэша и дилемма заключенного
[[JUMP:1:06:03]]

Когда мы выходим за рамки игр с нулевой суммой (где выигрыш одного — это всегда проигрыш другого), правила игры в «оптимальность» меняются. В играх с ненулевой суммой цели участников могут совпадать или частично пересекаться.

Ключевым понятием здесь становится **Равновесие Нэша** (Джон Нэш, 1950): это такая комбинация стратегий, при которой ни один игрок не может увеличить свой выигрыш, изменив стратегию в одиночку [1:08:49].

Классический пример — **Дилемма заключенного**:

*   Если оба молчат, оба получают по 1 году тюрьмы.
*   Если один предает, а другой молчит — предатель выходит сухим из воды, а «молчун» получает 10 лет.
*   Если оба предают — оба получают по 5 лет [1:10:46].

По мнению лектора, трагедия этой игры заключается в том, что равновесие Нэша здесь — когда оба предают. Хотя вариант «оба молчат» лучше для всех, он нестабилен: у каждого есть эгоистичный стимул сменить тактику, чтобы выйти на свободу сразу, что в итоге приводит обоих к худшему результату [1:11:42]. 

В отличие от игр с нулевой суммой, где решение часто единственное, в играх с ненулевой суммой может существовать несколько состояний равновесия, и они не всегда ведут к общему благу [1:12:12].