§ 60. Игра как модель управления

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

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

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

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

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

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

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

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

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

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

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

Классификация позиций в игре

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

Разбор задач

Задача 1. На столе 7 камней. Игроки по очереди забирают 1 или 2 камня; выигрывает тот, кто заберёт последний. Определите, кто победит при правильной игре, если начинает первый.

1. Обозначим позицию числом оставшихся камней. При 0 камней ходов нет, поэтому игрок, которому предстоял бы ход, уже проиграл.
2. При 1 или 2 камнях текущий игрок выигрывает, забирая их все. При 3 камнях любой ход оставит сопернику 1 или 2 камня, то есть выигрышную позицию.
3. Значит, 3 камня — проигрышная позиция. При 4 камнях можно взять 1 и оставить 3; так же проигрышны для соперника 6 камней, а выигрышны 7.
4. С первого хода нужно забрать 1 камень и оставить сопернику 6. После его хода брать столько, чтобы вместе с его взятием получилось 3 камня: если он взял 1, взять 2; если 2 — взять 1.

Ответ: первый игрок победит при правильной игре. Он оставляет сопернику кратное 3 число камней, а затем возвращает игру к такой позиции после каждого ответа.

Задача 2. На столе 15 камней. За ход разрешено взять 1, 2 или 3 камня; выигрывает тот, кто заберёт последний. Найдите выигрышную стратегию первого игрока.

1. При 0 камней игра завершена, а игрок, которому нужно было бы ходить, проиграл. При 1, 2 или 3 камнях игрок может забрать всё и выиграть.
2. При 4 камнях любой ход оставляет сопернику от 1 до 3 камней, поэтому 4 — проигрышное количество. Тот же вывод повторяется для 8 и 12: можно оставить сопернику 4, а при этих количествах любой ход отдаёт ему от 1 до 3 камней сверх предыдущей проигрышной позиции.
3. Из 15 камней первый игрок берёт 3 и оставляет 12. Затем он дополняет ход соперника до 4: если соперник взял 1, первый берёт 3; если 2 — берёт 2; если 3 — берёт 1.
4. После каждого такого ответа число камней уменьшается на 4 и становится 8, затем 4, затем 0. Последний камень или камни забирает первый игрок.

Ответ: первый игрок гарантирует победу, сначала взяв 3 камня, а затем каждый раз дополняя ход соперника до 4.

Задача 3. Число равно 1. Игроки по очереди прибавляют к нему 1 или 2; выигрывает тот, кто первым получит число не меньше 10. Определите, может ли первый игрок гарантировать победу, и обоснуйте стратегию.

1. Позиция задаётся текущим числом, а ход заканчивает игру, если результат становится не меньше 10. При 8 или 9 игрок, которому принадлежит ход, может достичь порога сразу.
2. При 7 игрок не может выиграть сразу и после прибавления 1 или 2 оставит сопернику 8 или 9. Значит, 7 — проигрышная позиция.
3. При 6 можно прибавить 1 и оставить 7, поэтому 6 выигрышно. Аналогично 4 проигрышно: ходы ведут к 5 или 6, а из этих позиций следующий игрок может привести число к 7 либо выиграть.
4. Продолжая рассуждение назад, получаем проигрышные позиции 1, 4 и 7. Первый игрок начинает с 1 и вынужден перейти к 2 или 3 — обе позиции выигрышны для соперника.

Ответ: первый игрок не может гарантировать победу. Если соперник играет правильно, он после первого хода достигнет 4 или 7, а затем — 7 или порога 10.

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

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

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

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

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

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

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

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

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