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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Пять фишек, брать можно одну или две

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

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

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

Восемь фишек, брать можно одну или две

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

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

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

Двенадцать фишек, брать можно одну, две или три

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

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

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

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

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

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

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

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

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

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

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

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