Prolog

        выбор( Поз0, Оц0, Поз1, Оц1, Поз0, Оц0) :-

                ход_мина( Поз0), Оц > Оц1,  !;

                ход_макса( Поз0), Оц < Оц1,  !.

        выбор( Поз0, Оц0, Поз1, Оц1, Поз1, Оц1).

Рис. 15. 3.  Упрощенная реализация минимаксного принципа.

Программа на Прологе, вычисляющая минимаксную рабочую оценку для некоторой заданной позиции, показана на рис. 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).