Введение в теорию игр. Жариков И.А - 36 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

36
В) Перебор можно прервать ниже любой ИЛИ-вершины, альфа-
величина которой не меньше, чем бета-величина одной из предшест-
вующих ей И-вершин.
При этом в случае А говорят, что имеет место альфа-отсечение,
поскольку отсекаются ветви дерева, начиная с ИЛИ-вершин, которым
приписана альфа-величина, а в случае В − бета-отсечение, поскольку
отсекаются ветви, начинающиеся с бета-величин.
Важно, что рассмотренные правила работают в ходе построения
игрового дерева вглубь; это означает, что предварительные оценки
промежуточных вершин появляются лишь по мере продвижения от
концевых вершин дерева вверх к корню и реально отсечения могут
начаться только после того, как получена хотя бы одна точная мини-
максная оценка промежуточной вершины.
В рассмотренном примере на рис. 5 первое прерывание перебора
было бета-отсечением, а второе − альфа-отсечением. Причем в обоих
случаях отсечение было неглубоким, поскольку необходимая для со-
блюдения соответствующего правила отсечения альфа- или бета-вели-
чина находилась в непосредственно предшествующей к точке отсече-
ния вершине. В общем же случае она может находиться существенно
выше отсекаемой ветви – где-то на пути от вершины, ниже которой
производится отсечение, к начальной вершине дерева, включая
последнюю.
После прерывания перебора предварительные оценки вершин в
точках отсечения остаются неуточненными, но, как уже отмечалось,
это не препятствует правильному нахождению предварительных оце-
нок всех предшествующих вершин, как и точной оценки корневой
вершины и ее дочерних вершин, а значит и искомого наилучшего пер-
вого хода.
На приведенных выше правилах вычисления оценок вершин
и выполнения отсечений (всюду, где это возможно) основана альфа-
бета процедура, являющаяся более эффективной реализацией мини-
максного принципа. В принципе, используя математическую индук-
цию и рассуждая аналогично рассмотренному примеру, несложно
доказать следующее.
Утверждение. Альфа-бета процедура всегда приводит к тому же
результату (наилучшему первому ходу), что и простая минимаксная
процедура той же глубины.
Важным является вопрос, насколько в среднем альфа-бета проце-
дура эффективнее обычной минимаксной процедуры. Нетрудно заме-
тить, что количество отсечений в альфа-бета процедуре зависит от
степени, в которой предварительные оценки (альфа- и бета-величины),
полученные первыми, аппроксимируют окончательные минимаксные
оценки: чем ближе эти оценки, тем больше отсечений и меньше пере-

Страницы