Минимаксный алгоритм (листинг 6.1) вычисляет минимаксное решение из текущего состояния. В нем используется простое рекурсивное вычисление минимаксных значений каждого состояния-преемника с непосредственной реализацией определяющих уравнений. Рекурсия проходит все уровни вплоть до листьев дерева, а затем минимаксные значения резервируются по всему дереву по мере обратного свертывания рекурсии. Например, в дереве, показанном на рис. 6.2, алгоритм вначале выполнил рекурсию с переходом на нижние уровни до трех нижних левых узлов и применил к ним функцию полезности Utility, чтобы определить, что значения полезности этих узлов соответственно равны 3, 12 и 8. Затем алгоритм определяет минимальное из этих значений, 3, и возвращает его в качестве зарезервированного значения узла В. Аналогичный процесс позволяет получить зарезервированные значения 2 для узла С и 2 для узла D. Наконец, берется максимальное из значений 3, 2 и 2 для получения зарезервированного значения 3 корневого узла.

Листинг 6.1. Алгоритм вычисления минимаксных решений. Он возвращает действие, соответствующее наилучшему возможному ходу, т.е. действие, ведущее к результату с наилучшей полезностью, в соответствии с предположением, что противник играет с целью минимизации полезности. Функции Max-Value и Min-Value используются для прохождения через все дерево игры вплоть до листьев, что позволяет определить зарезервированное значение некоторого состояния

Этот минимаксный алгоритм выполняет полное исследование дерева игры в глубину. Если максимальная глубина дерева равна m и в каждом состоянии имеются b допустимых ходов, то временная сложность этого минимаксного алгоритма составляет. Для алгоритма, который формирует сразу всех преемников, пространственная сложность равна О(bт), а для алгоритма, который формирует преемников по одному, — 0(т). Безусловно, в реальных играх такие затраты времени полностью неприемлемы, но данный алгоритм служит в качестве основы математического анализа игр, а также более практичных алгоритмов.