яний в процессе поиска и сократить время по сравнению с полным перебором. Кстати, этот подход достаточно распространен в экспертных продукционных системах.
Альфа-бета-процедура
Теоретически, это эквивалентная минимаксу процедура, с помощью которой всегда получается такой же результат, но заметно быстрее, так как целые части дерева исключаются без проведения анализа. В основе этой процедуры лежит идея Дж. Маккарти об использовании двух переменных, обозначенных и (1961 год).
Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся. Можно показать, что при определенных условиях некоторые вычисления являются лишними. Рассмотрим идею отсечения на примере рис. 3. 6. Предположим, позиция А полностью проанализирована и найдено значение ее оценки Допустим, что один ход из позиции Y приводит к позиции Z, оценка которой по методу минимакса равна z. Предположим, что . После анализа узла Z, когда справедливо соотношение , ветви дерева, выходящие из узла Y, могут быть отброшены (альфа-отсечение).
Рис. 3. 6. - отсечение
Если мы захотим опуститься до узла Z, лежащего на уровне произвольной глубины, принадлежащей той же стороне, что и уровень S, то необходимо учитывать минимальное значение оценки получаемой на ходах противника.
Отсечение типа можно выполнить всякий раз, когда оценка позиции, возникающая после хода противника, превышает значение Алгоритм поиска строится так, что оценки своих ходов и ходов противника сравниваются при анализе дерева с величинами и соответственно. В начале вычислений этим величинам присваиваются значения и , а затем, по мере продвижения к корню дерева, находится оценка начальной позиции и наилучший ход для одного из противн
Страницы: << < 4 | 5 | 6 | 7 | 8 > >>