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