В рамках курса Stanford CS221 «Искусственный интеллект: принципы и методы» прошла лекция, посвященная продвинутым аспектам теории игр. Преподаватель Стэндфордского университета подробно разобрал, как объединить обучение с подкреплением (Reinforcement Learning) с игровыми сценариями, а также объяснил математическую природу игр с одновременными ходами и ненулевой суммой.
🤖 Обучение функций оценки: от эвристик к ИИ 0:05
В классических играх, таких как шахматы, поиск по дереву решений часто ограничивается из-за его колоссального размера. Вместо полного перебора веками использовались функции оценки (evaluation functions), которые помогали примерно определить, насколько хороша та или иная позиция . Раньше эти функции писались вручную экспертами, но современный подход подразумевает их автоматическое обучение.
Для решения этой задачи применяется алгоритм TD-learning (Temporal Difference learning). Основные принципы:
- V-значения против Q-значений: В отличие от алгоритма SARSA, который оценивает действия (Q-значения), TD-learning фокусируется на оценке состояний (V-значения) .
- Использование модели мира: Поскольку в играх правила (переходы из состояния в состояние) обычно известны, агенту достаточно знать ценность следующего состояния, чтобы выбрать оптимальное действие .
- Бутстрапинг (Bootstrapping): Агент обновляет свою текущую оценку состояния, основываясь на не на полном исходе игры, а на оценке следующего шага («предсказание на основе предсказания») .
По словам лектора, использование обучения с подкреплением в играх обосновано не отсутствием знаний о правилах (MDP нам известен), а экспоненциальным количеством состояний, которые невозможно пересчитать простыми итерациями .
🎲 Self-Play и исторические вехи ИИ 25:19
Одной из самых элегантных концепций в обучении игровых агентов является Self-Play (самоучительство). Агент и его противник используют одну и ту же функцию ценности: агент стремится максимизировать её, а оппонент — минимизировать .
Лектор выделил три ключевых этапа в истории игрового ИИ:
- Checkers (Артур Самуэль, 1959): Программа для шашек, работавшая на компьютере с 9 Кб памяти. Она использовала линейные функции и ручные признаки, достигнув любительского уровня .
- TD-Gammon (Джеральд Тезауро, 1992): Агент для нард, который обучался через Self-Play (1 млн партий). Он использовал нейронные сети и достиг уровня эксперта-человека, предложив новые стратегии в дебютах .
- AlphaGo Zero (2016-2017): Пик технологии. Агент обучался «с нуля», имея лишь позиции камней на доске без промежуточных наград или экспертных знаний. Система победила всех предшественников и кардинально изменила понимание стратегии го людьми .
🖐️ Игры с одновременными ходами и теорема фон Неймана 38:04
В играх типа «Камень, ножницы, бумага» или «Двухпальцевая Мора» игроки ходят одновременно. Это рушит структуру обычного дерева игры .
Для анализа таких ситуаций вводятся понятия стратегий:
- Чистая стратегия: Детерминированный выбор одного действия.
- Смешанная стратегия: Распределение вероятностей между возможными действиями (например, выбрасывать «камень» в 30% случаев) .
Лектор подробно разобрал игру «Двухпальцевая Мора»: если оба игрока показывают одинаковое количество пальцев (1 или 2), выигрывает игрок А, если разное — игрок Б. Математический анализ показывает, что в чистых стратегиях второй игрок всегда имеет преимущество, так как может подстроиться под первого .
Однако ситуация меняется, когда мы переходим к смешанным стратегиям. Согласно теореме минимакса Джона фон Неймана (1928), в любой конечной игре с нулевой суммой для двух игроков значение игры при использовании оптимальных смешанных стратегий будет одинаковым, независимо от того, кто «объявляет» свою стратегию первым .
«Раскрытие вашей оптимальной смешанной стратегии не вредит вам. Вы можете заранее объявить друзьям свои вероятности, и они всё равно не смогут на этом заработать», — подчеркивает лектор .
⚖️ Равновесие Нэша и дилемма заключенного 1:06:03
Когда мы выходим за рамки игр с нулевой суммой (где выигрыш одного — это всегда проигрыш другого), правила игры в «оптимальность» меняются. В играх с ненулевой суммой цели участников могут совпадать или частично пересекаться.
Ключевым понятием здесь становится Равновесие Нэша (Джон Нэш, 1950): это такая комбинация стратегий, при которой ни один игрок не может увеличить свой выигрыш, изменив стратегию в одиночку .
Классический пример — Дилемма заключенного:
- Если оба молчат, оба получают по 1 году тюрьмы.
- Если один предает, а другой молчит — предатель выходит сухим из воды, а «молчун» получает 10 лет.
- Если оба предают — оба получают по 5 лет .
По мнению лектора, трагедия этой игры заключается в том, что равновесие Нэша здесь — когда оба предают. Хотя вариант «оба молчат» лучше для всех, он нестабилен: у каждого есть эгоистичный стимул сменить тактику, чтобы выйти на свободу сразу, что в итоге приводит обоих к худшему результату .
В отличие от игр с нулевой суммой, где решение часто единственное, в играх с ненулевой суммой может существовать несколько состояний равновесия, и они не всегда ведут к общему благу .
