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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

34
W
0
+
3
1
-1
3
W
2
+
3
W
3
+
4
4
W
1
3
3
2
W
4
3
W
5
+
3
Рис. 8
ской функцией, и вершина
+
2
W
получила точную минимаксную оцен-
ку 3, а вершина
−
1
W
− предварительную оценку 3. Далее при построе-
нии и раскрытии вершины
+
3
W
статическая оценка первой ее дочерней
вершины дает величину 4, которая становится предварительной оцен-
кой самой вершины
+
3
W
. Эта предварительная оценка будет потом,
после построения второй ее дочерней вершины, пересчитана. Причем,
согласно минимаксному принципу, оценка может только увеличиться
(поскольку подсчитывается как максимум оценок дочерних вершин),
но даже если она увеличится, это не повлияет на оценку вершины
−
1
W
,
поскольку последняя при уточнении по минимаксному принципу мо-
жет только уменьшаться (так как равна минимуму оценок дочерних
вершин). Следовательно, можно пренебречь второй дочерней верши-
ной для
+
3
W
, не строить и не оценивать ее, поскольку уточнение оцен-
ки вершины
+
3
W
не повлияет на оценку вершины
−
1
W
. Такое сокраще-
ние поиска в игровом дереве называется отсечением ветвей.
Продолжим для нашего примера процесс поиска в глубину с од-
новременным вычислением предварительных (и точных, где это воз-
можно) оценок вершин вплоть до момента, когда построены уже вер-
шины
−
4
W
,
+
5
W
и две дочерних последней, которые оцениваются ста-
тической функцией. Исходя из оценки первой дочерней вершины, на-
чальная вершина
+
0
W
, соответствующая исходной позиции игры, к
этому моменту уже предварительно оценена величиной 3. Вершина
+
5
W
получила точную минимаксную оценку 3, а ее родительская
−
4
W
получила пока только предварительную оценку 3. Эта предваритель-
ная оценка вершины
−
4
W
может быть уточнена в дальнейшем, и в со-
ответствии с минимаксным принципом возможно только ее уменьше-

Страницы