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