Задания № 19, 20, 21 · ЕГЭ

Позиция в игре

Как описывают состояние игры и определяют возможность победы

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Позиция в игреСлово «позиция» означает расположение или состояние объектов в данный момент.

Состояние игры в некоторый момент времени, включающее всю информацию, необходимую для определения разрешённых ходов, переходов в следующие состояния и результата игры. В задачах ЕГЭ позицию обычно задают одним или несколькими числами: например, количеством камней в куче или парами \((a,b)\) для двух куч.

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

Классификация позиций

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

\[W(P)=\begin{cases}\text{выигрышная}, & \exists\, Q\in Moves(P): L(Q),\\\text{проигрышная}, & \forall\, Q\in Moves(P): W(Q).\end{cases}\]1

Здесь \(P\) — текущая позиция, \(Moves(P)\) — множество позиций, достижимых одним ходом, а \(W\) и \(L\) обозначают выигрышность и проигрышность. Терминальная позиция без разрешённых ходов считается проигрышной для игрока, который должен ходить.

№

Пример

В куче лежит \(1\) камень, за ход можно убрать \(1\) или \(2\) камня. Ходящий убирает последний камень, поэтому позиция с одной кучей из \(1\) камня выигрышная. Позиция с \(0\) камней проигрышная: ход сделать нельзя. Позиция с \(3\) камнями также выигрышная, поскольку можно перейти в проигрышную позицию с \(1\) камнем, убрав \(2\).

Не путайте

Позиция — это не сам ход и не стратегия. Ход описывает переход из одной позиции в другую, а стратегия задаёт правила выбора ходов на всём протяжении партии. Все возможные переходы между позициями образуют граф игры.

Проверьте себя

Позиция является выигрышной, если из неё существует ход:

Главное за минуту

Главное

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