Теория игр

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

В контексте ЕГЭ по информатике теория игр занимает особое место, поскольку требует не только вычислительных навыков, но и способности формализовать состояние, выделить допустимые ходы, определить выигрышные и проигрышные позиции, а затем построить строгую логическую схему рассуждения. Такие задания проверяют владение рекурсией, динамическим программированием, логикой, деревьями состояний и методами доказательства.

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

Формальная модель игры

1. Игра как математический объект
   

   Конечную пошаговую игру удобно описывать кортежем

   G = (S, A, T, P, W, s0)

   где:

   • S – множество игровых состояний; 

   • A(s) – множество допустимых ходов в состоянии s; 

   • T(s, a) – функция перехода, переводящая состояние s в новое состояние после хода a; 

   • P(s) – функция, определяющая игрока, который делает ход в состоянии s; 

   • W(s) – предикат или функция выигрыша, определяющая, является ли состояние терминальным и кто в нём считается победителем; 

   • s0 – начальное состояние. 

   Если все допустимые ходы и их последствия заранее известны, а случайность отсутствует, игра называется детерминированной с полной информацией. Именно такие игры наиболее характерны для заданий ЕГЭ.

2. Игровое дерево
   

   Процесс игры можно представить в виде ориентированного дерева состояний, где:

   • вершины – игровые позиции; 

   • рёбра – допустимые ходы; 

   • листья – терминальные состояния, в которых игра заканчивается. 

   Если из позиции s возможны состояния s1, s2, ..., sk, то говорят, что s имеет потомков s1, s2, ..., sk. Анализ игры заключается в определении логического статуса каждой вершины.

3. Терминальные состояния
   

   Состояние s называется терминальным, если в нём игра заканчивается и новые ходы не выполняются.
   Пример формальной записи:

   Terminal(s) ⇔ A(s) = ∅

   или, если конец игры задаётся условием:

   Terminal(s) ⇔ f(s) ≥ M

   где M – пороговое значение.

   Именно терминальные состояния служат базой для рекурсивного анализа выигрышности.

Основные понятия и классификация позиций

1. Выигрышные и проигрышные позиции
   

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

   Формально для конечных игр эти понятия определяются рекурсивно:

   • s – проигрышная позиция, если все ходы из неё ведут в выигрышные позиции; 

   • s – выигрышная позиция, если существует хотя бы один ход из неё в проигрышную позицию. 

   Это фундаментальное рекуррентное правило:

   Lose(s) ⇔ ∀ s' ∈ Next(s): Win(s')
   Win(s)  ⇔ ∃ s' ∈ Next(s): Lose(s')

2. Позиции с выигрышем за 1, 2, 3 хода
   

   В задачах ЕГЭ часто требуется более детальная классификация:

   • позиция, из которой игрок выигрывает за один ход; 

   • позиция, из которой игрок выигрывает не позднее второго своего хода; 

   • позиция, из которой он не может выиграть сразу, но может при любой игре соперника выиграть позже. 

   Тогда вводятся обозначения:

   • W1 – позиции, из которых существует ход в терминальное выигрышное состояние; 

   • L1 – позиции, из которых все ходы ведут в W1; 

   • W2 – позиции, из которых существует ход в L1; 

   • L2 – позиции, из которых все ходы ведут в W1 ∪ W2; 

   • и так далее. 

   Именно такая ступенчатая классификация лежит в основе большинства заданий 19–21 ЕГЭ по информатике.

3. Стратегия
   

   Стратегия – это правило выбора хода для каждого возможного состояния.
   Стратегия называется выигрышной, если при её использовании игрок гарантирует победу независимо от ответов соперника.

   Если стратегия зависит только от текущего состояния, а не от всей истории партии, то она называется позиционной. В детерминированных играх с полной информацией позиционных стратегий обычно достаточно.

Рекурсивный анализ игры

1. Принцип обратной индукции
   

   Если игра конечна, анализ удобнее вести с конца, начиная с терминальных состояний. Это называется методом обратной индукции.

   Алгоритм логического анализа:

   1. Найти терминальные состояния. 

   2. Объявить их базовыми. 

   3. Поочерёдно подниматься вверх по дереву: 

   • если из вершины есть ход в проигрышную вершину, то текущая вершина выигрышная; 

   • если все ходы ведут в выигрышные вершины, текущая вершина проигрышная. 

2. Рекурсивная функция оценки
   

   Для компьютерной реализации часто вводится функция:

   F(s) = статус позиции s

   Например:

   F(s) = 0,  если s терминальна
   F(s) = 1,  если существует ход в позицию со статусом 0
   F(s) = -1, если все ходы ведут в позиции со статусом 1

   Однако в школьных задачах удобнее использовать более содержательную схему:

   если позиция терминальна → False/True в зависимости от того, кто победил
   иначе анализировать потомков

3. Пример рекуррентной логики
   

   Пусть игра задаётся числом S, из которого за ход можно получить S+1 или 2S, а выигрывает тот, кто первым получает число не меньше M.

   Тогда:

   Win(s) = True,  если s ≥ M и предыдущий игрок уже выиграл
   иначе
   Win(s) = True,  если существует ход в Lose(next)
   Lose(s) = True, если все ходы ведут в Win(next)

   Здесь важно точно различать: кто совершил последний ход и для кого оценивается позиция.

Минимакс и оптимальность решений

1. Идея минимакса
   

   Если каждому терминальному состоянию сопоставить выигрыш +1, проигрыш −1, ничью 0, то в двухигровой антагонистической игре с полной информацией применяется принцип минимакса:

   • текущий игрок выбирает ход, максимизирующий свой результат; 

   • соперник выбирает ответ, минимизирующий результат первого. 

   Формально:

   V(s) = max_{a ∈ A(s)} V(T(s, a)),  если ход первого игрока
   V(s) = min_{a ∈ A(s)} V(T(s, a)),  если ход второго игрока

2. Почему в ЕГЭ чаще обходятся без полного минимакса
   

   В школьных задачах вместо числовой минимакс-оценки чаще используется логическая рекурсия выигрыша, потому что:

   • она проще для ручного анализа; 

   • не требует построения полной оценки всех листьев; 

   • естественно соотносится с формулировками «выигрывает не позже второго хода». 

   Однако с методической точки зрения задания ЕГЭ являются частным случаем минимаксного анализа.

Динамическое программирование по состояниям

1. Когда рекурсия становится таблицей
   

   Если множество состояний можно пронумеровать, а переходы зависят только от текущего состояния, то игру можно анализировать с помощью динамического программирования.

   Например, для игры с параметром S все состояния 1, 2, ..., M можно расположить по возрастанию или убыванию и вычислять их статус в таблице.

2. Табличный подход
   

   Пусть dp[s] – статус состояния s. Тогда:

   dp[s] = W, если существует ход в L
   dp[s] = L, если все ходы ведут в W

   или в более подробной классификации:

   dp[s] = W1, если есть ход в терминальное
   dp[s] = L1, если все ходы ведут в W1
   dp[s] = W2, если есть ход в L1
   ...

   Этот подход особенно удобен, если:

   • состояний немного; 

   • переходы однотипны; 

   • требуется найти все стартовые позиции с заданным свойством. 

3. Преимущества динамического подхода
   

   • исключаются повторные вычисления; 

   • можно анализировать целый диапазон стартовых значений; 

   • легко строить таблицу для ответа на несколько вопросов сразу. 

Инженерные правила решения игровых задач

1. Сначала точно определить состояние.
   В задачах ЕГЭ состояние почти всегда должно включать только те параметры, от которых зависит набор последующих ходов. Нельзя перегружать состояние лишними деталями. 

2. Явно задать условие окончания игры.
   Нужно строго понимать, какая позиция считается терминальной и кто в ней победил. 

3. Не путать “позиция после хода” и “позиция перед ходом”.
   Это одна из самых частых ошибок при рекурсивном анализе. 

4. Различать “существует ход” и “все ходы”.
   Выигрышная позиция определяется через квантор существования, проигрышная – через квантор всеобщности. 

5. При анализе “за два хода” учитывать ходы обоих игроков.
   Фраза «игрок выигрывает вторым ходом» означает, что между его первым и вторым ходом обязательно есть ход соперника. 

6. Фиксировать семантику обозначений.
   Если используются W1, L1, W2, L2, необходимо строго определить каждое обозначение до начала анализа. 

7. Проверять крайние случаи.
   Если начальная позиция уже терминальна, рекурсивная логика может измениться. 

Мини-шпаргалка по теме

1. Базовые определения
   

   Win(s)  ⇔ ∃ s' ∈ Next(s): Lose(s')
   Lose(s) ⇔ ∀ s' ∈ Next(s): Win(s')

2. Классификация по числу ходов
   

   W1: есть ход в терминальное выигрышное состояние
   L1: все ходы ведут в W1
   W2: есть ход в L1
   L2: все ходы ведут в W1 или W2
   W3: есть ход в L2

3. Минимакс
   

   V(s) = max V(next), если ход игрока Max
   V(s) = min V(next), если ход игрока Min

4. Табличный анализ
   

   для s от M−1 до 1:
       если существует ход в проигрышную позицию:
           s – выигрышная
       иначе:
           s – проигрышная

Типичные ошибки и их профилактика

Ошибка 1. Неверное понимание терминального состояния
Иногда учащиеся считают терминальной позицию, из которой можно выиграть ходом, а не ту, в которой игра уже закончилась.
Исправление: терминальное состояние – это состояние, в котором дальнейших ходов нет или победа уже зафиксирована правилами.

Ошибка 2. Смешение кванторов
Фраза «если из позиции есть хотя бы один плохой ход, то позиция плохая» неверна.
Исправление:

• выигрышная позиция – при наличии хотя бы одного хорошего хода; 
• проигрышная – если все ходы плохи. 

Ошибка 3. Неправильный анализ позиций “второго хода”
Часто пропускается логика ответа соперника.
Исправление: анализировать цепочку:
мой ход → ход соперника → мой ход

Ошибка 4. Повторный анализ одинаковых состояний
При дереве игры одно и то же состояние может встречаться многократно.
Исправление: использовать мемоизацию или таблицу динамики.

Ошибка 5. Отсутствие строгих обозначений
Без формального определения W1, L1, W2 решение становится расплывчатым.
Исправление: сначала ввести систему обозначений, затем применять её последовательно.

Связь с подготовкой к ЕГЭ по информатике

Теория игр особенно важна для заданий, где нужно:

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

Работа с такими задачами развивает:

• рекурсивное мышление; 
• умение выделять состояния; 
• навык работы с кванторами существования и всеобщности; 
• способность формально описывать стратегию и доказывать её корректность. 

С методической точки зрения теория игр тесно связана с:

• рекурсией; 
• динамическим программированием; 
• деревьями решений; 
• логикой; 
• анализом алгоритмов. 

Пять упражнений 

Упражнение 1. Игра с прибавлением 1 и удвоением
Условие. Из числа S за ход можно получить S+1 или 2S. Выигрывает тот, кто первым получает число не меньше 20. Определите, какие позиции являются выигрышными в один ход.
Решение.

Позиция выигрышна в один ход, если из неё можно сразу перейти в число ≥ 20.
То есть должно выполняться хотя бы одно из условий:

S + 1 ≥ 20
2S ≥ 20

Из первого:

S ≥ 19

Из второго:

S ≥ 10

Объединяя:

S ≥ 10

Но если рассматриваются только нетерминальные позиции, то S < 20.
Следовательно:

W1 = {10, 11, 12, ..., 19} 

Упражнение 2. Проигрышные позиции первого уровня
Условие. Для той же игры найдите позиции L1, из которых игрок не может выиграть за один ход, а любой его ход переводит соперника в W1.
Решение.

Нужно, чтобы:

1. S не принадлежало W1, то есть S < 10; 
2. обе позиции S+1 и 2S принадлежали W1. 

Проверим условие:

S+1 ≥ 10   ⇒   S ≥ 9
2S ≥ 10    ⇒   S ≥ 5

Совместно с S < 10 получаем кандидата S = 9.
Проверка:

9+1 = 10 ∈ W1
2·9 = 18 ∈ W1

Значит:

L1 = {9}

Упражнение 3. Выигрыш за два хода
Условие. Для той же игры найдите позиции W2.
Решение.

Позиция W2 – это такая позиция, из которой есть ход в L1.
Поскольку L1 = {9}, ищем все S, для которых:

S+1 = 9   или   2S = 9

Из первого:

S = 8

Из второго целого решения нет.
Следовательно:

W2 = {8}

Упражнение 4. Табличный анализ игры
Условие. Из числа S за ход можно получить S+2 или 3S. Игра заканчивается, когда S ≥ 30. Постройте фрагмент таблицы статусов для S = 1..10.
Решение.

Сначала найдём W1:

S+2 ≥ 30  ⇒  S ≥ 28
3S ≥ 30   ⇒  S ≥ 10

Следовательно, среди нетерминальных позиций:

W1 = {10, 11, ..., 29}

Теперь L1 – позиции, из которых оба хода ведут в W1.
Проверяем:

• при S = 8: 8+2=10 ∈ W1, 3·8=24 ∈ W1, значит 8 ∈ L1; 
• при S = 9: 9+2=11 ∈ W1, 27 ∈ W1, значит 9 ∈ L1. 

Для меньших значений не выполняется первое условие.
Тогда:

L1 = {8, 9}

Далее W2 – позиции, из которых можно попасть в L1:

• S+2 = 8 ⇒ S=6; 
• S+2 = 9 ⇒ S=7; 
• 3S = 8 нет; 
• 3S = 9 ⇒ S=3. 

Значит:

W2 = {3, 6, 7}

Итоговая классификация для 1..10:

1. – не определён пока
2. – не определён пока
3. – W2
4. – не определён пока
5. – не определён пока
6. – W2
7. – W2
8. – L1
9. – L1
10. – W1

Упражнение 5. Рекурсивная функция статуса
Условие. Напишите псевдокод рекурсивной функции, определяющей, является ли позиция выигрышной, если из числа S можно перейти в S+1 или 2S, а победа достигается при S ≥ M.
Решение.

функция Win(S, M): лог
    если S ≥ M то
        вернуть ЛОЖЬ
    все
    если Win(S + 1, M) = ЛОЖЬ или Win(2*S, M) = ЛОЖЬ то
        вернуть ИСТИНА
    иначе
        вернуть ЛОЖЬ
    все
конец

Пояснение.
Если S ≥ M, игра уже завершилась предыдущим ходом, следовательно, текущий игрок проиграл – функция возвращает ЛОЖЬ.
Если существует ход в проигрышную для соперника позицию, текущая позиция выигрышная.
Иначе она проигрышная.

Для ускорения практической реализации следует добавить мемоизацию.

Практические рекомендации по решению задач

1. Сначала выпишите правила игры в виде переходов. 

2. Затем явно укажите условие победы. 

3. Определите терминальные состояния. 

4. Введите обозначения W1, L1, W2, L2, если задача требует анализа по числу ходов. 

5. Если состояний много и они повторяются, используйте таблицу или мемоизацию. 

6. При оформлении решения обязательно поясняйте, почему используется: 
   

   • «существует ход»; 

   • «все ходы».

Чек-лист самопроверки

• Точно ли определено состояние игры? 
• Правильно ли задано условие окончания? 
• Не перепутаны ли выигрышные и проигрышные позиции? 
• Верно ли используются кванторы «существует» и «все»? 
• Учтён ли ход соперника при анализе выигрыша за два хода? 
• Введены ли обозначения W1, L1, W2 и т.д.? 
• Исключены ли повторные вычисления одинаковых состояний? 

Заключение

Теория игр в информатике – это не просто раздел о развлечениях или абстрактных стратегиях, а строгий инструмент анализа дискретных процессов выбора. В школьной информатике она выступает в виде конечных детерминированных игр, где особенно важны формализация состояний, рекурсивное определение выигрышности и умение строить стратегию на основе логического анализа.

Для подготовки к ЕГЭ эта тема имеет двойную ценность. Во-первых, она непосредственно представлена в ряде экзаменационных заданий. Во-вторых, она формирует универсальный стиль мышления: умение рассматривать задачу как систему состояний, переходов и стратегий. Именно это делает теорию игр одной из наиболее содержательных и интеллектуально насыщенных тем школьной информатики.