В данном разделе речь идет об играх с двумя игроками, которые будут именоваться МАХ и MIN по причинам, которые вскоре станут очевидными. Игрок МАХ ходит первым, после чего игроки делают ходы по очереди до тех пор, пока игра не закончится. В конце игры игроку-победителю присваиваются очки, а на побежденного налагается штраф. Игра может быть формально определена как своего рода задача поиска с описанными ниже компонентами.

• Начальное состояние, которое включает позицию на доске и определяет игрока, который должен ходить.
• Функция определения преемника, возвращающая список пар (move, state), каждая из которых указывает допустимый ход и результирующее состояние.
• Проверка терминального состояния, которая определяет, что игра закончена. Состояния, в которых игра закончена, называются терминальными состояниями.
• Функция полезности (называемая также целевой функцией, или функцией вознаграждения), которая сообщает числовое значение терминальных состояний. В шахматах результатом является победа, поражение или ничья, со значениями +1, -1 или 0. Некоторые игры имеют более широкий диапазон возможных езультатов; например, количество очков в нардах может составлять от +192 до -192. В настоящем разделе в основном рассматриваются игры с нулевой суммой, хотя будут также кратко упоминаться игры с ненулевой суммой.

Начальное состояние и допустимые ходы каждой стороны определяют дерево игры для данной игры. Из начального состояния игрок МАХ имеет девять возможных ходов. Ходы чередуются так, что мах ставит значок X, a MIN значок О, до тех пор пока не будут достигнуты листовые узлы, соответствующие терминальным состояниям, таким, что один игрок оставил три своих значка в один ряд или заполнены все клетки.

Число под каждым листовым узлом указывает значение полезности соответствующего терминального состояния с точки зрения игрока мах; предполагается, что высокие значения являются благоприятными для игрока МАХ и неблагоприятными для игрока MIN (именно поэтому в теории этим игрокам присвоены такие имена). Задача игрока МАХ состоит в использовании дерева поиска (особенно данных о полезности терминальных состояний) для определения наилучшего хода.

Оптимальные стратегам

При решении обычных задач поиска оптимальное решение для игрока МАХ должно представлять собой последовательность ходов, ведущих к цели — к терминальному состоянию, которое соответствует выигрышу. С другой стороны, в игре участвует также игрок MIN, который имеет другое мнение по этому поводу. Это означает, что игрок МАХ должен найти надежную стратегию, позволяющую определить ход игрока МАХ в начальном состоянии, затем ходы игрока МАХ в состояниях, ставших результатом любого возможного ответа игрока MIN, а затем ходы МАХ в состояниях, ставших результатом любого возможного ответа MIN на те ходы, и т.д. Грубо говоря, оптимальная стратегия приводит к итогу, по меньшей мере, такому же благоприятному, как и любая другая стратегия, в тех условиях, когда приходится играть с противником, не допускающим ошибок. Прежде всего рассмотрим, как найти эту оптимальную стратегию, даже притом что для МАХ часто будет неосуществимой задача ее исчерпывающего вычисления в играх, более сложных, чем крестики-нолики.

(Частичное) дерево поиска для игры крестики-нолики. Верхний узел представляет собой начальное состояние, а первым ходит игрок МАХ, ставя значок X в пустой клетке. На этом рисунке показана часть дерева поиска, в которой демонстрируются чередующиеся ходы игроков MIN (значок О) и МАХ (значок X). Ходы выполняются до тех пор, пока в конечном итоге не будет достигнуто одно из терминальных состояний, которым могут быть назначены данные о полезности в соответствии с правилами игры

Даже такие простые игры, как крестики-нолики, являются слишком сложными, чтобы можно было привести в этой книге для них полное дерево игры, поэтому перейдем к описанию тривиальной игры, показанной на рисунке. Возможные коды игрока МАХ из корневого узла обозначены как аь а2 и а3. Возможными ответами на ход a-i для игрока MIN являются b1, Ь2, Ь3 и т.д. Данная конкретная игра заканчивается после того, как каждый игрок, МАХ и MIN, сделают по одному ходу. (Согласно терминологии теории игр, это дерево имеет глубину в один ход и состоит из сделанных двумя участниками ходов, каждый из которых называется полуходом.) Полезности терминальных состояний в этой игре находятся в пределах от 2 до 14.

Дерево игры с двумя полуходами. Узлы А представляют собой "узлы МАХ", в которых очередь хода принадлежит игроку МАХ, а узлы рассматриваются как "узлы MIN". Терминальные узлы показывают значения полезности для МАХ; остальные узлы обозначены их минимаксными значениями. Лучшим ходом игрока МАХ от корня является а.1, поскольку ведет к преемнику с наибольшим минимаксным значением, а наилучшим ответом MIN является hi, поскольку ведет к преемнику с наименьшим минимаксным значением

При наличии дерева игры оптимальную стратегию можно определить, исследуя минимаксное значение каждого узла, которое можно записать как Minimax-Value (n). Минимаксным значением узла является полезность (для МАХ) пребывания соответствующем состоянии, при условии, что оба игрока делают ходы оптимальным образом от этого узла и до узла, обозначающего конец игры. Очевидно, что минимаксным значением терминального состояния является просто его полезность. Более того, если есть выбор, игрок МАХ должен предпочесть ход, ведущий в состояние с максимальным значением, а игрок MIN — ведущий в состояние с минимальным значением. Поэтому имеет место приведенное ниже соотношение.

Применим эти определения к дереву игры, показанному на  рисунке. Терминальные узлы на низшем уровне уже обозначены числами, которые указывают их полезность. Первый узел MIN, обозначенный как B, имеет трех преемников со значениями 3, 12 и 8, поэтому его минимаксное значение равно 3. Аналогичным образом, другие два узла MIN имеют минимаксное значение, равное 2. Корневым узлом является узел МАХ; его преемники имеют минимаксные значения 3, 2 и 2, поэтому сам корневой узел имеет минимаксное значение 3. Можно также определить понятие минимаксного решения, принимаемого в корне дерева: действие a₁ является оптимальным выбором для игрока мах, поскольку ведет к преемнику с наивысшим минимаксным значением.

В этом определении оптимальной игры для игрока МАХ предполагается, что игрок MIN также играет оптимальным образом: он максимизирует результат, соответствующий наихудшему исходу игры для МАХ. А что было бы, если игрок MIN не играл оптимальным образом? В таком случае можно легко показать, что игрок МАХ добился бы еще большего. Могут существовать другие стратегии игры против соперников, играющих неоптимальным образом, которые позволяют добиться большего, чем минимаксная стратегия; но эти стратегии обязательно действуют хуже против соперников, играющих оптимально.

Минимаксный алгоритм

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

Например, в дереве, показанном на рисунке, алгоритм вначале выполнил рекурсию с переходом на нижние уровни до трех нижних левых узлов и применил к ним функцию полезности utility, чтобы определить, что значения полезности этих узлов соответственно равны 3, 12 и 8. Затем алгоритм определяет минимальное из этих значений, 3, и возвращает его в качестве зарезервированного значения узла В.

Аналогичный процесс позволяет получить зарезервированные значения 2 для узла С и 2 для узла D. Наконец, берется максимальное из значений 3, 2 и 2 для получения зарезервированного значения 3 корневого узла.