§ 2. Стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Куча из 7 камней: за ход убрать 1 или 2

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

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

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

Куча из 12 камней: за ход убрать 1, 2 или 3

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

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

Ответ: выигрышная стратегия первого игрока — убрать 3 камня. Затем нужно дополнять ход соперника до 4: если он убрал 1, убрать 3; если 2 — убрать 2; если 3 — убрать 1.

Две кучки по 3 камня

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

1. В начале позиция (3, 3) симметрична. Первый игрок уменьшает одну кучку, и кучки становятся разными, например (1, 3).
2. Второй игрок может убрать камни только из одной кучки. Первый игрок отвечает, убирая из другой кучки столько же, сколько соперник убрал из первой.
3. После такого ответа кучки снова равны. Этот приём можно повторять после каждого хода соперника, пока он не оставит одну кучку пустой.
4. Когда соперник опустошит одну кучку, первый игрок убирает все камни из оставшейся. Он забирает последний камень и выигрывает.

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

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

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

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

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

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

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

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

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

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