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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

32
3. В соответствии с минимаксным принципом вычисляются
оценки всех остальных вершин: сначала вычисляются оценки вершин,
родительских для концевых, затем родительских для этих родитель-
ских вершин и так далее; таким образом оценивание вершин происхо-
дит при движении снизу вверх по дереву поиска − до тех пор, пока не
будут оценены вершины, дочерние для начальной вершины, т.е. для
исходной конфигурации S.
Среди вершин, дочерних к начальной, выбирается вершина с наи-
большей оценкой: ход, который к ней ведет, и есть искомый наилуч-
ший ход в игровой конфигурации S.
На рисунке 7 показано применение минимаксной процедуры для
дерева игры, построенного до глубины (N = 3). Концевые вершины не
имеют имен, они обозначены своими оценками − значениями статиче-
ской оценочной функции. Числовые индексы имен остальных вершин
показывают порядок, в котором эти вершины строились алгоритмом
перебора вглубь. Рядом с этими вершинами находятся их минимакс-
ные оценки, полученные при движении в обратном (по отношению к
построению дерева) направлении. Таким образом, наилучший ход –
первый из двух возможных.
На рассматриваемом игровом дереве выделена ветвь (последова-
тельность ходов игроков), представляющая так называемую мини-
максно-оптимальную игру, при которой каждый из игроков всегда
выбирает наилучший для себя ход. Заметим, что оценки всех вершин
этой ветви дерева совпадают, и оценка начальной вершины равна
оценке концевой вершины этой ветви.
В принципе статическую оценочную функцию можно было бы
применить и к промежуточным вершинам, и на основе этих оценок
осуществить выбор наилучшего первого хода, например, сразу вы-
брать ход, максимизирующий значение статической оценочной функ-
ции среди вершин, дочерних к исходной. Однако считается, что оцен-
ки, полученные с помощью минимаксной процедуры, есть более на-
W
0
+
3
1
3
–1
W
2
+
3
W
3
+
4
4
W
1
−
−−
−
3
W
4
−
−−
−
0
3
2
W
5
+
3
1
–4
W
7
+
1
W
6
+
0
2
0
Рис. 7

Страницы