Альфабета алгоритм эффективная реализация минимаксного принципа
15. 3. Альфа-бета алгоритм: эффективная реализация минимаксного принципа
Программа, показанная на Рисунок 15.3, производит просмотр в глубину дерева поиска, систематически обходя все содержащиеся в нем позиции вплоть до терминальных; она вычисляет статические оценки всех терминальных позиций. Как правило, для того, чтобы получить правильную минимаксную оценку корневой вершины, совсем не обязательно проделывать эту работу полностью. Поэтому алгоритм поиска можно сделать более экономным. Его можно усовершенствовать, используя следующую идею. Предположим, что у нас есть два варианта хода. Как только мы узнали, что один из них явно хуже другого, мы можем принять правильное решение, не выясняя, на сколько в точности он хуже. Давайте используем этот принцип для сокращения дерева поиска Рисунок 15.2. Процесс поиска протекает следующим образом:
(1) Начинаем с позиции а.
(2) Переходим к b.
(3) Переходим к d.
(4) Берем максимальную из оценок преемников позиции d, получаем V( d) = 4.
(5) Возвращаемся к b и переходим к е.
(6) Рассматриваем первого преемника позиции е с оценкой 5. В этот момент МАКС (который как раз и должен ходить в позиции е) обнаруживает, что ему гарантирована в позиции е оценка не меньшая, чем 5, независимо от оценок других (возможно, более предпочтительных) вариантов хода. Этого вполне достаточно для того, чтобы МИН, даже не зная точной оценки позиции е, понял, что для него в позиции b ход в е хуже, чем ход в d.
На основании приведенного выше рассуждения мы можем пренебречь вторым преемником позиции е и приписать е приближенную оценку 5. Приближенный характер этой оценки не окажет никакого влияния на оценку позиции b, а следовательно, и позиции а.
На этой идее основан знаменитый альфа-бета алгоритм, предназначенный для эффективной реализации минимаксного принципа. На Рисунок 15.4 показан результат работы альфа-бета алгоритма, примененного к нашему дереву Рисунок 15.2. Из Рисунок 15.4 видно, что некоторые из рабочих оценок стали приближенными. Однако этих приближенных оценок оказалось достаточно для того, чтобы определить точную оценку корневой позиции. Сложность поиска уменьшилась до пяти обращений к оценочной функции по сравнению с восемью обращениями (в первоначальном дереве поиска Рисунок 15.2).
Как уже говорилось раньше, ключевая идея альфа-бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение. Эту идею можно формализовать, введя два граничных значения, обычно обозначаемых через Альфа и Бета, между которыми должна заключаться рабочая оценка позиции. Смысл этих граничных значений таков: Альфа -это самое маленькое значение оценки, которое к настоящему моменту уже гарантировано для игрока МАКС; Бета - это самое большое значение оценки, на которое МАКС пока еще может надеяться. Разумеется, с точки зрения МИН'а, Бета является самым худшим значением оценки, которое для него уже гарантировано. Таким образом, действительное значение оценки (т. е. то, которое нужно найти) всегда лежит между Альфа и Бета. Если же стало известно, что оценка некоторой позиции лежит вне интервала Альфа-Бета, то этого достаточно для того, чтобы сделать вывод: данная позиция не входит в основной вариант. При этом точное значение оценки такой позиции знать не обязательно, его надо знать только тогда, когда оценка лежит между Альфа и Бета. "Достаточно хорошую" рабочую оценку V( Р, Альфа, Бета) позиции Р по отношению к Альфа и Бета можно определить формально как любое значение, удовлетворяющее следующим ограничениям:
V( P, Альфа, Бета) <= Альфа если V( P) <= Альфа
V( P, Альфа, Бета) = V( P) если Альфа < V( P) < Бета
V( P, Альфа, Бета) >= Бета если V( P) >= Бета
