Игра камешки

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

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

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

Ответ: куча из 6 камешков выигрышная для первого игрока; ему нужно взять 2 камешка. Если он возьмёт, например, 3, останется 3, и соперник сможет оставить ему 0.

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

1. Делим 17 на 4: остаток равен 1.
2. Первый игрок берёт 1 камешек и оставляет 16. Это проигрышная позиция для соперника.
3. Если соперник берёт 1, 2 или 3 камешка, первый игрок берёт соответственно 3, 2 или 1. За два хода уйдут 4 камешка, и сопернику снова останется количество, кратное четырём.

Ответ: первым ходом нужно взять 1 камешек. Затем следует дополнять ход соперника до четырёх: если тот взял n камешков, взять 4 − n.

Задача 3. Из кучи можно брать от одного до k камешков. Как найти проигрышные позиции и первый выигрышный ход? Для такого правила нельзя автоматически использовать кратность четырём: закономерность зависит от разрешённых ходов и условия окончания игры.

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

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

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

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

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

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

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

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

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

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

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