Дерево игры

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

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

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

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

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

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

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

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

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

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

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

Элементы дерева игры и их значение

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

Разбор задач

Два первых хода и по одному ответу

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

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

Ответ. Дерево имеет корень S, два узла второго уровня A и B и два листа A₁ и B₁. В нём ровно два возможных продолжения партии. Каждая ветвь показывает отдельный ход, поэтому один путь от S до листа описывает один вариант.

Игра на вычитание из числа 5

Условие. Игроки по очереди вычитают из текущего числа 1 или 2; тот, кто не может сделать ход, проигрывает. Построим дерево до конца, записывая число, которое осталось. Начинаем с позиции 5, а достижение 0 означает, что следующий игрок уже не может ходить.

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

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

Есть ли у первого игрока выигрышная стратегия?

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

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

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

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

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

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

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

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

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

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

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

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

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