Игры в пространстве состояний: стратегия, риск и поиск оптимальных решений 0:05
Лекция курса Stanford CS221, посвященная теории игр, завершает цикл изучения моделей на основе состояний. Ключевой особенностью игр, в отличие от Марковских процессов принятия решений (MDP), является наличие противника, чья стратегия неизвестна, что делает задачу поиска оптимальной политики более комплексной.
Понятие игры и игровое дерево 2:44
В теории игр центральным объектом является игровое дерево, где корень — это начальное состояние, а каждое ребро — возможное действие.
- Игровой процесс: Каждый путь от корня к листу представляет собой «разыгрывание» игры (траекторию). На каждом узле решение принимает либо агент (стремящийся максимизировать полезность), либо противник.
- Игры с нулевой суммой: В данном курсе рассматриваются игры для двух игроков, где полезность агента равна отрицательной полезности противника. Сумма их полезностей всегда равна нулю.
- Формальное определение: Игра определяется стартовым состоянием, функцией окончания (
isEnd), функцией определения хода игрока и функцией преемников, возвращающей доступные действия. - Разреженность вознаграждения: В играх вся полезность часто сосредоточена в конечном состоянии. Это создает проблему «разреженного вознаграждения» (sparse reward), когда промежуточные действия кажутся успешными, но ведут к проигрышу в конце.
Оценка игры и поиск оптимальной стратегии 11:06
Существует несколько подходов к анализу игр в зависимости от того, знаем ли мы стратегию противника.
- Оценка игры: При фиксированных стратегиях агента и противника значение игры — это ожидаемая полезность по всем возможным исходам. Это вычисляется либо через симуляцию (метод Монте-Карло), либо через рекурсию, что требует экспоненциального времени.
- Expected Max: Поиск оптимальной стратегии агента против фиксированной стратегии противника. Это аналогично итерации по значениям (value iteration) в MDP.
- Minimax (Минимакс): Основной принцип игр, где стратегия противника неизвестна. Мы предполагаем, что противник играет идеально и стремится минимизировать полезность агента. Агент максимизирует значение на своих ходах, а противник минимизирует — на своих.
Теория совершенной игры 33:16
Когда оба игрока действуют оптимально, это называется «совершенной игрой» (perfect play).
- Решенные игры: Если результат игры при совершенной игре известен, она считается «решенной» (solved).
- Типы решений:
- Сильно решенные: Известны значения минимакса для каждого состояния (например, крестики-нолики, Connect 4).
- Слабо решенные: Известен результат только из начальной позиции.
- Нерешенные: Шахматы и Го остаются нерешенными, несмотря на превосходство компьютеров над людьми, так как мы не знаем минимаксное значение каждой позиции.
Методы оптимизации: Alpha-Beta Pruning и эвристики 52:16
Поскольку поиск в игровом дереве требует экспоненциального времени, применяются методы ускорения.
- Alpha-Beta Pruning: Классическая техника, позволяющая не посещать узлы, которые гарантированно не повлияют на итоговое решение. Используются границы:
alpha(нижняя граница для max-узлов) иbeta(верхняя граница для min-узлов). Если интервалы не пересекаются, ветвь отсекается. - Порядок обхода: Эффективность отсечения зависит от порядка исследования преемников. Лучше сначала проверять действия, которые, скорее всего, изменят значение узла.
- Оценочные функции (Evaluation Functions): Позволяют прервать поиск на определенной глубине (depth-limited search) и оценить состояние эвристически, не доходя до листа.
