альфа-бета алгоритмом по сравнению с программой минимаксного полного перебора
рис. 15.3?
Эффективность альфа-бета процедуры зависит от порядка, в котором просматриваются позиции. Всегда лучше первыми рассматривать самые сильные ходы с каждой из сторон. Легко показать на примерах, что
% Альфа-бета алгоритм
альфабета( Поз, Альфа, Бета, ХорПоз, Оц) :-
ходы( Поз, СписПоз), !,
прибл_лучш( СписПоз, Альфа, Бета, ХорПоз, Оц);
стат_оц( Поз, Оц).
прибл_лучш( [Поз | СписПоз], Альфа, Бета, ХорПоз, ХорОц) :-
альфабета( Поз, Альфа, Бета, _, Оц),
дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц).
дост_хор( [ ], _, _, Поз, Оц, Поз, Оц) :- !.
% Больше нет кандидатов
дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-
ход_мина( Поз), Оц > Бета, !;
% Переход через верхнюю границу
ход_макса( Поз), Оц < Альфа, !.
% Переход через нижнюю границу
дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-
нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета),
% Уточнить границы
прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),
выбор( Поз, Оц, Поз1, Оц1, ХорПоз, ХорОц).
нов_границы( Альфа, Бета, Поз, Оц, Оц, Бета) :-
ход_мина( Поз), Оц > Альфа, !.
% Увеличение нижней границы
нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-
ход_макса( Поз), Оц < Бета, !.
% Уменьшение верхней границы
нов_границы( Альфа, Бета, _, _, Альфа, Бета).
выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-
ход_мина( Поз), Оц > Оц1, !;
ход_макса( Поз), Оц < Оц1, !.
выбор( _, _, Поз1, Оц1, Поз1, Оц1).
Рис. 15. 5. Реализация альфа-бета алгоритма.
возможен настолько неудачный порядок просмотра, что альфа-бета алгоритму придется пройти через
