WikiSort.ru - Не сортированное

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

Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «Кто выиграет при правильной игре?»

Характеристики игр

Как правило, в задачах этого типа игры:

• детерминированы: без доли случая
• финитны: заканчиваются в конечное время
• с полной информацией: нет возможности скрыть что-то от противника
• включают ровно двух участников
• с невозможной (по правилам) ничьей

Отклонения от указанных характеристик единичны. Часть задач состоит как раз в доказательстве этих характеристик.

«Правильная игра»

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

Отношение к теории игр

Указанные задачи, как правило, не предполагают знания теории игр. Тем не менее, отдельные положения теории игр — интуитивно очевидные — могут использоваться (см. ниже).

Виды игр

Игры бывают следующих типов:

1. Игра-шутка

В данном типе игр победа не зависит от действий игроков и заранее известна.

2. Игры на симметрию

Для решений задач данного типа применяется идея симметрии - после какого-то момента один игрок играет симметрично другому.

3. Игры на выигрышные и проигрышные позиции

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

Используемые идеи

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

1. инвариант — один из игроков каждым своим ходом приводит состояние игры в некоторое состояние (например, сумма оставшихся незанятыми полей) и такое состояние является выигрышным. А игра является финитной
2. выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным. (См. функция Гранди).
3. необязательно разрабатывать стратегию, чтобы доказать её существование (при этом достаточно доказать т. н. «чистое существование» стратегии, не конструируя её явно).
4. если в финитной детерминированной игре с двумя участниками доказать невозможность выигрышной стратегии одного из участников, значит второй выиграет.
5. т. н. передача хода: если в некоторой ситуации игрок А может передать ход противнику, то у А позиция не хуже, чем у его противника.
6. т. н. заимствование стратегии: предположим, что второй игрок имеет стратегию; показываем, что первый может перехватить инициативу и сам воспользоваться этой стратегией.