"Информатика (базовый уровень)", Гейн А.Г., Гейн А.А.
Стратегия в игре — правило, которое подсказывает игроку ход при каждом возможном развитии событий. Чтобы найти её, игру представляют как цепочку позиций и переходов между ними, а затем начинают анализ с конца: там результат часто уже известен. Позиции делят на выигрышные и проигрышные. Если из позиции можно перевести соперника в проигрышную, она выигрышная; если любой ход отдаёт сопернику выигрышную позицию, она проигрышная. Так удаётся не угадывать ходы, а обосновать их.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Игровая позиция — состояние игры, задаваемое всеми данными, от которых зависят возможные дальнейшие ходы. Например, в игре с одной кучкой достаточно знать число фишек, а в игре с двумя — число фишек в каждой кучке. Это понятие нужно, чтобы точно описать, где именно находится игра и какие действия доступны.
Ход — допустимое действие игрока, переводящее игру из одной позиции в другую. Важно учитывать именно разрешённые правилами действия: если можно взять только 1 или 2 фишки, взять 3 нельзя. Описание ходов помогает перечислить все варианты продолжения и ничего не пропустить при анализе.
Выигрышная позиция — позиция, из которой игрок может обеспечить свою победу при правильной игре. Для этого достаточно найти хотя бы один ход в позицию, проигрышную для соперника. Понятие позволяет отличить гарантированную возможность выиграть от хода, который лишь кажется удачным.
Проигрышная позиция — позиция, из которой при правильной игре соперника победить невозможно. Это означает, что любой разрешённый ход переводит игру в выигрышную позицию соперника. Такое определение помогает проверять не отдельный вариант, а все возможные действия.
Игру представляют как последовательность позиций: исходная, полученная после первого хода, затем следующая и так далее, пока не наступит конец. Каждый ход — переход между двумя позициями, поэтому такую игру можно анализировать по возможным продолжениям. Представление полезно тем, что переводит разговор о «хорошем ходе» в проверку конкретных вариантов.
Анализ начинают с конечных позиций, потому что там уже понятно, кто выиграл или проиграл согласно правилам. Если не знать результат конца игры, нельзя уверенно определить, куда ведут более ранние ходы. Установив конечный результат, его можно переносить на позиции, из которых до конца остался один ход, а затем — ещё дальше.
Позиция выигрышная, если из неё существует ход в проигрышную позицию для соперника. Игрок выбирает именно этот ход, а сопернику приходится продолжать из состояния, где все его действия ведут к выгодной для первого игрока позиции. Поэтому для признания позиции выигрышной не требуется, чтобы хорошими были все доступные ходы: достаточно одного надёжного.
Позиция проигрышная, если любой допустимый ход переводит игру в выигрышную позицию соперника. Проверять приходится все варианты, поскольку даже один ход в проигрышную для соперника позицию изменил бы классификацию. Если ходов нет, результат определяется условием игры: например, при правиле «взял последнюю фишку — выиграл» игрок без хода проигрывает.
Когда позиции размечены, из этого получается стратегия: после каждого хода соперника снова выбирают ход в проигрышную для него позицию. Такой способ не зависит от того, какой именно разрешённый вариант выбрал соперник. Стратегия считается обоснованной, если она указывает ответ для каждого возможного продолжения и приводит к конечному результату, выгодному игроку.
| Тип позиции | Признак | Действие игрока | Результат правильной игры |
|---|---|---|---|
| Конечная позиция | Игра завершена по правилам | Ход не выполняется | Результат задаётся условием окончания игры |
| Выигрышная позиция | Есть ход в проигрышную позицию соперника | Выбрать такой ход | Победу можно обеспечить |
| Проигрышная позиция | Все допустимые ходы ведут в выигрышные позиции соперника | Выбрать любой разрешённый ход | Соперник может обеспечить победу |
| Ход из выигрышной позиции | Найдена проигрышная позиция для соперника | Перевести игру туда | Сохранить возможность победы |
| Ход из проигрышной позиции | Любое продолжение отдаёт сопернику выигрышную позицию | Выбрать допустимый ход | Сам по себе ход не гарантирует спасения |
Сначала выясните, к какому типу относится текущая позиция, и только потом выбирайте действие. Для выигрышной позиции ищите хотя бы один ход в проигрышную; для проигрышной проверяйте все варианты. В конечной позиции ориентируйтесь на точную формулировку правил.
В кучке 17 фишек, игроки берут по 1 или 2, а взявший последнюю фишку выигрывает. Нужно найти стратегию первого игрока. Удобно классифицировать количества с конца: при 0 фишек игра завершена, а игрок, которому предстоит ходить, уже не может выиграть.
При 1 или 2 фишках текущий игрок выигрывает, забирая всё. При 3 фишках любой ход оставляет сопернику 1 или 2, поэтому 3 — проигрышная позиция.
По тому же правилу 4 и 5 — выигрышные: можно оставить сопернику 3. При 6 фишках любой ход оставляет 4 или 5, значит, 6 — проигрышная.
Получается закономерность: проигрышны количества, кратные 3. Из 17 нужно взять 2 фишки и оставить 15; затем после хода соперника взять столько, чтобы два хода вместе составили 3.
Например, если соперник берёт 1, нужно взять 2, а если берёт 2 — взять 1. Так первый игрок каждый раз оставляет сопернику количество, кратное 3, и в итоге забирает последнюю фишку. Ответ: первый игрок выигрывает, начиная с хода на 2 фишки.
В кучках 7 и 11 фишек; за ход разрешено уменьшить только одну кучку на любое положительное число. Последняя взятая фишка приносит победу. Требуется найти выигрышный ход первого игрока и понять, почему выбранное состояние удобно удерживать.
Если кучки одинаковы, например (7; 7), ход из одной кучки нарушит равенство. Второй игрок сможет взять столько же фишек из другой кучки и восстановить равенство, пока первый не оставит пустую кучку.
Значит, (7; 7) — проигрышная позиция для того, кому предстоит ходить: после любого его действия соперник может вернуть кучки к равенству. Из (7; 11) первый игрок уменьшает большую кучку на 4.
Получается (7; 7), и дальше первый игрок отвечает на уменьшение одной кучки таким же уменьшением другой. Кучки остаются равными после его ответов, а последнюю фишку берёт он.
Ответ: выигрышный ход — забрать 4 фишки из кучки с 11 фишками. Дальше нужно копировать ход соперника в другой кучке, чтобы сохранять симметрию. Именно возможность ответить на любой ход делает это стратегией, а не единичным удачным действием.
В кучке 25 фишек, за ход можно взять от 1 до 3, но игрок, забравший последнюю, проигрывает. Теперь нужно учитывать не только возможные переходы, но и то, кто получает поражение при завершении игры. Поэтому привычное правило для задачи, где последняя фишка приносит победу, здесь применять нельзя.
Если осталось от 1 до 3 фишек, игрок вынужден забрать последнюю и проиграть. При 4 фишках он берёт 1 и оставляет сопернику 3, поэтому 4 — выигрышная позиция.
При 5 и 6 фишках тоже можно оставить сопернику 3 или 2. При 7 любой ход оставляет 4, 5 или 6 — выигрышные позиции, значит, 7 проигрышно.
Дальше повторяется шаг 4: проигрышны 3, 7, 11, 15, 19, 23 и далее, то есть числа вида 4k − 1. Поскольку 25 — выигрышная позиция, первый игрок берёт 2 и оставляет 23.
После этого первый игрок отвечает на ход соперника так, чтобы за два хода было взято 4 фишки. Если соперник взял k, ответ — 4 − k; так сопернику последовательно остаются 19, 15, 11, 7 и 3 фишки.
Ответ: при правильной игре выигрывает первый игрок. Он начинает с 2 фишек, а затем дополняет каждый ход соперника до 4; в конце сопернику достаются 3 фишки и он вынужден взять последнюю, проиграв.
Считать выигрышной любую позицию, из которой можно сделать ход, недостаточно: нужно проверить, куда этот ход приводит. Ошибка возникает, когда игрок оценивает только собственное действие и забывает о ходе соперника. Проверьте себя вопросом: оставляет ли выбранный ход соперника в позиции, где тот может обеспечить победу?
Начинать рассуждение с первого хода и перебирать варианты без классификации конечных позиций обычно неудобно. Вариантов становится много, а повторяющуюся закономерность легко не заметить. Сначала определите результат в конце игры, затем двигайтесь назад и проверяйте, какие позиции перед ним выигрышные или проигрышные.
Условия «взял последнюю фишку — выиграл» и «взял последнюю фишку — проиграл» дают разные результаты. Путаница появляется, если переносить готовое решение похожей задачи, не перечитав правило окончания. Перед расчётами сформулируйте, кто проигрывает при последнем ходе, и проверьте на этом самые простые позиции.
Один удачный ответ сопернику ещё не является стратегией: соперник мог выбрать другой допустимый ход. Такую ошибку допускают, рассматривая только один пример продолжения. Проверка простая: для каждого возможного действия соперника должно быть указано, как ответить и почему ответ сохраняет выигрышную позицию.
Для анализа игр полезны понятия алгоритма, состояния системы и ветвления: они помогают описывать позиции и варианты ходов. Рекурсия связана с повторяющимися обращениями к позициям, а математическая индукция — с обоснованием закономерности для всех этапов игры. Остатки от деления часто позволяют кратко записать проигрышные количества, например как числа определённого остатка по модулю 3 или 4.
Такие рассуждения применяются при создании алгоритмов перебора и рекурсивных программ, а также программ, которые выбирают действия в играх. Связь с математикой проявляется в поиске закономерностей последовательностей и их доказательстве. Одного наблюдения за несколькими примерами мало: необходимо объяснить, почему правило работает на каждом шаге.
Чем выигрышная позиция отличается от просто выгодной?
Выигрышная позиция гарантирует победу при правильной игре, даже если соперник выбирает любой допустимый ответ. Просто выгодная позиция может выглядеть удобной, но не исключать проигрышного продолжения.
Почему стратегию удобнее строить с конца игры?
У конечных позиций результат уже известен: игра либо закончилась победой одного из игроков, либо последний ход определён правилами. От них можно последовательно установить, какие позиции перед концом дают победу, а какие — поражение.
Как доказать, что позиция проигрышная?
Нужно показать, что каждый допустимый ход из неё ведёт в выигрышную позицию соперника. Если таких ходов нет, учитывают правило окончания игры: например, позиция без ходов может быть проигрышной для игрока, которому предстоит ходить.
Что делать, если из одной позиции возможны несколько ходов?
Проверить каждый допустимый ход, а не только самый очевидный. Позиция выигрышная, если хотя бы один ход ведёт в проигрышную для соперника; она проигрышная, только если все ходы ведут в выигрышные для него позиции.
Как изменить стратегию, если последний ход считается проигрышным?
Нужно заново определить конечные позиции: теперь игрок, который забирает последнюю фишку, проигрывает. Затем позиции классифицируют с конца по тем же правилам, но с учётом изменённого условия окончания игры.
§ 58. Построение стратегии
