Назад | Содержание| Вперёд 15. 3. Альфа-бета алгоритм:эффективная реализаци...

Назад | Содержание| Вперёд

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) >= Бета

Рис. 15. 4.  Дерево рис. 15.2после применения альфа-бета алгоритма.