"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Инвариант помогает увидеть закономерность, которая сохраняется после ходов в конечной игре. Сначала позицию переводят на формальный язык, затем сравнивают изменения параметров и выделяют проигрышный класс состояний. После этого первый игрок выполняет ход в такой класс, а дальше отвечает на действия соперника, возвращая игру к нужному свойству. Главное — доказать, что ответ возможен всегда и приводит к окончанию игры в пользу выбранного игрока.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Инвариант — свойство позиции или величина, которая не изменяется либо изменяется предсказуемым образом после каждого разрешённого хода. Например, это может быть чётность числа объектов или остаток по модулю. Инвариант нужен, чтобы заменить множество отдельных позиций понятным общим правилом.
Игровая позиция — описание состояния игры в данный момент: расположение объектов, количество ресурсов и доступные ходы. Важно указать только те параметры, от которых действительно зависит дальнейшая игра. Такое описание переводит условие задачи на формальный язык и помогает сравнивать состояния.
Выигрышная позиция — позиция, из которой при правильной игре можно обеспечить победу. Это не обязательно позиция, где победа наступает немедленно: иногда нужно выполнить несколько ответных ходов. Понятие позволяет оценивать состояние не по внешнему виду, а по возможному результату всей игры.
Проигрышная позиция — позиция, из которой победа невозможна при безошибочной игре соперника. Из неё любой ход должен давать противнику возможность перейти в выигрышное состояние. Поиск таких позиций обычно становится основой стратегии.
Сначала условие игры переводят на формальный язык: выделяют начальную позицию, разрешённые ходы и условие окончания. Это нужно потому, что обычное описание может скрывать существенные ограничения, например запрет брать объекты из двух кучек сразу. Формальная модель показывает, какие параметры требуется отслеживать и какие действия действительно доступны игрокам.
Инвариант ищут, сравнивая позиции до и после хода. Проверяют чётность, остатки по модулю, симметрию, равенство частей или другую величину, которая ведёт себя предсказуемо. Такой поиск полезен потому, что ходов может быть много, а изменение выбранного свойства часто описывается одним коротким правилом.
Инвариант помогает найти проигрышные позиции, если удаётся выделить класс состояний, в который игрок может возвращать игру после каждого хода соперника. Тогда соперник каждый раз начинает из неудобного класса, а возможность ответить сохраняется до конца. Само совпадение значения инварианта ещё ничего не доказывает: нужно установить связь с победой или поражением.
Стратегия строится в два этапа. Сначала игрок своим ходом переводит начальную позицию в выбранный класс проигрышных позиций, а затем после каждого действия соперника выполняет ответ, восстанавливающий инвариант. Такая схема превращает разрозненные решения в единое правило, работающее для любого допустимого хода.
Стратегия требует доказательства, потому что удачные ответы для нескольких случаев не гарантируют результата. Нужно показать, что ответ существует после каждого хода соперника и сам остаётся разрешённым. Наконец, анализируют окончание: если выбранный игрок сохраняет инвариант до последнего хода, то по условию игры устанавливают, кому достаётся победа.
Таблица задаёт порядок анализа задачи: от точного описания состояния до проверки окончания игры. Ею удобно пользоваться как алгоритмом решения: на каждом этапе записывают не догадку, а проверяемое свойство. Если на каком-то шаге не получается доказать существование ответа, выбранный инвариант нужно заменить.
| Этап анализа | Что проверяется | Результат |
|---|---|---|
| Описание позиции | Какие параметры полностью определяют состояние игры | Формальная модель позиции |
| Анализ хода | Как меняются параметры после каждого разрешённого действия | Кандидаты на инвариант |
| Классификация позиций | Какие значения инварианта соответствуют выигрышным и проигрышным позициям | Выбранный класс проигрышных позиций |
| Первый ход | Можно ли перевести начальную позицию в проигрышный класс | Начало стратегии |
| Ответ на ход соперника | Как восстановить инвариант после любого хода | Правило ответных действий |
| Проверка окончания | Кто делает последний ход и к какому результату это приводит | Доказательство стратегии |
На столе лежит 21 спичка, за ход можно взять 1, 2 или 3 спички, а последняя спичка приносит победу взявшему. Требуется определить выигрышную стратегию первого игрока. Удобно считать не взятые, а оставшиеся спички и искать число, после которого любой ответ соперника можно дополнить до четырёх.
Выигрывает первый игрок. Его стратегия — сначала взять одну спичку, а затем каждый раз дополнять ход соперника до четырёх.
В двух кучках лежит по 17 камней, за ход разрешено взять любое положительное число камней только из одной кучки. Проигрывает тот, кто не может сделать ход. Нужно понять, кто выигрывает при правильной игре, если начать с равных кучек.
При правильной игре выигрывает второй игрок. Его стратегия сохраняет равенство кучек и обеспечивает ответ на любое допустимое действие первого.
На доске 6 × 6 фишки стоят в клетках, симметричных относительно центра, а за ход можно убрать одну или несколько фишек из одной строки. Проигрывает тот, кто не может сделать ход. Нужно проверить, сможет ли первый игрок нарушить ответную стратегию соперника.
Первый игрок выиграть не может: при правильной игре второй сохраняет симметрию и делает последний ход. Это пример инварианта-симметрии, а не числового остатка.
Первую ошибку допускают, когда любую неизменную величину сразу называют инвариантом. Она может сохраняться лишь в нескольких случаях и нарушаться другим разрешённым ходом. Проверьте свойство на всех типах действий, предусмотренных условием.
Вторая ошибка — объявить выигрышными позиции с удобным значением инварианта без доказательства. Само значение не показывает, можно ли сделать из позиции нужный ход. Проверьте, что из каждой позиции выбранного класса существует переход в проигрышный класс соперника.
Третья ошибка состоит в описании одного удачного первого хода. Соперник может выбрать другой вариант, для которого ответа не указано. Составьте правило, зависящее от любого его хода, и проверьте несколько разных случаев.
Четвёртая ошибка связана с условием окончания игры. Если последний ход выигрывает, отсутствие хода означает поражение, а при обратном правиле вывод меняется. Перед классификацией конечных позиций выпишите это условие отдельно и примените его к последнему шагу.
Для работы нужны делимость, остатки по модулю, чётность, симметрия, математическая индукция и умение описывать алгоритм. Метод применяется в олимпиадных задачах и при анализе конечных игр, где требуется доказать результат для всех ходов.
Он связан с рекурсивным анализом состояний и динамическим программированием: каждую позицию можно классифицировать по результатам доступных переходов. В информатике похожая логика используется при доказательстве корректности программ и построении стратегий в алгоритмах.
Как понять, какую величину выбрать в качестве инварианта?
Сравните состояние игры до и после каждого разрешённого хода. Подходящими кандидатами часто оказываются чётность, остаток по модулю, равенство частей или симметрия. Затем проверьте кандидат не на одном ходе, а на всех возможных действиях.
Почему недостаточно просто заметить закономерность в нескольких примерах?
Несколько примеров могут случайно давать одинаковый результат. Доказательство должно охватывать любую позицию и любой разрешённый ход. Иначе неизвестно, не нарушится ли закономерность в другой ситуации.
Как определить, какая позиция является проигрышной?
Проигрышной считают позицию, из которой соперник при правильной игре может избежать поражения. Обычно проверяют, можно ли из неё попасть в выигрышную позицию соперника, а из любой соседней выигрышной позиции — вернуть игру в проигрышный класс.
Что делать, если после хода соперника нельзя точно восстановить прежнее значение инварианта?
Проверьте, действительно ли нужно сохранять то же значение. Иногда достаточно возвращать позицию в тот же класс, например сохранять чётность или симметрию. Если это невозможно, следует искать другой инвариант или иную стратегию.
Всегда ли симметричный ответ является стратегией на основе инварианта?
Нет. Симметричный ответ становится такой стратегией только тогда, когда после него сохраняется выбранное свойство позиции. Нужно также доказать, что ответ возможен после любого хода и что игра завершится с нужным результатом.
Лабораторная работа № 28 (к § 59) Построение стратегии на основе инварианта
