Игровые стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

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

1. Сначала найдём позиции, близкие к концу. Если осталась 1 фишка, игрок забирает её и выигрывает; если осталось 2, он тоже может выиграть, взяв обе.

2. Если на столе 3 фишки, игрок может взять 1 и оставить сопернику 2. При 4 фишках можно взять 2 и оставить 2. Значит, 3 и 4 — позиции, из которых ходящий может выиграть.

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

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

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

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

1. Начинаем с конца. Если осталась 1, 2 или 3 фишки, игрок может забрать их все и выиграть. Если осталось 4, любой разрешённый ход оставит сопернику от 1 до 3, поэтому 4 — проигрышное количество.

2. Теперь отступаем назад: при 5, 6 или 7 фишках можно оставить сопернику 4, взяв соответственно 1, 2 или 3. Значит, эти количества позволяют ходящему передать сопернику проигрышную позицию.

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

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

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

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

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

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

2. Если осталось 2, 3 или 4 фишки, можно оставить сопернику одну, взяв соответственно 1, 2 или 3. Значит, эти позиции выигрышные для ходящего.

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

4. Продолжая разбор с конца, получаем проигрышные количества 1, 5, 9 и 13: из каждого следующего такого количества можно взять от 1 до 3 и оставить сопернику одно из выгодных количеств.

5. При 15 фишках первый игрок может взять 2 и оставить сопернику 13. Затем он отвечает так, чтобы вместе с ходом соперника забирать 4 фишки: на 1 отвечает 3, на 2 — 2, на 3 — 1.

Ответ: первый игрок может выиграть при правильной игре. Нужно первым взять 2 фишки, а затем каждый раз дополнять ход соперника до 4, чтобы передавать ему позиции с 13, 9, 5 и 1 фишкой.

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

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

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

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

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

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

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

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

• Сначала выясни правила ходов и условие окончания игры.

• Выигрышная позиция позволяет выбрать ход к проигрышной позиции соперника.

• Из проигрышной позиции любой разрешённый ход ведёт к выигрышной для соперника.

• В играх с конечным числом ходов позиции можно разбирать с конца.

• Стратегия должна учитывать возможные ответы соперника.

• Изменение правил может изменить выигрышную стратегию.