Выигрышные и проигрышные стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

1. Одна фишка

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

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

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

2. Положения от одной до восьми фишек

Теперь проверим количества от 1 до 8. Положение с 0 фишек проигрышно для ходящего, поскольку он не может сделать ход; число 1 выигрышно, так как можно убрать последнюю фишку. Дальше для каждого количества смотрим, можно ли оставить сопернику уже известное проигрышное число.

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

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

3. Начало с 17 фишек

Игроки убирают за ход 1, 2 или 4 фишки, а проигрывает тот, кому нечего убрать. Чтобы оценить число 17, строим цепочку проигрышных положений от 0, проверяя каждый ход назад. Получаются 0, 5, 8, 11, 14 и 17; из каждого такого количества любой разрешённый ход оставляет сопернику выигрышное положение.

1. Проверим 17: после снятия 1, 2 или 4 останется 16, 15 или 13.
2. Все три числа выигрышны для ходящего: из 16 можно оставить 14, из 15 — 14, а из 13 — 11.
3. Значит, 17 проигрышно для первого игрока: любой его ход даёт сопернику возможность перейти к проигрышному для первого числу.
4. Если первый игрок ошибётся и оставит не проигрышное число, второй может вернуть игру к 14, затем к 11, 8, 5 или 0. Для этого он выбирает снятие, которое оставляет ближайшее меньшее число из этой цепочки.

Ответ: при старте с 17 первый игрок не может гарантировать победу, если соперник играет правильно. Он может победить только при ошибке соперника; стратегия второго игрока — после каждого хода возвращать количество фишек к следующему числу из цепочки 14, 11, 8, 5, 0.

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

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

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

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

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

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

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

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

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

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