Prolog

значением оценки, которое для него уже гарантировано. Таким образом, действительное значение оценки (т. е. то, которое нужно найти) всегда лежит между Альфа и Бета. Если же стало известно, что оценка некоторой позиции лежит вне интервала Альфа-Бета, то этого достаточно для того, чтобы сделать вывод: данная позиция не входит в основной вариант. При этом точное значение оценки такой позиции знать не обязательно, его надо знать только тогда, когда оценка лежит между Альфа и Бета. 'Достаточно хорошую' рабочую оценку  V( Р, Альфа, Бета)  позиции  Р  по отношению к Альфа и Бета можно определить формально как любое значение, удовлетворяющее следующим ограничениям:

        V( P, Альфа, Бета) <= Альфа    если        V( P) <= Альфа

        V( P, Альфа, Бета) = V( P)           если         Альфа < V( P) < Бета

        V( P, Альфа, Бета) >= Бета      если         V( P) >= Бета

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

Пунктиром показаны ветви, отсеченные альфа-бета алгоритмом

для экономии времени поиска. В результате некоторые из

рабочих оценок стали приближенными (вершины  c,   е,  f;

сравните с рис.15.2). Однако этих приближенных оценок

достаточно для вычисления точной оценки корневой

вершины и построения основного варианта.

Очевидно, что, умея вычислять 'достаточно хорошую' оценку, мы всегда можем вычислить точную оценку корневой позиции  Р,   установив границы интервала следующим образом:

        V( Р, -бесконечность, +бесконечность)  =  V( P)

На рис. 15.5 показана реализация альфа-бета алгоритма в виде программы на Прологе. Здесь основное отношение -

        альфабета( Поз, Альфа, Бета, ХорПоз, Оц)

где ХорПоз - преемник позиции Поз с 'достаточно хорошей' оценкой Оц, удовлетворяющей всем указанным выше ограничениям:

        Оц = V( Поз, Альфа, Бета)

Процедура

        прибл_лучш( СписПоз, Альфа, Бета, ХорПоз, Оц)

находит достаточно хорошую позицию ХорПоз в списке позиций СписПоз; Оц - приближенная (по отношению к Альфа и Бета) рабочая оценка позиции ХорПоз.

Интервал между Альфа и Бета может сужаться (но не расширяться!) по мере углубления поиска, происходящего при рекурсивных обращениях к альфа-бета процедуре. Отношение

        нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета)

определяет новый интервал (НовАльфа, НовБета). Он всегда уже, чем старый интервал (Альфа, Бета), или равен ему. Таким образом, чем глубже мы оказываемся в дереве поиска, тем сильнее проявляется тенденция к сжатию интервала Альфа-Бета, и в результате оценивание позиций на более глубоких уровнях происходит в условиях более тесных границ. При более узких интервалах допускается большая степень 'приблизительности' при вычислении оценок, а следовательно, происходит больше отсечений ветвей дерева. Возникает интересный вопрос: насколько велика экономия, достигаемая