§ 57. Дерево игры

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Кучка из 1, 2 или 3 камней: последний взявший проигрывает

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

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

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

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

Ответ: начальная позиция выигрышна для первого игрока. Нужно взять 1 или 2 камня; брать все 3 нельзя. После этого сопернику придётся взять оставшиеся камни и забрать последний.

Кучка из 7 камней: последний взявший выигрывает

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

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

2. Из 4 камней можно взять 1 и оставить 3, значит, позиция 4 выигрышна. Из 5 камней можно оставить сопернику 3, поэтому 5 тоже выигрышна. Из 6 камней после взятия 1 останется 5, а после взятия 2 — 4; оба результата выигрышны для соперника, значит, 6 проигрышно.

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

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

Две кучки: 3 и 4 камня

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

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

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

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

Ответ: первый игрок выигрывает, если сразу берёт 1 камень из кучки в 4 камня и получает (3, 3). Затем он повторяет ход соперника в другой кучке, сохраняя симметрию до победы.

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

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

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

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

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

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

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

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

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