§ 58. Построение стратегии

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

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

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

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

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

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

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

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

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

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

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

Как определить результат из игровой позиции

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

Разбор задач

Задача 1

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

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

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

Задача 2

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

1. Начинаем с 0: это проигрышная позиция для того, кому предстоит ходить.
2. Из 1, 2 и 3 можно сразу перейти в 0, поэтому эти позиции выигрышны, а 4 проигрышна: любой ход оставляет 1, 2 или 3.
3. Далее повторяется блок из четырёх чисел: 5–7 выигрышны, 8 проигрышна, затем 9–11 выигрышны и 12 проигрышна.
4. До 20 проигрышными будут 0, 4, 8, 12, 16 и 20, а все остальные позиции — выигрышными.

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

Задача 3

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

1. Позиции 0, 3, 6, 9, 12 и 15 оказываются проигрышными: из каждой все допустимые переходы ведут в выигрышные позиции.
2. Позиции 16 и 17 выигрышны, потому что из них можно попасть соответственно в 15 и 16; позиция 18 тоже выигрышна уже благодаря переходу в 9.
3. Переход 18 → 9 разрешён, так как 18 делится на два, а 9 — проигрышная позиция для следующего игрока.

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

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

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

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

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

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

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

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

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

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