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




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


                                                % Увеличение нижней границы

        нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-
                ход_макса( Поз), Оц < Бета,  !.

                                                % Уменьшение верхней границы

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

        выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-
                ход_мина( Поз), Оц > Оц1,  !;
                ход_макса( Поз), Оц < Оц1,  !.

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

line();

Рис. 15. 5.  Реализация альфа-бета алгоритма.

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




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