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

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

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

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

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

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

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

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

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

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

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

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

Элементы и признаки дерева игры

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

Разбор задач

Задача 1. В кучке 5 камней, за ход можно взять 1 или 2, последний камень приносит победу взявшему. Нужно построить дерево и найти выигрышный первый ход. Обозначим позицию числом оставшихся камней: при 0 камней ходить уже нельзя, поэтому для игрока, которому предстоит ход, это проигрыш. Разметим позиции снизу вверх, чтобы не выбирать ход только по тому, насколько он приближает конец партии.

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

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

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

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

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

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

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

Ответ: первый игрок выигрывает, если первым уменьшит 20 до 19. Дальнейший ход выбирают не по принципу «число стало меньше», а по оценке всех доступных продолжений. Например, из 19 соперник может получить 18, 17 или 9; все эти позиции выигрышны для игрока, которому предстоит ходить после соперника.

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

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

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

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

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

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

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

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

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