Равновесные выигрышные стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

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

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

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

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

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

Ответ: при 10 предметах первый игрок начинает с хода «убрать 2». Затем он дополняет ход соперника до 4, сохраняя у соперника количество, кратное 4. Для другого начального количества нужно оставить ближайшее меньшее кратное 4, если оно достижимо одним ходом.

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

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

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

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

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

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

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

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

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

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

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

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

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