PART3 (Печатные лекции), страница 5

Утверждение:

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

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

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

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

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

• направленное (эвристическое) отсечение неперспективных ветвей (например, построение дерева игры обрывается на «пассивных» позициях, к которым применяется оценочная функция, для «активных» же позиций поиск продолжается дальше, до нужной глубины или даже глубже, поскольку на это можно использовать время, сэкономленное вследствие отбрасывания ветвей);

• последовательное углубление, при котором альфа-бета процедура применяется неоднократно: сначала до некоторой небольшой глубины (например, 2), а затем глубина увеличивается с каждой итерацией, причем после каждой итерации выполняется переупорядочение всех дочерних вершин – с тем, чтобы увеличить число отсечений в последующих итерациях;

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

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

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

Плэнер-алгоритмы поиска на игровых деревьях

Рассмотрим сначала написанную на Плэнере функцию MIN_MAX, реализующую минимаксную процедуру. Аргументы этой функции: Instate  исходная позиция игры, для которой ищется наилучший ход; N  глубина поиска (т.е. количество ходов вперед). Вырабатываемое функцией значение  это дочерняя для Instate позиция, соответствующая наилучшему ходу.

[define MIN_MAX (lambda (Instate N)

[SELECT_MAX [MM_EVALP .Instate 0 T ]] )]

Функция MIN_MAX использует две вспомогательные функции: SELECT_MAX и MM_EVALP. Первая функция, SELECT_MAX выбирает из своего аргумента-списка List, каждый элемент которого – позиция (ход) и ее оценка, позицию (ход) с наибольшей оценкой:

[define SELECT_MAX (lambda (List)

[prog (Elem Max_elem )

[fin Max_elem .List]

SM [cond([fin Elem List] [return [2 .Max_elem]])

([gt [1 .Elem] [1 .Max_elem]]

[set Max_elem .Elem]) ]

[go SM] ] )]

Функция MM_EVALP с тремя аргументами является главной рекурсивной функцией, оценивающей вершины дерева игры по минимаксному принципу. На каждом шаге рекурсии она оценивает вершину-позицию Position, находящуюся на глубине Depth и имеющую тип Deptype ("ИЛИ" при Deptype=Т и "И" при Deptype=() ). Исходная позиция (корневая вершина) имеет тип Т и находится на глубине 0. Значением функции MM_EVALP является либо вычисленная оценка Position (при Depth>0 ) либо список ходов (точнее, дочерних для Position позиций) с их числовыми оценками (при Depth=0).

При работе MM_EVALP используются вспомогательные функции, определение которых зависит от конкретной игры: OPENING, вычисляющая для заданной позиции игры список дочерних вершин-позиций, и STAT_EST  статическая оценочная функция. Основные этапы вычислений предваряются комментарием.

[define MM_EVALP (lambda (Position Depth Deptype)

[prog (D %дочерняя позиция;

(Movelist()) %список ходов-позиций);

Pvalue Dvalue) %оценки текущей и дочерней

позиций;

% 1:установка развилки, включающей все дочерние вершины текущей позиции(список () добавлен в развилку, чтобы "поймать" момент ее закрытия);

[set D [among (<OPENING .Position> ())]]

% 2: если развилка закрыта - возврат функцией подсчитанной оценки;

[cond ([empty .D]

[return [cond ([eq .Depth 0] .Movelist)

(t .Pvalue) ]] )]

% 3: вычисление оценки очередной дочерней позиции: либо применение статической функции, либо рекурсивный спуск;

[cond ([eq .Depth [- .N 1]]

[set Dvalue [STAT_EST .D]])

(t [set Dvalue [MM_EVALP .D

[+ 1 .Depth]

[not .Deptype]]] )]

% 4:пересчет оценки текущей позиции по минимаксному принципу;

[cond ([hasval Pvalue] [pset Pvalue

[cond(.Deptype [max .Pvalue .Dvalue])

(t [min .Pvalue .Dvalue]) ]])

(t [pset Pvalue .Dvalue]) ]

% 5: при необходимости пересчет для исходной позиции списка ходов(дочерних позиций) с их оценками;

[cond([eq .Depth 0]

[pset Movelist(!.Movelist (.Dvalue .D)) ])]

% 6: возврат к другой альтернативе развилки;

[fail] ])]