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