"Информатика", Рудченко Т.А., Семёнов А.Л. / Под ред. Семёнова А.Л.
Стратегия победы — это план ходов, который позволяет выиграть независимо от решений соперника. Чтобы её найти, игру описывают как переходы между позициями: после каждого разрешённого хода меняется состояние игры. Затем рассуждают от конца: определяют позиции, из которых можно выиграть сразу, и постепенно находят те, где победа гарантирована. Такой способ помогает не гадать, а проверять каждый возможный ответ противника.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Игровая позиция — состояние игры в конкретный момент, заданное всеми значимыми данными, например количеством оставшихся предметов. Это описание нужно, чтобы понять, какие действия доступны сейчас и к каким состояниям они приведут. Если на исход влияет, чей ход, это тоже часть позиции.
Ход — разрешённое правилами действие игрока, которое переводит игру из одной позиции в другую. Например, в игре с предметами ходом может быть удаление одного или нескольких предметов. Понятие хода помогает отделить допустимые действия от тех, которые правила запрещают.
Выигрышная позиция — позиция, из которой игрок может обеспечить себе победу при любых ответах соперника. Это не обязательно означает, что партия закончится сразу: иногда нужно сделать ход, после которого соперник окажется в невыгодном состоянии. Такая оценка позволяет выбирать действие не наугад, а с расчётом на продолжение игры.
Стратегия победы — план выбора ходов, который гарантирует победу независимо от действий соперника. Стратегия указывает, как действовать в разных возникающих позициях, а не только на первом ходу. Она нужна, чтобы заранее учитывать возможные ответы противника и не зависеть от его ошибки.
Сначала правила игры записывают так, чтобы ими могли одинаково пользоваться оба игрока. Нужно указать, кто ходит первым, какие действия разрешены и при каком условии партия завершается. Это необходимо потому, что без точного условия окончания нельзя понять, какой ход считается победным, а какие действия вообще следует рассматривать.
Затем игру представляют как цепочку позиций: игрок выбирает разрешённый ход, и состояние меняется. Из одной позиции могут выходить несколько переходов, если доступно несколько действий. Такое представление помогает увидеть не только собственный следующий ход, но и все варианты ответа соперника.
Поиск начинают с позиций, в которых игра заканчивается победой одного из игроков. Они служат опорой, потому что их исход уже известен и дальше анализировать ходы не нужно. От них можно определить позиции, ведущие к завершению: если игрок способен одним ходом оставить соперника без возможности избежать поражения, это подсказывает, как отмечать предыдущие позиции.
Далее рассуждают от конца игры назад. Позиция выигрышна, если из неё есть хотя бы один ход в проигрышную позицию соперника: игрок может выбрать этот ход. Позиция проигрышна, если все разрешённые ходы ведут в выигрышные для соперника позиции, потому что тот сможет ответить подходящим образом при любом выборе. Так постепенно получают классификацию всё более ранних состояний.
Найденное правило проверяют на небольших примерах, где можно выписать все варианты и сравнить их с рассуждением. Это позволяет заметить пропущенный ход или неверно определённый исход. После проверки стратегию записывают как правило выбора действий или алгоритм: он должен подсказывать ход в каждой важной позиции и учитывать возможные ответы соперника.
| Тип позиции | Что можно установить | Как выбирать ход |
|---|---|---|
| Выигрышная | Есть ход в проигрышную позицию соперника. | Выбрать ход, который оставляет сопернику проигрышную позицию. |
| Проигрышная | Все разрешённые ходы ведут в выигрышные позиции соперника. | Гарантирующего победу хода нет; любой допустимый ход позволяет сопернику продолжить выигрышно. |
| Конечная | Игра заканчивается по правилам; исход определён без дальнейших ходов. | Не искать продолжение: определить, кто выиграл или проиграл по условию окончания. |
| Неизвестная | Исход пока не установлен. | Рассмотреть все допустимые ходы и оценить позиции, в которые они ведут. |
Сначала отметь конечные позиции и установи их исход, а затем оценивай позиции, из которых в них можно попасть. Если найдётся ход в проигрышную для соперника позицию, текущая позиция выигрышная; если все ходы ведут в выигрышные для него, она проигрышная. Неизвестные позиции требуют дальнейшего перебора.
Условие. За ход разрешено убрать один или два предмета; забравший последний предмет выигрывает. Определите исход, если остался один предмет. Чтобы ответить, нужно проверить разрешённые действия и понять, завершает ли каждое из них игру.
Ответ. Игрок, которому достался ход при одном оставшемся предмете, выигрывает: он забирает этот предмет. Проверка всех допустимых действий нужна, чтобы не считать незаконный ход возможным.
Условие. За ход можно убрать один или два предмета, а победа достаётся тому, кто забирает последний. Нужно выяснить, может ли первый игрок гарантировать победу при четырёх предметах. Рассмотрим не только первый ход, но и способ отвечать на действия соперника.
Ответ. Да, первый игрок может гарантировать победу: ему нужно убрать один предмет и оставить три. При любом допустимом ходе соперника останется один или два предмета, которые первый игрок сможет забрать.
Условие. За ход разрешено убрать от одного до трёх предметов; последний забранный предмет приносит победу. Требуется найти способ выбора хода, гарантирующий победу при заданном начальном количестве. Стратегию удобно получить, отмечая проигрышные состояния с конца.
Ответ. Если начальное количество не кратно четырём, убери остаток от деления на четыре и затем после каждого хода соперника дополняй число убранных за пару ходов предметов до четырёх. Если количество кратно четырём, при правильной игре соперника гарантировать победу первым ходом нельзя.
Считать ход выигрышным только потому, что он уменьшает число предметов, — ошибка: имеет значение позиция, которая останется сопернику. Её часто допускают, сосредоточившись на самом действии, а не на продолжении игры. Проверь себя: перечисли все допустимые ходы и оцени состояние после каждого из них.
Можно оценить позицию только по собственному следующему ходу и не учесть ответы противника. Тогда план кажется удачным, но соперник может выбрать другой разрешённый вариант и изменить исход. Для проверки выпиши все его возможные ответы и убедись, что стратегия работает при каждом из них.
Нельзя называть позицию выигрышной, не проверив, существует ли ход в проигрышную позицию для соперника. Иногда в позиции есть несколько ходов, но все они оставляют сопернику возможность выиграть. Перед выводом найди хотя бы один подходящий переход, а если его нет — проверь, куда ведут остальные действия.
Ещё одна ошибка — проверять стратегию только на одном примере. Один удачный исход показывает лишь, что план сработал в этой партии, но не доказывает гарантию. Проверь правило на нескольких начальных позициях и перебери разные ответы соперника, особенно те, которые могут нарушить задуманный план.
Для поиска стратегии нужно уметь точно формулировать правила, указывать условие окончания игры и перебирать возможные действия. Эти умения помогают превратить словесное описание в понятную модель, где можно проверить каждый переход. Если правила заданы неточно, классификация позиций тоже может оказаться неверной.
Поиск выигрышных стратегий связан с разработкой алгоритмов: в обоих случаях задают порядок действий и учитывают возможные условия. Он пригодится при анализе игр и решении задач на перебор вариантов, где нужно рассматривать разные пути и сравнивать их исходы. Классификация позиций помогает сократить перебор, если удаётся обнаружить повторяющееся правило.
Что именно считать игровой позицией?
Игровая позиция — это состояние игры в конкретный момент, включая всё, что влияет на возможные ходы и исход. Например, в игре с предметами достаточно знать их оставшееся количество и чей сейчас ход.
Чем выигрышная позиция отличается от выигрышной стратегии?
Выигрышная позиция — состояние, из которого можно обеспечить победу при любых ответах соперника. Выигрышная стратегия — сам план выбора ходов, который помогает попадать в такие позиции и в итоге выигрывать.
Почему стратегию ищут, рассуждая от конца игры?
В конце игры исход часто ясен: например, игрок может забрать последний предмет и победить. Зная такие завершающие позиции, можно определить, какие ходы приводят к ним, а затем шаг за шагом продвигаться к началу.
Как доказать, что стратегия гарантирует победу?
Нужно проверить все разрешённые ходы соперника, а не только один удобный ответ. На каждом своём ходу стратегия должна предлагать действие, которое снова оставляет сопернику проигрышную позицию.
Можно ли найти стратегию, если ходов очень много?
Да, если удаётся описать позиции правилом или алгоритмом, а не перебирать каждую партию вручную. Для этого ищут повторяющиеся закономерности и проверяют их на конечных случаях; сложные игры могут потребовать более трудного анализа.
Проект "Стратегия победы"
