§ 59 Инвариант стратегии

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

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

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

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

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

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

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

Обычное наблюдение сообщает, что некоторое свойство встречается в нескольких позициях, но не объясняет, почему оно будет появляться дальше. Инвариант требует правила действий: после выбранного ответа свойство должно сохраняться или восстанавливаться. Часто ход соперника нарушает его, а ответ игрока возвращает игру к нужному виду. Поэтому инвариант может относиться не к каждому отдельному ходу, а к паре «ход соперника — ответ».

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

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

Построение стратегии с инвариантом

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

Разбор задач

Кучка из 15 камней

Игроки берут за ход 1 или 2 камня, а проигрывает тот, кто не может ходить. Нужно найти победителя и правило действий. Подходящий инвариант — после своего ответа оставлять число камней, кратное 3.

1. Число 15 кратно 3, поэтому первый игрок отдаёт сопернику позицию с 15 камнями, фактически не делая хода невозможно; значит, эту позицию нужно рассмотреть внимательнее.
2. Первый игрок берёт 1 камень, оставляя 14, то есть переводит игру в позицию, где остаток по модулю 3 равен 2.
3. После хода соперника первый берёт столько камней, чтобы за два хода было взято 3: после 1 берёт 2, после 2 берёт 1.
4. Так после каждой пары ходов из исходной кучки исчезают 3 камня. После ответа первого игрока останется 2, затем соперник возьмёт 1 или 2, а первый заберёт остаток до трёх.

Первый игрок выигрывает: его первый ход — взять 1 камень, затем каждый раз дополнять ход соперника до трёх. В конце после его ответа сопернику остаётся 0 камней, поэтому именно соперник не сможет сделать ход.

Две кучки по 7 камней

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

1. Первый игрок берёт k камней из одной кучки, где 1 ≤ k ≤ 7.
2. Вторая кучка после этого остаётся больше первой ровно на k камней, поэтому второй игрок берёт k камней из другой кучки.
3. Размеры кучек снова становятся одинаковыми. После любого следующего хода первого игрок повторяет такое же действие в оставшейся кучке.

Выигрывает второй игрок. Его стратегия — зеркально повторять количество взятых камней в другой кучке; после его ответов позиции имеют вид (a, a), а последним ход всегда делает он.

Три кучки: 3, 4 и 5 камней

В этой игре можно взять любое положительное число камней из одной кучки. Для таких позиций используют двоичный XOR: это побитовая операция, обозначаемая ⊕. Выигрышными для отвечающего игрока будут позиции, где 3 ⊕ 4 ⊕ 5 = 2, поэтому сначала нужно сделать ход, переводящий позицию в XOR, равный 0.

1. В двоичной записи 3 = 011, 4 = 100, 5 = 101, поэтому 3 ⊕ 4 ⊕ 5 = 010, то есть 2.
2. Из кучки 3 можно взять 2 камня и оставить 1: 1 ⊕ 4 ⊕ 5 = 0. Значит, первый ход — взять 2 камня из первой кучки.
3. После любого хода соперника XOR становится ненулевым. Теорема о XOR позволяет выбрать одну кучку и уменьшить её так, чтобы общий XOR снова стал 0; такой ход всегда положителен и допустим.

Побеждает первый игрок, начав с хода «взять 2 из кучки 3». Затем он после каждого хода соперника возвращает XOR к нулю, а конечную позицию без камней получает после своего ответа.

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

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

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

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

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

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

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

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

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

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

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