Интеллектуальные робототехнические системы

Альфа-бета-процедура


Теоретически, это эквивалентная минимаксу процедура, с помощью которой всегда получается такой же результат, но заметно быстрее, так как целые части дерева исключаются без проведения анализа. В основе этой процедуры лежит идея Дж. Маккарти об использовании двух переменных, обозначенных

и ? (1961 год).

Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся. Можно показать, что при определенных условиях некоторые вычисления являются лишними. Рассмотрим идею отсечения на примере рис. 3.6. Предположим, позиция А полностью проанализирована и найдено значение ее оценки

. Допустим, что один ход из позиции Y приводит к позиции Z, оценка которой по методу минимакса равна z. Предположим, что z
. После анализа узла Z, когда справедливо соотношение y
z
s, ветви дерева, выходящие из узла Y, могут быть отброшены (альфа-отсечение).

- отсечение

Рис. 3.6.  - отсечение

Если мы захотим опуститься до узла Z, лежащего на уровне произвольной глубины, принадлежащей той же стороне, что и уровень S, то необходимо учитывать минимальное значение оценки ?, получаемой на ходах противника.

Отсечение типа ? можно выполнить всякий раз, когда оценка позиции, возникающая после хода противника, превышает значение ?. Алгоритм поиска строится так, что оценки своих ходов и ходов противника сравниваются при анализе дерева с величинами

и ? соответственно. В начале вычислений этим величинам присваиваются значения +? и -?, а затем, по мере продвижения к корню дерева, находится оценка начальной позиции и наилучший ход для одного из противников.

Правила вычисления

и ? в процессе поиска рекомендуются следующие:

  1. у MAX вершины значение
    равно наибольшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин;
  2. у MIN вершины значение ? равно наименьшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин.

Правила прекращения поиска:

  1. можно не проводить поиска на поддереве, растущем из всякой MIN вершины, у которой значение ? не превышает значения
    всех ее родительских MAX вершин;
  2. можно не проводить поиска на поддереве, растущем из всякой MAX вершины, у которой значение
    не меньше значения ? всех ее родительских MIN вершин.




Начало  Назад  Вперед