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


         

возможен настолько неудачный порядок просмотра,



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

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

                ход_макса( Поз), Оц < Бета,  !.


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

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

        выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-

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

                ход_макса( Поз), Оц < Оц1,  !.


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

line();

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

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


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