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

находит достаточно хорошую позицию ХорПоз в списке позиций СписПоз; Оц — приближенная (по отношению к Альфа и Бета) рабочая оценка позиции ХорПоз.

Интервал между Альфа и Бета может сужаться (но не расширяться!) по мере углубления поиска, происходящего при рекурсивных обращениях к альфа-бета процедуре. Отношение

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

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

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

альфабета( Поз, Альфа, Бета, ХорПоз, Оц) :-

 ходы( Поз, СписПоз), !,

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

 стат_оц( Поз, Оц).

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

 альфабета( Поз, Альфа, Бета, _, Оц),

 дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц).

дост_хор( [], _, _, Поз, Оц, Поз, Оц) :- !.

 % Больше нет кандидатов

дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-

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

  % Переход через верхнюю границу

 ход_макса( Поз), Оц < Альфа, !.

  % Переход через нижнюю границу

дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-

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

  % Уточнить границы

 прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),

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

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

 ход_мина( Поз), Оц > Альфа, !.

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

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

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

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

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

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

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

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

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

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

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

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