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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

35
ние, но это уменьшение не повлияет на оценку вершины
+
0
W
, посколь-
ку последняя, опять же согласно минимаксному принципу, может
только увеличиваться. Таким образом, построение дерева можно пре-
рвать ниже вершины
−
4
W
, отсекая целиком выходящие из нее вторую
и третью ветви (и оставляя ее оценку предварительной).
На этом построение игрового дерева заканчивается, полученный
результат − лучший первый ход − тот же самый, что и при минимакс-
ной процедуре. У некоторых вершин дерева осталась не уточненная,
предварительная оценка, однако этих приближенных оценок оказалось
достаточно для того, чтобы определить точную минимаксную оценку
начальной вершины и наилучший первый ход. В то же время про-
изошло существенное сокращение поиска: вместо 17 вершин построе-
но только 11, и вместо 10 обращений к статической оценочной функ-
ции понадобилось всего 6.
Обобщим рассмотренную идею сокращения перебора. Сформу-
лируем сначала правила вычисления оценок вершин дерева игры, в
том числе предварительных оценок промежуточных вершин, которые
для удобства будем называть альфа- и бета-величинами:
− концевая вершина игрового дерева оценивается статической
оценочной функцией сразу, как только она построена;
− промежуточная вершина предварительно оценивается по ми-
нимаксному принципу, как только стала известна оценка хотя бы од-
ной из ее дочерних вершин; каждая предварительная оценка пересчи-
тывается (уточняется) всякий раз, когда получена оценка еще одной
дочерней вершины;
− предварительная оценка ИЛИ-вершины (альфа-величина) по-
лагается равной наибольшей из вычисленных к текущему моменту
оценок ее дочерних вершин;
− предварительная оценка И-вершины (бета-величина) полага-
ется равной наименьшей из вычисленных к текущему моменту оценок
ее дочерних вершин.
Укажем очевидное следствие этих правил вычисления: альфа-
величины не могут уменьшаться, а бета-величины не могут увеличи-
ваться.
Сформулируем теперь правила прерывания перебора, или от-
сечения ветвей игрового дерева.
А) Перебор можно прервать ниже любой И-вершины, бета-вели-
чина которой не больше, чем альфа-величина одной из предшествую-
щих ей ИЛИ-вершин (включая корневую вершину дерева).

Страницы