Дерево игры

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

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

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

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

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

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

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

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

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

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

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

Что показывает дерево игры

Читай схему от корня: выбери ветвь и перейди к узлу, который показывает результат хода. Из нового узла снова рассмотрите все ветви, ведь ходить будет другой игрок. Дойдя до листа, определи исход по правилам, а затем используй его для анализа предыдущих позиций.

Разбор задач

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

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

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

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

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

Ответ: нужно взять 1 фишку. Тогда после любого ответа соперника первый игрок сможет забрать оставшиеся фишки последним ходом.

Задача 3. На столе лежат 7 фишек. За ход можно взять 1 или 2 фишки, а взявший последнюю выигрывает. Составь дерево до позиций, из которых можно определить исход, и опиши стратегию первого игрока.

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

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

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

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

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

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

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

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

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

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

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

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