Выигрышные стратегии в игре камешки

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

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

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

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

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

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

Сначала формализуют правила игры: записывают начальное число камешков, возможные ходы, условие победы и имя первого игрока. Это нужно потому, что без таких сведений нельзя однозначно решить, какой ход разрешён и когда партия заканчивается. Например, возможность брать 1 или 2 камешка даёт другой набор вариантов, чем возможность брать 1, 2 или 3.

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

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

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

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

Позиции в игре, где за ход можно взять 1 или 2 камешка

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

Разбор задач

Задача 1. По правилам можно брать 1 или 2 камешка, последний взявший побеждает. Определить, выиграет ли первый игрок при 7 камешках, и назвать его первый ход.

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

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

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

Ответ: первый игрок может выиграть; первым ходом ему нужно взять 1 камешек.

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

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

2. После этого игрок следит за ходом соперника. Если соперник взял 1, первый берёт 2; если соперник взял 2, первый берёт 1.

3. Каждая пара ходов в сумме убирает 3 камешка. Поэтому после ответа первого игрока сопернику снова остаётся число, кратное 3: 6, затем 3 и, наконец, 0.

Ответ: первым ходом взять 1, а затем дополнять ход соперника до 3. Так последний камешек возьмёт первый игрок.

Задача 3. За ход можно взять 1, 2 или 3 камешка, последний взявший побеждает. Определить тип позиции при 14 камешках и стратегию первого игрока.

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

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

3. Так как 14 не кратно 4, первый игрок может оставить сопернику 12. Для этого нужно взять 2 камешка, а затем после каждого хода соперника дополнять его ход до 4.

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

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

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

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

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

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

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

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

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

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

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