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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

31
столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще
может поставить три выигрышных крестика подряд);
−−−
DCL
NNN ,,
−
аналогичные числа для игрока МИНУС.
На рисунке 6 приведены две игровые позиции (на квадрате 4×4) и
соответствующие значения статической оценочной функции.
Подчеркнем, что с помощью статической оценочной функции
оцениваются только концевые вершины дерева игры, для оценок же
промежуточных вершин, как и начальной вершины, используется ми-
нимаксный принцип, основанный на следующей простой идее. Если
бы игроку ПЛЮС пришлось бы выбирать один из нескольких возмож-
ных ходов, то он выбрал бы наиболее сильный ход, т.е. ход, приводя-
щий к позиции с наибольшей оценкой. Аналогично, если бы игроку
МИНУС пришлось бы выбирать ход, то он выбрал бы ход, приводя-
щий к позиции с наименьшей оценкой.
Сформулируем теперь сам минимаксный принцип:
− ИЛИ-вершине дерева игры приписывается оценка, равная
максимуму оценок ее дочерних вершин;
− И-вершине игрового дерева приписывается оценка, равная
минимуму оценок ее дочерних вершин.
Минимаксный принцип положен в основу минимаксной проце-
дуры, предназначенной для определения наилучшего (более точно,
достаточно хорошего) хода игрока исходя из заданной конфигурации
игры S при фиксированной глубине поиска N в игровом дереве. Пред-
полагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина
есть ИЛИ-вершина). Основные этапы этой процедуры таковы.
1. Дерево игры строится (просматривается) одним из известных
алгоритмов перебора (как правило, алгоритмом поиска вглубь) от ис-
ходной позиции S до глубины N.
2. Все концевые вершины полученного дерева, т.е. вершины, на-
ходящиеся на глубине N, оцениваются с помощью статической оце-
ночной функции.
б)
Рис. 4
а)
O
X
E (P) = 8 - 5 = 3 E (P) = 6 - 4 = 2
X
O
O
X
X
X
Рис. 6
Е(Р) = 8 – 5 = 3 Е(Р) = 6 – 4 = 2

Страницы