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

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

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

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

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

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

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

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

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

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

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

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

Как определить исход позиции

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

Разбор задач

Задача 1. В кучке 5 камней. За ход можно взять 1 или 2 камня; выигрывает тот, кто забирает последний камень. Нужно проверить, есть ли у первого игрока способ обеспечить победу. Для этого сначала выясним, какие маленькие количества невыгодно оставлять сопернику. Рассуждать будем от уже известного конца игры.

1. Если осталось 1 или 2 камня, игрок забирает их и выигрывает. Значит, количества 1 и 2 выигрышны.
2. При 3 камнях можно взять 1 и оставить 2 либо взять 2 и оставить 1. Оба остатка выигрышны для соперника, поэтому 3 — проигрышное количество.
3. Из 5 камней можно взять 2 и оставить 3. Мы выяснили, что 3 проигрышны для того, кому предстоит ходить.

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

Задача 2. В кучке 10 камней, за ход разрешено взять 1, 2 или 3 камня. Побеждает тот, кто забирает последний. Найдём выигрышные и проигрышные количества, последовательно проверяя, куда ведут возможные ходы. Ноль камней означает, что предыдущий игрок уже забрал последний и выиграл.

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

Ответ: от 1 до 10 проигрышны 4 и 8; остальные количества выигрышны. При 10 камнях первый игрок может забрать 2 и оставить сопернику 8.

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

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

Ответ: при правильной игре победит второй игрок. У первого нет выигрышной стратегии; второй может после каждого хода первого выбрать ответ, который оставляет ему чётное количество камней.

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

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

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

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

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

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

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

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

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