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