Выигрышные стратегии. Продолжение

Определения и обозначения

Игра — занятие, в котором участники делают ходы по заранее заданным правилам. В правилах указано, что можно делать и когда игра заканчивается. Это определение нужно, чтобы отличать допустимый ход от запрещённого и понимать, что считается победой.

Позиция — состояние игры в определённый момент, например количество оставшихся предметов перед ходом. При одном и том же числе предметов и одинаковых правилах игроки оказываются в одинаковой позиции. Понятие позиции помогает сравнивать разные партии и замечать, какие состояния повторяются.

Выигрышная стратегия — план ходов, который позволяет игроку победить, как бы ни отвечал соперник. Такой план не обязан заранее перечислять все ходы: он может задавать правило выбора ответа на каждый ход соперника. Это понятие нужно, чтобы отличать продуманную игру от удачной случайности.

Выигрышная позиция даёт игроку, которому предстоит ход, способ гарантировать победу при правильной игре обоих участников. Проигрышная позиция такого способа не даёт, если соперник не ошибается. Эти названия помогают рассуждать о результате, не называя позиции «хорошими» только потому, что сейчас в них много предметов.

Ход — одно разрешённое действие игрока. Например, в игре с кучей предметов ходом может быть взятие одного или двух предметов. Нужно точно понимать границы хода: именно они определяют, какие позиции достижимы и можно ли построить план победы.

Как это устроено

В игре сначала определяют правила: кто ходит первым, какие действия разрешены и кто побеждает в конце. Без этого нельзя оценить позицию, потому что одно и то же число предметов может вести к разному результату при разных правилах. Например, условие «выигрывает взявший последний» отличается от условия «выигрывает тот, кому не осталось хода». Поэтому перед поиском плана нужно проговорить правила своими словами.

Затем выясняют, что именно меняется после каждого хода. Если игрок забирает предметы из одной кучи, позицию удобно описывать числом оставшихся предметов. Если меняется несколько куч или есть дополнительные действия, для описания может понадобиться несколько чисел. Такое описание важно, потому что стратегию строят не по внешнему виду игры, а по тому, как один ход переводит позицию в другую.

Поиск часто начинают с конца игры. В конечной позиции уже понятно, кто победил, поэтому можно шаг за шагом смотреть на предыдущие позиции: есть ли из каждой ход, который ведёт к победе? Если такой ход есть, позиция может быть выигрышной; если каждый допустимый ход отдаёт сопернику выигрышную позицию, она проигрышная. Рассуждение с конца полезно потому, что в начале партии вариантов много, а рядом с завершением результат каждого хода виден яснее.

Рассмотрим правило: за ход можно взять один или два предмета, а победит тот, кто заберёт последний. Если перед ходом остался один или два предмета, игрок может забрать их все и выиграть. Если осталось три, взять можно только один или два, и сопернику достанется соответственно два или один: он заберёт остаток. Значит, три предмета образуют проигрышную позицию для того, кому предстоит ход.

Рассуждение можно продолжить назад. При четырёх предметах игрок может взять один и оставить сопернику три, поэтому четыре — выигрышная позиция; при пяти можно взять два и тоже оставить три. При шести любой ход оставляет четыре или пять, то есть выгодное положение сопернику, поэтому шесть — проигрышная позиция. Так видна повторяющаяся закономерность: проигрышными оказываются количества, кратные трём.

Когда закономерность найдена, нужно превратить её в правило для каждого хода. В игре с кучей из 15 предметов первый игрок не может оставить сопернику количество, не кратное трём: он может взять только один или два. Второй игрок после хода соперника берёт столько, чтобы общее количество убранных ими предметов стало равным трём. Тогда после их пары ходов количество на столе уменьшается на три, и соперник снова получает кратное трём число.

Стратегия работает не потому, что второй игрок угадывает намерения первого, а потому, что у него есть подходящий ответ на оба разрешённых хода. Если первый взял один предмет, второй берёт два; если первый взял два, второй берёт один. При повторении этого правила второй игрок забирает последний предмет. В другой игре закономерность может быть иной, поэтому проверяют не только примеры, но и все допустимые варианты хода.

Позиции в игре с предметами

Таблица показывает, как рассуждать для игры, где за ход берут один или два предмета, а победитель забирает последний. В ней проигрышными отмечены позиции для игрока, которому предстоит ход.

Сначала найдите строки, где позиция проигрышная, и проверьте, почему ни один ход не помогает игроку. Затем посмотрите, какие ходы из соседних выигрышных позиций оставляют сопернику проигрышное количество. Таблица подсказывает закономерность, но она верна только для указанных правил игры.

Разбор задач

Задача. На столе лежат 15 фишек. Два игрока по очереди забирают одну или две фишки. Побеждает тот, кто забрал последнюю. Может ли один из игроков гарантировать победу, и как ему действовать? Считаем, что оба знают правила и стараются играть правильно. Нужно не угадать, что сделает соперник, а найти ответ для каждого его возможного хода.

1. Сначала проверим небольшие количества. Если осталась одна или две фишки, игрок на ходу забирает их и выигрывает. Если осталось три, он вынужден взять одну или две, после чего соперник заберёт оставшееся. Значит, число 3 проигрышно для того, кому нужно ходить.

2. Посмотрим, какие количества позволяют оставить сопернику три фишки. Из четырёх можно взять одну, а из пяти — две. Поэтому четыре и пять выигрышны: есть ход, после которого соперник оказывается в проигрышной позиции.

3. Проверим шесть. Если взять одну, останется пять; если взять две — четыре. И пять, и четыре дают сопернику возможность оставить три фишки уже следующему игроку. Поэтому шесть проигрышно для игрока на ходу.

4. Продолжая проверку, получаем проигрышные количества 3, 6, 9, 12 и 15. Они отличаются друг от друга на три, потому что каждый раз можно сгруппировать ходы по три предмета: один участник берёт один, другой — два, или наоборот.

5. В начале на столе 15 фишек, и первым ходит игрок, которому предстоит сделать ход из проигрышной позиции. Он берёт одну или две, а второй игрок отвечает так, чтобы за два хода вместе ушло три фишки. Если первый взял одну, второй берёт две; если первый взял две, второй берёт одну.

6. После каждой пары ходов на столе будет оставаться 12, затем 9, 6 и 3 фишки. Когда останутся три, первый игрок вынужден взять одну или две, а второй заберёт последнюю или последние две. Значит, второй игрок может гарантировать победу, если каждый раз правильно дополняет ход соперника до трёх.

Ответ: при правильной игре второй игрок гарантирует победу. Его правило — после хода первого забирать столько фишек, чтобы оба игрока вместе убирали три. Такой вывод зависит от исходных правил: если разрешить брать три фишки или изменить условие победы, стратегию придётся искать заново.

Типичные ошибки

• Ошибка — сразу объявить победителем того, кто ходит первым. Так думают, потому что первый игрок начинает и кажется, что он управляет игрой. Но решает не порядок хода сам по себе, а позиция и допустимые действия. Проверь себя: проследи, может ли соперник отвечать на каждый ход и в итоге оставить тебе проигрышное количество.

• Ошибка — запомнить правило про числа, кратные трём, и применять его к любой игре. Оно получено для конкретных условий: брать можно только одну или две фишки, а последний предмет приносит победу. Если правила другие, меняются и позиции. Проверь себя: выпиши разрешённые ходы и заново разбери несколько маленьких количеств с конца.

• Ошибка — считать один удачный ход доказательством стратегии. Ход может сработать против одного ответа соперника, но проиграть против другого. Это часто происходит, когда рассматривают только самый удобный вариант. Проверь себя: перебери каждый разрешённый ответ соперника и найди для него следующий ход по своему плану.

• Ошибка — не уточнить условие окончания игры. Можно перепутать победу того, кто забрал последний предмет, с победой того, кому больше нечего брать. Такое чтение меняет результат даже в простом примере. Проверь себя: перед решением отдельно назови последний ход и игрока, которому правила присуждают победу.

Связь с другими темами

Поиск стратегии связан с алгоритмами: стратегия задаёт последовательность действий или правило, по которому выбирают следующий ход. Как и в алгоритме, важно соблюдать точные условия, иначе решение может не сработать. Ещё эта тема связана с перебором вариантов: чтобы найти закономерность, рассматривают возможные ходы и их последствия. Рассуждение с конца помогает проверять решение и в других задачах, где известен результат и нужно восстановить путь к нему.

Что запомнить

• Стратегия — план, который учитывает возможные ответы соперника.
• Сначала уточняй правила, допустимые ходы и условие победы.
• Для поиска стратегии часто удобно рассуждать с конца игры.
• Выигрышная позиция позволяет гарантировать победу, проигрышная — нет при правильной игре соперника.
• Найденную закономерность проверяй на разных ходах и применяй только к игре с теми же правилами.