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

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

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

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

Как различать выигрышные и проигрышные позиции

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

Разбор задач

Задача 1. Нужно забрать последний камень; за ход разрешено взять 1, 2 или 3 камня. Определим тип позиций с 1–4 камнями, проверяя, что останется сопернику. Последний камень приносит победу взявшему, поэтому позиция без камней для следующего игрока проигрышна. Удобно начинать с неё и рассматривать доступные ходы.

1. При 1 камне игрок берёт его и выигрывает сразу.
2. При 2 камнях он может взять оба, а при 3 — взять все три; обе позиции выигрышны.
3. При 4 камнях можно взять 1, 2 или 3 камня. Сопернику останется соответственно 3, 2 или 1 камень, а каждая такая позиция для него выигрышна.

Ответ: позиции с 1, 2 и 3 камнями выигрышные, а с 4 камнями — проигрышная. Игрок в позиции с четырьмя камнями не может закончить игру своим ходом и не может оставить сопернику проигрышное количество.

Задача 2. На столе кучка от 0 до 8 камней. За ход можно убрать 1 или 2 камня, выигрывает взявший последний. Нужно классифицировать позиции по порядку, начиная с пустой кучки. Позиция с 0 камней проигрышна для игрока, которому ходить: взять камень он не может, а последний камень уже взял предыдущий игрок.

1. Из 1 или 2 камней можно забрать всё, поэтому обе позиции выигрышны.
2. Из 3 камней любой ход оставляет 1 или 2. Это выигрышные позиции соперника, значит, 3 проигрышны.
3. Из 4 камней можно убрать 1 и оставить 3. Поэтому 4 выигрышна; из 5 камней можно убрать 2 и тоже оставить 3, значит, 5 выигрышна.
4. Из 6 камней ход оставит 4 или 5, обе позиции выигрышны. Значит, 6 проигрышна; из 7 и 8 можно оставить 6, поэтому они выигрышны.

Ответ: проигрышны 0, 3 и 6 камней; выигрышны 1, 2, 4, 5, 7 и 8 камней. Каждый вывод получен из уже определённых позиций, поэтому проверять длинные цепочки ходов не пришлось.

Задача 3. Имеются две кучки по 3 и 5 камней. За ход разрешено убрать любое положительное число камней из одной кучки, а победит тот, кто заберёт последний камень. Чтобы найти выигрышный ход, ищем позицию, в которой соперник не сможет изменить равенство кучек в свою пользу. Если оставить одинаковое число камней, соперник, убрав часть одной кучки, откроет возможность повторить такой же ход с другой.

1. Из кучки с 5 камнями убираем 2 камня, не трогая кучку из 3.
2. Получается позиция (3, 3), то есть обе кучки равны.
3. Если соперник уберёт несколько камней из одной кучки, мы можем убрать столько же из другой и снова оставить равные кучки. Так можно продолжать, пока сопернику не придётся взять последние камни.

Ответ: выигрышный ход — убрать 2 камня из кучки из 5, оставив позицию (3, 3). При правильном ответе на действия соперника игрок, сделавший этот ход, заберёт последние камни.

Типичные ошибки

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

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

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

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

Связь с другими темами

Для анализа позиций нужно уметь читать правила игры, перечислять все допустимые ходы и прослеживать последствия каждого из них. Это связывает тему с алгоритмами: ход за ходом можно описать порядок действий и проверить возможные варианты. Чем точнее выписаны правила, тем меньше риск пропустить важный ход или учесть запрещённый.

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

Что запомнить

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