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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

37
бор. Это положение иллюстрирует пример на рис. 5, в котором ветвь
дерева с мини-максно-оптимальной игрой строится практически в
самом начале поиска.
Таким образом, эффективность альфа-бета процедуры зависит от
порядка построения и раскрытия вершин в дереве игры. Возможен и
неудачный порядок просмотра, при котором придется пройти без отсе-
чений через все вершины дерева, и в этом, худшем случае, альфа-бета
процедура не будет иметь никаких преимуществ против минимаксной
процедуры.
Наилучший случай, т.е. наибольшее число отсечений, достигает-
ся, когда при переборе в глубину первой обнаруживается конечная
вершина, статическая оценка которой станет впоследствии минимакс-
ной оценкой начальной вершины. При максимальном числе отсечений
строится и оценивается минимальное число концевых вершин. Пока-
зано, что в случае, когда самые сильные ходы всегда рассматриваются
первыми, количество концевых вершин глубины N, которые будут
построены и оценены альфа-бета процедурой, примерно, равно числу
концевых вершин, которые были бы построены и оценены на глубине
N
/
2 обычной минимаксной процедурой. Таким образом, при фикси-
рованном времени и памяти альфа-бета процедура сможет пройти
при поиске вдвое глубже по сравнению с обычной минимаксной
процедурой.
В заключение отметим, что статическая оценочная функция и
альфа-бета процедура − две непременные составляющие почти всех
компьютерных игровых программ (в том числе коммерческих). Часто
используются также дополнительные эвристические приемы в самой
альфа-бета процедуре:
− направленное (эвристическое) отсечение неперспективных
ветвей: например, построение дерева игры обрывается на «пассивных»
позициях, к которым применяется оценочная функция, для «активных»
же позиций поиск продолжается дальше, до нужной глубины или даже
глубже, поскольку на это можно использовать время, сэкономленное
вследствие отсечения ветвей;
− последовательное углубление, при котором альфа-бета проце-
дура применяется неоднократно: сначала до некоторой небольшой
глубины (например, 2), а затем глубина увеличивается с каждой ите-
рацией, причем после каждой итерации выполняется переупорядоче-
ние всех дочерних вершин – с тем, чтобы увеличить число отсечений в
последующих итерациях;
− фиксированное упорядочение вершин при спуске-построении
дерева вглубь, при котором в первую очередь строится и раскрывается
дочерняя вершина, оцениваемая как более перспективная (эта оценка

Страницы