Программирование на языке ПРОЛОГ для искуственного интеллекта




Альфа-бета алгоритм: эффективная реализация минимаксного принципа - часть 4


Отношение

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

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

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

line();

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

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

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

        дост_хор( [ ], _, _, Поз, Оц, Поз, Оц) :-  !.
                                                % Больше нет кандидатов




Содержание  Назад  Вперед