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

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

На примере, приведенном на рис. 6.8, поясняется идея процедуры отсечения. Предположим, что узел 5 соответствует позиции, в которой ход принадлежит нам. При этом в нашем распоряжении несколько возможных ходов, два из которых показаны на рисунке. В результате одного из них возникает позиция А, в результате другого — позиция Предположим также, что позиция А уже полностью проанализирована и найдено значение ее оценки Перейдем к анализу позиции Допустим, что один ход из этой позиции приводит к позиции оценка которой (полученная по методу минимакса) равна 2.

Предположим далее, что . Кроме того, пусть величина и у являются значениями оценки в узлах и Тогда в любом случае выполняется неравенство поскольку в

Рис. 6.8. Неглубокое альфа-отсечение.

позиции ход за противником, который из всех возможных ходов выбирает такой, который приводит к позиции с минимальной оценкой.

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

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

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

Рис. 6.9. Глубокое отсечение.

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

Рассмотрим позицию V. Не анализ может привести к двум различным результатам: или Очевидно, что в первом случае результаты анализа других ходов не могут привести к изменению значения оценки так как уже известно, что у 2, а величина у в результате такого анализа может быть только уменьшена. Во втором случае справедливо равенство отсюда с учетом предыдущих неравенств имеем , т. е. узел V получает меньшую по величине оценку, чем узел А, и таким образом опять возвращаемся к схеме, приведенной на рис. 6.8. Окончательно получаем, что в обоих случаях оценка позиции не зависит от других ветвей дерева, выходящих из узла У, и анализ последних может не проводиться (глубокое отсечение типа а).

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

Рис. 6.10. (см. скан) Альфа — бета-процедура отсечения дерева, приведенного на рис. 6.6

анализа позиций на нисходящих ветвях дерева служит уже минимальное значение оценки Отсечение типа можно выполнить всякий раз, когда оценка позиции, возникшей после хода противника (обозначим ее со), превышает значение Алгоритм поиска строится так, что при анализе дерева оценки своих ходов и ходов противника сравниваются с величинами а и Р соответственно. В начале вычислений этим величинам присваиваются значения плюс и минус бесконечности, а затем, по мере восхождения к корню дерева по описанной выше схеме, находится оценка начальной позиции и наилучший ход для одного из противников (рис. 6.10 и табл. 6.3).

Таблица 6.3 (см. скан)

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

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

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

В заключение отметим одно интересное свойство: алгоритм находит тем больше ходов за определенное время, т. е. является тем более производительным, чем более упорядоченно расположены вершины при отыскании каждого хода. В идеальном случае (естественно, недостижимом на практике) вершины на каждом уровне должны располагаться по монотонно убывающим значениям оценки. Для приближения к идеальному случаю в некоторых программах, прежде чем применить алгоритм до глубины, например, 6, сначала используется этот алгоритм до глубины 2, после чего на основе полученных результатов выполняется упорядочивание узлов. Затем вновь проводится анализ уже до глубины, например 3, производится новое упорядочивание, и только после этого алгоритм применяется к полной глубине 6. Два первых захода, в течение которых обрабатывается небольшое число вершин, выполняются очень быстро и позволяют заметно приблизиться к идеальному упорядочению вершин, для уровня 6. При этом полное время вычислений сокращается по сравнению со случаем выполнения анализа сразу на всю глубину без предварительной подготовки.