Выигрышная стратегия

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

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

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

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

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

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

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

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

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

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

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

Признаки выигрышных и проигрышных позиций

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

Разбор задач

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

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

Ответ: при правильной игре побеждает первый игрок; его первый ход — взять 2 предмета. Далее он должен возвращать сопернику количество, кратное трём.

Задача 2. На столе 12 предметов, за ход разрешено взять 1, 2 или 3. Требуется выяснить, есть ли выигрышная стратегия у первого игрока. Здесь проигрышные количества повторяются через четыре: из 4, 8 или 12 любой ход оставляет сопернику соответственно 1–3, 5–7 или 9–11 предметов. Эти меньшие количества являются выигрышными для того, кто ходит следующим.

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

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

Задача 3. На доске записано число 1. За ход можно прибавить 1 или умножить число на 2; побеждает тот, кто первым получит 20. Нужно определить, может ли первый гарантировать победу. Рассуждаем с конца: 19 и 10 выигрышны, потому что из них можно получить 20 одним ходом. Положение 18 проигрышно: единственный ход, не превышающий цель, ведёт к 19.

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

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

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

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

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

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

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

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

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

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

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