Минимаксный алгоритм
Минимаксный алгоритм (листинг 6.1) вычисляет минимаксное решение из текущего состояния. В нем используется простое рекурсивное вычисление минимаксных значений каждого состояния-преемника с непосредственной реализацией определяющих уравнений. Рекурсия проходит все уровни вплоть до листьев дерева, а затем минимаксные значения резервируются по всему дереву по мере обратного свертывания рекурсии. Например, в дереве, показанном на рис. 6.2, алгоритм вначале выполнил рекурсию с переходом на нижние уровни до трех нижних левых узлов и применил к ним функцию полезности Utility, чтобы определить, что значения полезности этих узлов соответственно равны 3, 12 и 8. Затем алгоритм определяет минимальное из этих значений, 3, и возвращает его в качестве зарезервированного значения узла В. Аналогичный процесс позволяет получить зарезервированные значения 2 для узла С и 2 для узла D. Наконец, берется максимальное из значений 3, 2 и 2 для получения зарезервированного значения 3 корневого узла.
Листинг 6.1. Алгоритм вычисления минимаксных решений. Он возвращает действие, соответствующее наилучшему возможному ходу, т.е. действие, ведущее к результату с наилучшей полезностью, в соответствии с предположением, что противник играет с целью минимизации полезности. Функции Max-Value и Min-Value используются для прохождения через все дерево игры вплоть до листьев, что позволяет определить зарезервированное значение некоторого состояния
function Minimax-Decision(state) returns действие action inputs: state, текущее состояние игры
v
function Max-Value(state) returns значение полезности if Terminal-Test(state) then return Utility(state) v
v
v