Лекция 9. Смешанные стратегии: теория и теннис

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

Суть простыми словами

Иногда в игре нет одного правильного хода. Если ты всегда бьёшь в одну сторону, соперник это заметит и встанет туда. Поэтому надо чередовать ходы в правильной пропорции, чтобы тебя нельзя было предсказать. А если у тебя в чём-то одном появилось преимущество, соперник начнёт этого избегать, и тебе тоже придётся перестроиться.

Что было на лекции

Полак напомнил камень-ножницы-бумагу с шансом 1/3 на каждый вариант и дал строгое определение смешанной стратегии. У варианта может быть вероятность 0, а чистая стратегия оказалась частным случаем смеси.
Расчёт на «Битве полов»: против соперника, который ходит 50 на 50, чистые ходы игрока I приносят 1 и 1/2, а смесь 1/5 и 4/5 даёт 3/5, то есть число между ними.
Рост трёх ассистентов, отбивание «Янкиз», средний балл первого ряда. Среднее всегда между худшим и лучшим. Хочешь наибольшее среднее, оставь только лучших, равных между собой.
Главный вывод дня: если смесь оптимальна, каждый ход в ней тоже оптимален и приносит столько же.
Теннис, пример из книги Диксита и Скит. Серена у сетки. Винус бьёт обводящий удар слева или справа от Серены, а Серена заранее смещается влево или вправо. Шанс Винус выиграть очко (сначала удар Винус, потом смещение Серены): «влево, влево» 50%, «влево, вправо» 80%, «вправо, влево» 90%, «вправо, вправо» 20%. Цифры придуманы. Студент объяснил, почему не 100%: мяч может уйти в аут.
Совет телекомментаторов «всегда играй на свою силу» Полак назвал плохим. Чистого равновесия нет: лучшие ответы ходят по кругу.
Ответ: Винус бьёт влево в 70% случаев, Серена смещается влево в 60%. Если Серена смещается влево чаще, Винус выгодно всегда бить вправо, и наоборот.
Новый тренер улучшил Серене удар с лёта слева: 50 в клетке «влево, влево» стало 30. Прямой эффект зовёт Серену смещаться влево чаще. Стратегический эффект говорит обратное: Винус теперь реже бьёт туда. В голосовании аудитории многие воздержались.
Расчёт: Серена смещается влево в 50% случаев вместо 60%, Винус бьёт влево в 7/12 случаев вместо 7/10. Победил стратегический эффект.

Главные понятия

Смешанная стратегия (mixed strategy) — выбор ходов с заданными вероятностями, например «влево в 70% случаев». Чистая стратегия (pure strategy) это один ход наверняка.
Ожидаемый выигрыш (expected payoff) — средний результат с учётом вероятностей. У смеси это взвешенное среднее выигрышей её ходов.
Безразличие (indifference) — в равновесии все ходы из смеси приносят игроку поровну. Из этого уравнения находят смесь соперника.
Равновесие Нэша в смешанных стратегиях (mixed strategy Nash equilibrium) — смесь каждого игрока есть лучший ответ на смеси остальных.
Сравнительная статика (comparative statics) — меняем правило игры и сравниваем старое равновесие с новым.
Прямой и стратегический эффект (direct and strategic effect) — первый учитывает только твоё изменение, второй ещё и ответ соперника.

Зерно для создателя игр

Дуэль живёт, пока нет одного верного ответа. Пенальти, удар и блок в файтинге, выбор укрытия в прятках: если какой-то ход лучше всегда, угадывание исчезает. Лучшие ответы должны ходить по кругу.
Числа задают пропорции. Меняя шансы в клетках, дизайнер управляет тем, как часто сильные игроки выбирают каждый ход. Пропорцию можно рассчитать заранее.
Усиление может уменьшить использование. Улучшишь приём, и соперники начнут его избегать. Тогда и его владелец будет реже на него ставить. Перед изменением баланса считай не только прямой эффект, но и ответ игроков.
ИИ-сопернику нужно смешивать и наказывать шаблоны. Если игрок бьёт в одну сторону чаще равновесной доли, лучший ответ ИИ прост: всегда закрывать эту сторону. Так игра сама учит не быть предсказуемым.
Равные результаты означают здоровый баланс. Если игроки смешивают два хода, ходы приносят поровну. Если один ход заметно выгоднее, сильные игроки скоро перестанут смешивать.

Мини-игра для урока

«Обводящий удар». Двое, 10 минут, десятигранный кубик или карты от туза до десятки.

У каждого карточки «влево» и «вправо», стороны считаем от Серены. Винус и Серена тайно кладут по карточке и открывают.
Тянем карту. Винус выигрывает очко, если число не больше порога: «влево, влево» 5; «влево, вправо» 8; «вправо, влево» 9; «вправо, вправо» 2.
Играем 10 очков, записываем ходы, меняемся ролями.
«Новый тренер Серены»: порог «влево, влево» становится 3. Перед вторым туром каждый пишет прогноз: Серене теперь смещаться влево чаще или реже?

Что заметить: кто повторял один ход, тот проигрывал. По расчёту Полака после улучшения Серене выгодно смещаться влево реже. В браузере игрок может сразиться с ИИ, который замечает его привычки.

Ошибки и заблуждения

«Всегда играй на свою сильную сторону». Соперник подстроится, и сила сама по себе ничего не решает.
«Улучшил приём, значит, им будут пользоваться чаще». В примере Полака вышло наоборот.
«Смешивать значит ходить как попало». Нужны точные доли. Любой перекос соперник накажет чистым ходом.
«Смесь может дать больше лучшего хода». Не может: среднее всегда между худшим и лучшим.

Для продвинутых

Ожидаемый выигрыш линеен по смеси p_i. Отсюда: если p_i*(s_i) > 0, то s_i есть лучший ответ на p_−i*.
Теннис. Смесь Серены q из безразличия Винус: 50q + 80(1−q) = 90q + 20(1−q), q = 0,6. Смесь Винус p из безразличия Серены: 50p + 10(1−p) = 20p + 80(1−p), p = 0,7. После изменения q = 0,5 и p = 7/12.
Теорема Нэша (1950): в любой конечной игре есть равновесие, хотя бы в смешанных стратегиях. Для игр двоих с постоянной суммой, как здесь, раньше доказана теорема фон Неймана о минимаксе (1928).
Пример взят из книги A. Dixit, S. Skeath «Games of Strategy». Проверка на подачах профессионалов: M. Walker, J. Wooders «Minimax Play at Wimbledon» (2001).