Prolog
Шрифт:
Оц = V( Поз, Альфа, Бета)
Процедура
прибл_лучш( СписПоз, Альфа, Бета, ХорПоз, Оц)
находит достаточно хорошую позицию ХорПоз в списке позиций СписПоз; Оц– приближенная (по отношению к Альфа и Бета) рабочая оценка позиции ХорПоз.
Интервал между Альфа и Бета может сужаться (но не расширяться!) по мере углубления поиска, происходящего при рекурсивных обращениях к альфа-бета процедуре. Отношение
нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета)
определяет новый интервал (НовАльфа, НовБета). Он всегда уже, чем старый интервал (Альфа, Бета), или равен ему. Таким образом, чем глубже мы оказываемся в дереве поиска, тем сильнее проявляется тенденция к сжатию интервала Альфа-Бета, и в результате оценивание позиций на более глубоких уровнях происходит в условиях более тесных границ. При более узких интервалах допускается большая степень "приблизительности" при вычислении оценок, а следовательно, происходит больше отсечений ветвей дерева. Возникает интересный вопрос: насколько велика экономия, достигаемая альфа-бета алгоритмом по сравнению с программой минимаксного полного перебора
рис. 15.3?
Эффективность альфа-бета процедуры зависит от порядка, в котором просматриваются позиции. Всегда лучше первыми рассматривать самые сильные ходы с каждой из сторон. Легко показать на примерах, что
% Альфа-бета алгоритм
альфабета( Поз, Альфа, Бета, ХорПоз, Оц) :-
ходы( Поз, СписПоз), !,
прибл_лучш( СписПоз, Альфа, Бета, ХорПоз, Оц);
стат_оц( Поз, Оц).
прибл_лучш( [Поз | СписПоз], Альфа, Бета, ХорПоз, ХорОц) :-
альфабета( Поз, Альфа, Бета, _, Оц),
дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц).
дост_хор( [ ], _, _, Поз, Оц, Поз, Оц) :- !.
% Больше нет кандидатов
дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-
ход_мина( Поз), Оц > Бета, !;
% Переход через верхнюю границу
ход_макса( Поз), Оц < Альфа, !.
% Переход через нижнюю границу
дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-
нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета),
% Уточнить границы
прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),
выбор( Поз, Оц, Поз1, Оц1, ХорПоз, ХорОц).
нов_границы( Альфа, Бета, Поз, Оц, Оц, Бета) :-
ход_мина( Поз), Оц > Альфа, !.
% Увеличение нижней границы
нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-
ход_макса( Поз), Оц < Бета, !.
% Уменьшение верхней границы
нов_границы( Альфа, Бета, _, _, Альфа, Бета).
выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-
ход_мина( Поз), Оц > Оц1, !;
ход_макса( Поз), Оц < Оц1, !.
выбор( _, _, Поз1, Оц1, Поз1, Оц1).
Рис. 15. 5. Реализация альфа-бета алгоритма.
возможен настолько неудачный порядок просмотра, что альфа-бета алгоритму придется пройти через все вершины, которые просматривались минимаксным алгоритмом полного перебора. Это означает, что в худшем случае альфа-бета алгоритм не будет иметь никаких преимуществ. Однако, если порядок просмотра окажется удачным, то экономия может быть значительной. Пусть N– число терминальных поисковых позиций, для которых вычислялись статические оценки алгоритмом минимаксного полного перебора. Было доказано, что в лучшем случае, когда самые сильные ходы всегда рассматриваются первыми, альфа-бета алгоритм вычисляет статические оценки только для N позиций.
Этот результат имеет один практический аспект, связанный с проведением турниров игровых программ. Шахматной программе, участвующей в турнире, обычно дается некоторое определенное время для вычисления очередного хода, и доступная программе глубина поиска зависит от этого времени. Альфа-бета алгоритм сможет пройти при поиске вдвое глубже по сравнению с минимаксным полным перебором, а опыт показывает, что применение той же оценочной функции, но на большей глубине приводит к более сильной игре.
Экономию, получаемую за счет применения альфа-бета алгоритма, можно также выразить в терминах более эффективного коэффициента ветвления дерева поиска (т. е. числа ветвей, исходящих из каждой внутренней вершины). Пусть игровое дерево имеет единый коэффициент ветвления, равный b. Благодаря эффекту отсечения альфа-бета алгоритм просматривает только некоторые из существующих ветвей и тем самым уменьшает коэффициент ветвления. В результате коэффициент b превратится в b (в лучшем случае). В шахматных программах, использующих альфа-бета алгоритм, достигается коэффициент ветвления, равный 6, при наличии 30 различных вариантов хода в каждой позиции. Впрочем, на этот результат можно посмотреть и менее оптимистично: несмотря на применение альфа-бета алгоритма, после каждого продвижения вглубь на один полуход число терминальных поисковых вершин увеличивается примерно в 6 раз.