Теория игр: стратегии и баланс

1. Что такое теория игр

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

• Игроки — минимум двое.
• Цель — одинаковая у всех (купить путёвку) или разная, но связанная с выгодой сторон (начальник экономит бюджет, сотрудник хочет повышения).
• Правила — инструкции и возможности для достижения цели, строгие официальные или негласные.
• Действия — набор доступных вариантов: действовать сообща или порознь, зайти на сайт ровно в 9:00 или приехать к зданию за полчаса до открытия.
• Информация — что игрок может наблюдать и анализировать: количество оставшихся путёвок, обсуждение в общем чате.
• Взаимосвязанность решений — действия одних игроков влияют на других и меняют ход событий.

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

2. Классификация игр

Джон фон Нейман, автор теории, изначально рассматривал только деление по сумме выигрыша; позднейшие авторы дополнили классификацию. Пять основных признаков:

Классификация — не формальность: она определяет метод анализа. Последовательные игры с полной информацией анализируются обратной индукцией (раздел 3), параллельные — платёжной матрицей (раздел 4), а сложные игры с неполной информацией — симуляцией (раздел 5).

3. Последовательные игры и обратная индукция

В играх с последовательными ходами игроки ходят один за другим: каждый наблюдает ход соперника и реагирует на него. Многие такие игры — игры с полной информацией: принимая решение, игрок полностью осведомлён обо всех предыдущих ходах. Классический пример — шахматы: стратегия включает предвидение будущих ходов противника на основе текущего состояния. Последовательные игры представляются игровыми деревьями и моделируют не только настольные игры, но и деловые переговоры, торги, политическую стратегию.

Распространённый метод анализа — обратная индукция: игрок предвидит конец игры и рассуждает в обратном порядке, определяя лучший ход на ранних этапах. Разберём на игре проще шахмат.

Игра «гонка до 15». Счёт начинается с нуля; игроки по очереди прибавляют 1 или 2; побеждает тот, кто первым назовёт 15. Рассуждаем с конца. Назвать 15 может тот, кто получил счёт 13 или 14 — значит, позиция 12 проигрышна для того, чей ход: любая прибавка отдаёт сопернику победу. Но тогда выигрывает тот, кто называет 12, и проигрышной становится позиция 9 — и так далее: 12, 9, 6, 3, 0. Стратегия из этого анализа: всегда ходить на число, кратное трём.

4. Одновременные ходы: платёжная матрица

Когда игроки ходят одновременно, дерево не работает — реагировать не на что. Инструмент анализа здесь — платёжная матрица: по строкам стратегии первого игрока, по столбцам второго, в ячейках выигрыши обоих.

Дилемма заключённого — типовой пример симметричной игры. Двое задержанных не могут сговориться; каждый выбирает: молчать или дать показания. Числа в ячейках — сроки заключения (меньше — лучше):

Что бы ни выбрал второй, первому выгоднее дать показания (0 < 1 и 2 < 3) — такая стратегия называется доминирующей. Оба рассуждают одинаково, оба дают показания и получают по два года — хотя, промолчав, оба получили бы по одному. Индивидуально рациональные решения дали худший общий исход; для геймдизайнера это готовый рецепт напряжения в кооперативных механиках: сделай предательство локально выгодным.

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

5. Баланс проверяется симуляцией

Для игр сложнее — много ходов, случайность, неполная информация — точный анализ быстро становится необозримым. Рабочий метод — Монте-Карло: реализовать стратегии в коде, столкнуть их в десятках тысяч партий и посмотреть на частоты побед.

Разберём кейс: карточная игра, в которой у двух игроков по 5 карт с номиналами от 1 до 10, карты выкладываются вслепую по одной, большая карта приносит очко. Сравнивались стратегии: всегда играть наибольшую карту (PlayHighest), наименьшую (PlayLowest), медианную (PlayMedian), случайную (Random) и другие. Результаты 20 000 партий поучительны:

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

Тот же метод на C# — для простоты на разобранной выше «гонке до 15». Стратегия — функция «позиция → прибавка»; симулятор сталкивает две стратегии в серии партий:

using System;

public static class BalanceCheck
{
    // Игра «гонка до 15»: стратегия получает текущий счёт, возвращает прибавку (1 или 2)
    static readonly Random Rng = new Random();

    static int RandomStrategy(int position) => Rng.Next(1, 3);

    static int OptimalStrategy(int position)
    {
        int move = (15 - position) % 3;           // шаг до ближайшей позиции, кратной 3
        return move == 0 ? Rng.Next(1, 3) : move; // из проигрышной позиции любой ход плох
    }

    // Возвращает номер победителя (1 или 2)
    static int PlayGame(Func<int, int> first, Func<int, int> second)
    {
        int position = 0, player = 1;
        while (true)
        {
            Func<int, int> strategy = player == 1 ? first : second;
            int move = Math.Min(strategy(position), 15 - position); // нельзя перескочить 15
            position += move;
            if (position == 15) return player;
            player = 3 - player; // смена хода: 1 → 2, 2 → 1
        }
    }

    public static void Main()
    {
        const int n = 20000;
        int firstWins = 0;
        for (int i = 0; i < n; i++)
            if (PlayGame(RandomStrategy, OptimalStrategy) == 1) firstWins++;

        Console.WriteLine($"Random против Optimal: доля побед первого = {(double)firstWins / n:F4}");
    }
}

Оптимальная стратегия, ходящая второй, не проигрывает ни одной партии — ноль кратен трём, и она с первого же хода занимает проигрышные для соперника позиции. Заменив функции стратегий и правила PlayGame, этот же каркас проверяет баланс любой дуэльной механики вашей игры; в проекте Unity такой класс удобно запускать как консольную утилиту или тест редактора, не дожидаясь готового интерфейса.

Контрольные вопросы

• Перечислите шесть компонентов, присутствующих в любой игре.
  Игроки (минимум двое), цель, правила, действия, информация, взаимосвязанность решений.
• Чем игра с нулевой суммой отличается от игры с ненулевой суммой?
  С нулевой суммой — выигрыш одного равен проигрышу остальных: один забирает приз, прочие ни с чем (покер). С ненулевой — часть приза уносит каждый, но победитель получает больше других.
• Что такое обратная индукция и для каких игр она применима?
  Метод анализа последовательных игр (как правило, конечных, с полной информацией): рассуждение ведётся от конца игры к началу — терминальные позиции оцениваются сразу, а каждая предыдущая получает оценку через лучший ход из неё.
• Почему в «гонке до 15» проигрышны позиции, кратные трём?
  Позиция 12 проигрышна: любой ход (13 или 14) позволяет сопернику назвать 15. Значит, выигрывает называющий 12, и тем же рассуждением проигрышны 9, 6, 3 и 0: из позиции, кратной трём, любой ход ведёт в позицию, откуда соперник снова может пойти на кратную трём.
• Что такое доминирующая стратегия? Какая стратегия доминирует в дилемме заключённого?
  Стратегия, дающая игроку не худший результат при любом ходе соперника. В дилемме заключённого доминирует «дать показания»: и при молчании, и при показаниях второго она даёт меньший срок — хотя обоюдное молчание было бы лучше для обоих.
• Зачем нужна смешанная стратегия в «камень — ножницы — бумага»?
  Чистой выигрышной стратегии нет: каждая проигрывает какой-то другой. Равновероятный случайный выбор не позволяет сопернику подстроиться; любое устойчивое предпочтение (частый «камень») наблюдательный соперник выявляет и наказывает.
• Почему все стратегии карточной игры показали равный результат против Random, но разный друг против друга?
  Против равновероятного случайного соперника исход определяется только распределением карт — знание чужой стратегии ничего не даёт, эксплуатировать нечего. Различия проявляются в парах детерминированных стратегий: поведение соперника предсказуемо, и одна стратегия систематически его использует (PlayHighest выигрывает у PlayLowest две трети партий).

Источники

1. Нейман, Дж. фон. Теория игр и экономическое поведение / Дж. фон Нейман, О. Моргенштерн ; пер. с англ. — Москва : Наука, 1970. — 708 с.