Исследуем позиции на дереве игры

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

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

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

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

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

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

Ответ: выигрышными отмечают вершины, имеющие ход в проигрышную позицию; проигрышными — вершины, все ходы из которых ведут в выигрышные. Конечные вершины размечают первыми согласно правилам.

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

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

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

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

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

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

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

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

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

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

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

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

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