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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

33
дежные меры относительного достоинства промежуточных вершин,
чем оценки, полученные прямым применением статической оценочной
функции. Действительно, минимаксные оценки основаны на просмот-
ре игры вперед и учитывают разные особенности, которые могут воз-
никнуть в последующем, в то время как простое применение оценоч-
ной функции учитывает лишь свойства позиции как таковой. Это от-
личие статических и минимаксных оценок существенно для «актив-
ных», динамичных позиций игры (например, в шашках и шахматах к
ним относятся конфигурации, в которых возникает угроза взятия од-
ной или нескольких фигур). В случае же так называемых «пассивных»,
спокойных позиций статическая оценка может мало отличаться от
оценки по минимаксному принципу.
3.8.3. АЛЬФА-БЕТА ПРОЦЕДУРА
Минимаксная процедура организована таким образом, что про-
цесс построения частичного дерева игры отделен от процесса оцени-
вания вершин. Такое разделение приводит к тому, что в целом мини-
максная процедура − неэффективная стратегия поиска хорошего пер-
вого хода. Чтобы сделать процедуру более экономной, необходимо
вычислять статические оценки концевых вершин и минимаксные
оценки промежуточных вершин одновременно с построением игрово-
го дерева. Этот путь приводит к так называемой альфа-бета процеду-
ре поиска наилучшего первого хода от заданной позиции, при этом
можно добиться существенного сокращения вычислительных затрат,
прежде всего, времени вычисления статических оценок. В основе со-
кращения поиска лежит достаточно очевидное соображение: если есть
два варианта хода одного игрока, то худший в ряде случаев можно
сразу отбросить, не выясняя, насколько в точности он хуже.
Рассмотрим сначала идею работы альфа-бета процедуры на при-
мере игрового дерева, приведенного на рис. 7. Дерево игры строится
до глубины (N = 3) алгоритмом перебора вглубь. Причем сразу, как это
становится возможным, вычисляются не только статические оценки
концевых вершин, но и предварительные минимаксные оценки про-
межуточных вершин. Предварительная оценка определяется соответ-
ственно как минимум или максимум уже известных к настоящему мо-
менту оценок дочерних вершин. В общем случае, эта оценка может
быть получена при наличии оценки хотя бы одной дочерней вершины.
В ходе дальнейшего построения дерева игры и получения новых оце-
нок вершин предварительные оценки постепенно уточняются, опять
же по минимаксному принципу.
Пусть таким образом построены вершины
+−
21
, WW
и первые три
конечные вершины (листья) − см. рис. 8. Эти листья оценены статиче-

Страницы