"Информатика", Поляков К.Ю., Еремин Е.А.
Игровая стратегия — способ выбирать ходы так, чтобы добиться победы независимо от действий соперника. Для её поиска игру описывают как последовательность позиций: каждое разрешённое действие переводит её в новое состояние. Затем выясняют, из каких позиций можно выиграть, а из каких при правильной игре победит соперник. Удобнее всего начинать анализ с конца игры и двигаться к началу.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Игровая позиция — состояние игры в конкретный момент, задаваемое значениями всех существенных параметров, например количеством оставшихся предметов. В игре с двумя кучками нужно указать число предметов в каждой, а не только их общую сумму. Такое описание позволяет сравнивать состояния и рассуждать о том, какие из них выгодны игроку.
Ход — разрешённое правилами действие игрока, переводящее игру из одной позиции в другую. Например, если за ход можно взять один или два предмета, нельзя взять три, даже если это кажется выгодным. Понятие хода помогает точно задать все переходы, которые нужно проверить при поиске стратегии.
Выигрышная стратегия — способ выбирать ходы, который обеспечивает победу при любых ответах соперника. Это не просто удачное начало: план должен оставаться рабочим на каждом этапе игры. Такое определение нужно, чтобы отличать доказанную гарантию победы от надежды на ошибку противника.
Выигрышная и проигрышная позиции — позиции, из которых при правильной игре можно соответственно добиться победы или избежать её. Оценка зависит от того, чей сейчас ход и как сформулировано условие победы. Эти понятия позволяют отмечать позиции, из которых игрок может навязать сопернику невыгодное продолжение.
Игру представляют как последовательность позиций и ходов. Каждая позиция описывает состояние, а правила перечисляют допустимые переходы из неё: например, из состояния с пятью предметами можно перейти к состоянию с четырьмя или тремя. Это представление важно, потому что стратегия выбирает не абстрактно «хорошее действие», а переход в конкретное состояние. Если не учесть хотя бы одно разрешённое действие, можно ошибочно решить, что соперник лишён ответа.
Для анализа нужны конечные позиции — состояния, в которых ходов больше нет или игра завершается по другому правилу. В них исход можно определить непосредственно: например, игрок, забравший последний предмет, выигрывает, а следующий игрок уже не может ходить. Сначала выясняют, кто считается победителем в каждом таком случае, потому что именно условие окончания задаёт оценку позиции. Без этого нельзя правильно рассуждать о ходах, которые ведут к завершению.
Позицию называют выигрышной, если существует хотя бы один ход в проигрышную позицию соперника. Игроку достаточно найти такой переход, потому что после него соперник окажется в состоянии, где любой его ответ будет невыгоден. Слово «существует» здесь принципиально: не каждый доступный ход обязан помогать, но хотя бы один должен обеспечивать нужное продолжение. Поэтому при проверке позиции ищут конкретный ход, а не просто оценивают общее число вариантов.
Позиция проигрышная, если все разрешённые ходы ведут в выигрышные позиции соперника. Это значит, что при правильной игре противник сможет ответить на любой выбор так, чтобы сохранить преимущество. Если ходов нет, результат определяется условием окончания: в игре, где побеждает взявший последний предмет, игрок без хода обычно проигрывает. Проверка всех возможных переходов необходима, иначе можно пропустить ответ, меняющий исход.
Чтобы анализировать игру от конца к началу, сначала отмечают конечные позиции, затем рассматривают те, из которых в них можно попасть. Если из позиции есть ход в уже известную проигрышную позицию соперника, её отмечают как выигрышную; если все ходы ведут в выигрышные для соперника, позиция проигрышная. Дальше повторяют это рассуждение для предыдущих состояний. Такой порядок работает потому, что исход более раннего хода зависит от оценки позиций, в которые он может привести.
| Тип позиции | Что верно о доступных ходах | Что может обеспечить игрок |
|---|---|---|
| Конечная позиция | Продолжить игру нельзя либо выполнено условие её завершения. | Исход задаётся правилами; нового хода для изменения позиции нет. |
| Выигрышная позиция | Есть хотя бы один ход в проигрышную позицию соперника. | Можно выбрать ход, после которого сопернику трудно избежать поражения. |
| Проигрышная позиция | Все разрешённые ходы ведут в выигрышные позиции соперника. | При правильной игре соперника нельзя гарантировать победу. |
Пользуйся таблицей после того, как перечислишь все разрешённые ходы и установишь правило окончания игры. Для выигрышной позиции достаточно найти один подходящий переход, а для проигрышной нужно проверить каждый переход. Конечную позицию оценивай отдельно по условию победы: само отсутствие ходов не всегда означает один и тот же результат.
За ход берут один или два предмета, а выигрывает тот, кто забирает последний. Нужно оценить позиции по числу оставшихся предметов и начать с нуля: игрок, которому нечего брать, уже не может сделать последний ход. Для каждого следующего числа проверим, можно ли одним ходом оставить сопернику проигрышное состояние.
Следовательно, первый игрок выигрывает, если выберет правильный ход. Он должен взять два предмета, чтобы оставить три, а затем отвечать так, чтобы после его хода сопернику снова оставалось три предмета или соответствующее проигрышное состояние. Ответ: при правильной игре победит первый игрок, начав с взятия двух предметов.
Теперь разрешено брать 1, 2 или 3 предмета, а последний предмет приносит победу. Ищем проигрышные количества снизу: 0 проигрышно, а 1, 2 и 3 выигрышны, потому что можно забрать всё. Состояние с 4 предметами тоже проигрышно: любой разрешённый ход оставляет сопернику от 1 до 3 предметов, то есть выигрышную позицию.
Здесь обнаруживается повторяющийся шаг в четыре предмета: проигрышные позиции — 0, 4, 8, 12 и далее. Поэтому при начальных 12 предметах первый игрок не может выполнить требование задачи — сделать проигрышную позицию для соперника после первого хода. Ответ: выигрышной стратегии у первого игрока нет; при правильной игре победит второй.
За ход можно убрать любое положительное количество предметов, но только из одной кучки. Это вариант игры ним: чтобы определить выигрышный ход, размеры кучек сравнивают побитовой операцией исключающее ИЛИ, обозначаемой XOR. Если результат не равен нулю, можно изменить одну кучку так, чтобы результат стал нулевым; нулевая ним-сумма соответствует проигрышной позиции при правильной игре.
Первый игрок должен взять три предмета из кучки, где было 7, оставив кучки 4 и 4. После каждого хода соперника нужно выбирать ответ, который снова делает ним-сумму нулевой; при любом изменении одной кучки такой ответ существует, пока игра не закончится. Ответ: у первого игрока есть выигрышная стратегия — сначала оставить две равные кучки, а затем возвращать игру к позиции с нулевой ним-суммой.
Ошибка — считать позицию выигрышной только потому, что из неё доступно много ходов. Число вариантов само по себе ничего не говорит: даже единственный ход может вести в проигрышное состояние, а из десятка вариантов достаточно одного подходящего. Проверяй, есть ли хотя бы один ход именно в проигрышную позицию соперника.
Ошибка — оценивать ход только по количеству взятых предметов. Один и тот же размер хода может быть хорошим или плохим в зависимости от того, сколько останется и какие действия разрешены дальше. Перед выбором выпиши позицию после хода и проверь её тип по дальнейшим возможностям.
Ошибка — объявлять выигрышным любой ход, который не завершает игру. То, что игра продолжается, ещё не означает, что игрок сохранил преимущество: соперник может получить удобную позицию и перехватить инициативу. Проверь, может ли соперник ответить ходом в проигрышную для тебя позицию.
Ошибка — рассматривать только один предполагаемый ответ соперника. Игрок не обязан отвечать так, как удобно нам, и может выбрать любой разрешённый ход. Чтобы проверить стратегию, перечисли все ответы соперника и убедись, что для каждого из них есть подходящее продолжение; если хотя бы один ответ ломает план, гарантии нет.
Для анализа игры нужно внимательно читать правила, перечислять допустимые действия и описывать состояние набором параметров. Это связано с представлением задач в информатике: точное описание помогает не пропустить возможный вариант. Перебор продолжений можно изобразить деревом игры, где вершины — позиции, а ветви — ходы. Похожие рассуждения применяют в рекурсивных алгоритмах, которые повторно решают меньшие подзадачи.
Стратегический анализ пригодится при создании игровых программ: программа должна оценивать возможные ответы, а не только выбирать ближайший ход. Перебрав варианты и классифицировав позиции, можно проверить, существует ли стратегия, гарантирующая победу. Такой подход также помогает понять, почему алгоритм выигрывает или проигрывает при заданных правилах.
Что именно называют позицией в игре?
Позиция — это состояние игры в определённый момент, описанное всеми важными параметрами. Например, в игре с предметами достаточно указать, сколько их осталось; при нескольких кучках нужно указать количество предметов в каждой.
Чем выигрышная стратегия отличается от удачного первого хода?
Удачный первый ход сам по себе ещё не гарантирует победу: соперник может ответить так, что преимущество перейдёт к нему. Выигрышная стратегия задаёт дальнейшие решения и обеспечивает победу при любом разрешённом ответе соперника.
Почему для гарантированной победы нужно учитывать все ответы соперника?
Соперник выбирает ответ, который выгоден ему, а не нам. Если хотя бы один его разрешённый ход разрушает план, стратегия не гарантирует победу.
Как определить, является ли позиция выигрышной или проигрышной?
Позиция выигрышная, если у игрока есть хотя бы один ход в проигрышную позицию для соперника. Она проигрышная, если все разрешённые ходы переводят игру в выигрышные позиции соперника.
Зачем анализировать игру, начиная с конечных позиций?
У конечных позиций исход уже известен по условию победы, поэтому их можно сразу оценить. Затем по правилам игры определяют, какие предыдущие позиции позволяют попасть в уже классифицированные.
§ 18. Игровые стратегии
