Назад | Содержание| Вперёд 15. 3. Альфа-бета алгоритм:эффективная реализаци...

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

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

Программа, показанная на рис. 15.3, производитпросмотр в глубину дерева поиска, систематическиобходя все содержащиеся в нем позициивплоть до терминальных; она вычисляетстатические оценки всех терминальныхпозиций. Как правило, для того, чтобы получитьправильную минимаксную оценку корневой вершины,совсем не обязательно проделывать эту работуполностью. Поэтому алгоритм поиска можно сделатьболее экономным. Его можно усовершенствовать,используя следующую идею. Предположим, что у насесть два варианта хода. Как только мы узнали, чтоодин из них явно хуже другого, мы можем принятьправильное решение, не выясняя, на сколько вточности он хуже. Давайте используем этотпринцип для сокращения дерева поиска рис. 15.2.Процесс поиска протекает следующим образом:

    (1)        Начинаем спозиции  а.

    (2)        Переходим к  b.

    (3)        Переходим к  d.

    (4)        Береммаксимальную из оценок преемников позиции  d,  получаем  V( d) = 4.

    (5)        Возвращаемся к  b   и переходим к  е.

    (6)        Рассматриваем первого преемника позиции  е с оценкой 5. В этот момент МАКС (который как раз идолжен ходить в позиции  е) обнаруживает, что ему гарантирована в позиции е  оценка не меньшая, чем 5, независимо отоценок других (возможно, более предпочтительных)вариантов хода. Этого вполне достаточно для того,чтобы МИН, даже не зная точной оценки позиции  е,  понял, что для него в позиции  b  ходв  е  хуже, чем ход в  d.

На основании приведенного выше рассуждения мыможем пренебречь вторым преемником позиции  е  и приписать  е  приближенную оценку5. Приближенный характер этой оценки не окажетникакого влияния на оценку позиции  b,  а следовательно, и позиции  а.

На этой идее основан знаменитый альфа-бетаалгоритм, предназначенный для эффективнойреализации минимаксного принципа. На рис. 15.4показан результат работы альфа-бета алгоритма,примененного к нашему дереву рис. 15.2. Из рис. 15.4видно, что некоторые из рабочих оценок сталиприближенными. Однако этих приближенных оценококазалось достаточно для того, чтобы определитьточную оценку корневой позиции. Сложность поискауменьшилась до пяти обращений к оценочнойфункции по сравнению с восемью обращениями (впервоначальном дереве поиска рис. 15.2).

Как уже говорилось раньше, ключевая идеяальфа-бета отсечения состоит в том, чтобы найтиход не обязательно лучший, но "достаточнохороший" для того, чтобы принять правильноерешение. Эту идею можно формализовать, введя дваграничных значения, обычно обозначаемых через Альфаи Бета, между которыми должна заключатьсярабочая оценка позиции. Смысл этих граничныхзначений таков: Альфа -это самое маленькоезначение оценки, которое к настоящему моментууже гарантировано для игрока МАКС; Бета - этосамое большое значение оценки, на которое МАКСпока еще может надеяться. Разумеется, с точкизрения МИН'а, Бета является самым худшимзначением оценки, которое для него ужегарантировано. Таким образом, действительноезначение оценки (т. е. то, которое нужно найти)всегда лежит между Альфа и Бета. Если жестало известно, что оценка некоторой позициилежит вне интервала Альфа-Бета, то этогодостаточно для того, чтобы сделать вывод: даннаяпозиция не входит в основной вариант. При этомточное значение оценки такой позиции знать необязательно, его надо знать только тогда, когдаоценка лежит между Альфа и Бета."Достаточно хорошую" рабочую оценку  V(Р, Альфа, Бета)  позиции  Р  поотношению к Альфа и Бета можноопределить формально как любое значение,удовлетворяющее следующим ограничениям:

        V( P, Альфа, Бета) <=Альфа    если        V(P) <= Альфа

        V( P, Альфа, Бета) = V( P)          если        Альфа < V( P) < Бета

        V( P, Альфа, Бета) >=Бета      если        V( P) >= Бета

Рис. 15. 4.  Дерево рис. 15.2после применения альфа-бета алгоритма.

Пунктиром показаны ветви, отсеченные альфа-бетаалгоритмом

для экономии времени поиска. В результатенекоторые из

рабочих оценок стали приближенными (вершины  cеf;

сравните с рис.15.2). Однако этих приближенныхоценок

достаточно для вычисления точной оценкикорневой

вершины и построения основного варианта.

Очевидно, что, умея вычислять "достаточнохорошую" оценку, мы всегда можем вычислитьточную оценку корневой позиции  Р,  установив границы интервала следующим образом:

        V( Р, -бесконечность,+бесконечность)  =  V( P)

На рис. 15.5 показана реализация альфа-бетаалгоритма в виде программы на Прологе. Здесьосновное отношение -

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

где ХорПоз - преемник позиции Позс "достаточно хорошей" оценкой Оц,удовлетворяющей всем указанным вышеограничениям:

        Оц = 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 раз.

Проект

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

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









Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Наверх