"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Инвариант стратегии — свойство игровой позиции, которое игрок умеет сохранять после каждого хода соперника. Такой подход помогает не перебирать все возможные партии, а построить общее правило действий. Нужно найти выгодное состояние, доказать, что после любого хода противника существует допустимый ответ, восстанавливающий это состояние, и связать сохранение инварианта с окончанием игры. Особенно часто метод работает через симметрию, чётность и остатки при делении.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Позиция игры — состояние задачи перед очередным ходом: например, количество камней в кучках или расположение фишек. От позиции зависят разрешённые действия и возможность победить. Это понятие позволяет описывать игру не словами о конкретной партии, а набором параметров.
Выигрышная стратегия — правило выбора ходов, гарантирующее победу независимо от действий соперника. Она должна работать не только против одного удобного варианта поведения противника. Поэтому стратегия описывает ответ на любой допустимый ход.
Инвариант — свойство позиции или величина, сохраняющаяся после заранее выбранной последовательности ходов. Например, можно поддерживать равенство двух кучек или кратность трём числа камней. Инвариант нужен, чтобы узнавать выгодную позицию после каждого раунда игры.
Инвариантная стратегия — стратегия, при которой игрок после каждого хода соперника восстанавливает заданный инвариант. Соперник может изменить позицию, но ответ возвращает её в нужный класс. Так игрок управляет развитием партии, не угадывая следующий ход противника.
Игровую задачу сначала представляют как множество позиций и разрешённых переходов между ними. Для каждой позиции указывают, кто ходит, какие ходы допустимы и когда игра заканчивается. Такое описание нужно потому, что стратегия должна учитывать не отдельную историю партии, а любую ситуацию, которая может возникнуть.
Для построения стратегии ищут позиции с выгодным свойством, из которых соперник не может навсегда вывести игру из удобного состояния. Если после каждого его хода существует возвращающий ответ, игрок снова получает такую позицию. Поэтому достаточно доказать устойчивость свойства, а не перечислять все партии.
Инвариант выбирают, сравнивая разрешённые ходы игроков. Часто два последовательных хода должны в сумме давать фиксированное число, либо действия игроков должны взаимно компенсироваться. Полезно проверить чётность, остатки при делении, равенство частей и симметрию расположения.
После хода соперника нужно явно построить ответ. Для этого вычисляют, как изменилась позиция, и выбирают допустимое действие, возвращающее инвариант: например, при взятии одного камня взять два, чтобы общая потеря составила три. Ответ должен быть найден для каждого разрешённого хода, а не только для показанного примера.
Нескольких удачных партий недостаточно, потому что соперник может выбрать непроверенный ход. Полное доказательство устанавливает существование ответа, его допустимость и восстановление инварианта на каждом шаге. Наконец, нужно показать, что число предметов уменьшается и игра заканчивается, причём сохранение свойства приводит именно к победе.
Таблица показывает, какие вопросы нужно последовательно задать при построении доказательства. Если на одном этапе нет ответа, стратегию нельзя считать доказанной. Особенно тщательно проверяют ответный ход и завершение игры.
| Этап | Что нужно определить | Роль в доказательстве |
|---|---|---|
| Начальная позиция | Кто ходит первым и обладает ли позиция выгодным свойством | Определяет, кому доступна инвариантная стратегия |
| Инвариант | Свойство или величина, которую необходимо сохранять | Разделяет позиции на выгодные и невыгодные |
| Ход соперника | Какие изменения инварианта может вызвать любой ход соперника | Показывает, какие ответы должны быть предусмотрены |
| Ответный ход | Как восстановить инвариант после хода соперника | Обеспечивает выполнение стратегии |
| Завершение игры | Почему последовательность ходов обязательно закончится победой | Завершает доказательство стратегии |
В кучке 15 камней, за ход разрешено взять 1 или 2 камня, а игрок без хода проигрывает. Нужно определить победителя при правильной игре. Подходящими будут позиции, в которых число камней кратно трём.
Ответный ход всегда допустим и восстанавливает кратность трём. После хода второго игрока наступает нулевая позиция, и первый не может сделать ход. Выигрывает второй игрок.
Есть две равные кучки, из одной за ход можно взять любое положительное число камней. Требуется найти стратегию второго игрока. Здесь естественный инвариант — равенство размеров кучек.
Стратегия работает после каждого хода первого игрока. Когда обе кучки опустеют, первый игрок не сможет ходить. Следовательно, при ненулевых равных кучках выигрывает второй.
В двух кучках 7 и 11 камней, за ход можно брать любое положительное число только из одной кучки. Первый игрок должен начать так, чтобы получить равные кучки. Разность размеров равна 4, поэтому именно столько нужно убрать из большей кучки.
Первый ход переводит игру в позицию, выгодную применяющему симметричную стратегию. Каждый ответ существует и допустим, потому что равные кучки содержат одинаковое число камней. Побеждает первый игрок.
Инвариантом называют любое удобное число, не проверяя сохранение после ответа. Такое число может красиво выглядеть в начальной позиции, но разрушаться первым же ходом соперника. Проверяйте инвариант на всех типах разрешённых ходов, а не только на одном.
Иногда описывают подходящий ответ, но не доказывают, что он существует всегда. Ошибка возникает из-за проверки нескольких привычных случаев вместо полного разбора. Составьте список всех ходов соперника и для каждого укажите конкретный допустимый ответ.
Последовательность ходов против одного поведения соперника принимают за выигрышную стратегию. Но противник не обязан повторять этот сценарий и может выбрать любой разрешённый ход. Проверьте, сформулировано ли правило ответа независимо от намерений соперника.
Наконец, забывают об условии окончания игры. Сохранение инварианта само по себе не доказывает победу, если непонятно, кто получит последний ход. Укажите, как уменьшается число камней или другой параметр и почему именно соперник окажется без допустимого действия.
Для метода нужны понятия состояния задачи, допустимого хода, выигрыша и проигрыша, а также навыки рассуждения о чётности и остатках. Инвариантные стратегии встречаются в олимпиадных задачах с камнями, фишками, клетками и последовательностью ходов. Тема подготавливает к изучению выигрышных и проигрышных позиций, рекуррентного анализа игр и компьютерного моделирования стратегий.
Чем инвариантная стратегия отличается от обычного перебора ходов?
Перебор рассматривает отдельные варианты развития игры и может быстро стать слишком большим. Инвариантная стратегия задаёт общее правило: после любого хода соперника выполнить ответ, восстанавливающий нужное свойство.
Как понять, какое свойство выбрать в качестве инварианта?
Ищите свойство, связанное с разрешёнными ходами и условием победы. Часто подходят равенство кучек, чётность числа предметов или кратность некоторому числу.
Обязательно ли инвариант должен быть числом?
Нет. Инвариантом может быть равенство, симметрия расположения, определённый остаток или другое свойство позиции.
Что делать, если после хода соперника нельзя восстановить инвариант?
Значит, выбранное свойство не подходит для данной стратегии или начальная позиция невыгодна. Нужно изменить инвариант либо проверить, не должен ли первым ходить другой игрок.
Как доказать, что найденная стратегия гарантирует победу?
Нужно доказать три факта: ответный ход существует при любом ходе соперника, он допустим и восстанавливает инвариант. Затем следует показать, что игра обязательно закончится и последний допустимый ход сделает игрок, применяющий стратегию.
§ 59. Инвариант стратегии
