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

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

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

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

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

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

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

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

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

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

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

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

Как определить тип позиции

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

Разбор задач

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

На столе 5 фишек; за ход разрешено убрать 1 или 2, а победит тот, кто уберёт последнюю. Разберём количества фишек, начиная с нуля, чтобы выяснить, какие позиции проигрышные для игрока, которому предстоит ход. Это позволит не гадать о первом ходе, а опереться на повторяющийся порядок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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