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

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

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

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

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

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

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

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

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

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

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

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

Процедура

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

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

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

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

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

рис. 15.3?

Эффективность альфа-бета процедуры зависит от порядка, в котором просматриваются позиции. Всегда лучше первыми рассматривать самые сильные ходы с каждой из сторон. Легко показать на примерах, что

% Альфа-бета алгоритм

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

ходы( Поз, СписПоз), !,

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

стат_оц( Поз, Оц).

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

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

дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц).

дост_хор( [ ], _, _, Поз, Оц, Поз, Оц) :- !.

% Больше нет кандидатов

дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-

ход_мина( Поз), Оц > Бета, !;

% Переход через верхнюю границу

ход_макса( Поз), Оц < Альфа, !.

% Переход через нижнюю границу

дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-

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

% Уточнить границы

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

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

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

ход_мина( Поз), Оц > Альфа, !.