Игра (задача)
Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «Кто выиграет при правильной игре?»
Характеристики игр
Как правило, в задачах этого типа игры:
- детерминированы: без доли случая
- финитны: заканчиваются в конечное время
- с полной информацией: нет возможности скрыть что-то от противника
- включают ровно двух участников
- с невозможной (по правилам) ничьей
Отклонения от указанных характеристик единичны. Часть задач состоит как раз в доказательстве этих характеристик.
«Правильная игра»
«Правильной игрой» в задачах этого класса называется выигрышная стратегия из теории игр — стратегия, придерживаясь которой игрок выиграет при любых ответных действиях соперника. Правильная игра - игра, в которой оба соперника действуют разумно, пытаясь выиграть (не поддаются друг другу).
Отношение к теории игр
Указанные задачи, как правило, не предполагают знания теории игр. Тем не менее, отдельные положения теории игр — интуитивно очевидные — могут использоваться (см. ниже).
Виды игр
Игры бывают следующих типов:
1. Игра-шутка
В данном типе игр победа не зависит от действий игроков и заранее известна.
2. Игры на симметрию
Для решений задач данного типа применяется идея симметрии - после какого-то момента один игрок играет симметрично другому.
3. Игры на выигрышные и проигрышные позиции
В процессе решения задач этого типа находятся позиции, попадая в которые игрок может обеспечить себе победу - выигрышные, и из которых он не может победить при любых своих действиях - проигрышные.
Используемые идеи
В задачи-играх используются самые разные методы решения, однако есть несколько часто повторяющихся идей:
- инвариант — один из игроков каждым своим ходом приводит состояние игры в некоторое состояние (например, сумма оставшихся незанятыми полей) и такое состояние является выигрышным. А игра является финитной
- выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным. (См. функция Гранди).
- необязательно разрабатывать стратегию, чтобы доказать её существование (при этом достаточно доказать т. н. «чистое существование» стратегии, не конструируя её явно).
- если в финитной детерминированной игре с двумя участниками доказать невозможность выигрышной стратегии одного из участников, значит второй выиграет.
- т. н. передача хода: если в некоторой ситуации игрок А может передать ход противнику, то у А позиция не хуже, чем у его противника.
- т. н. заимствование стратегии: предположим, что второй игрок имеет стратегию; показываем, что первый может перехватить инициативу и сам воспользоваться этой стратегией.