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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

30
окончание перебора вершин в игровом дереве: например, ограничива-
ется время перебора или же глубина поиска.
В построенном таким образом частичном дереве игры оценива-
ются вершины, и по полученным оценкам определяется наилучший
ход от заданной игровой конфигурации. При этом для оценивания
концевых вершин (листьев) полученного дерева используется так на-
зываемая статическая оценочная функция, а для оценивания
остальных вершин – корневой (начальной) и промежуточных между
корневой и концевыми вершинами – используется так называемый
минимаксный принцип.
Статическая оценочная функция, будучи применена к некоторой
вершине-конфигурации игры, дает числовое значение, оценивающее
различные достоинства этой игровой позиции. Например, для шашек
могут учитываться такие (статические) элементы конфигурации игры,
как продвинутость и подвижность шашек, количество дамок, контроль
ими центра и пр. По сути, статическая функция вычисляет эвристиче-
скую оценку шансов на выигрыш одного из игроков. Для определен-
ности будем рассматривать задачу выигрыша игрока ПЛЮС и соот-
ветственно поиска достаточно хорошего его первого хода от заданной
конфигурации.
Будем придерживаться общепринятого соглашения, по которому
значение статической оценочной функции тем больше, чем больше
преимуществ имеет игрок ПЛЮС (над игроком МИНУС) в оценивае-
мой позиции. Очень часто оценочная функция выбирается следующим
образом:
− статическая оценочная функция положительна в игровых кон-
фигурациях, где игрок ПЛЮС имеет преимущества;
− статическая оценочная функция отрицательна в конфигураци-
ях, где МИНУС имеет преимущества;
− статическая оценочная функция близка к нулю в позициях, не
дающих преимущества ни одному из игроков.
Например, для шашек в качестве простейшей статической функ-
ции может быть взят перевес в количестве шашек (и дамок) у игрока
ПЛЮС. Для игры «крестики-нолики» на фиксированном квадрате
возможна такая статическая оценочная функция:
( ) ( )
−++−++
−∞−
−∞+
=
−−−+++
,случаяхостальныхв
МИНУС;игрокавыигрышапозициясеть-если,
ПЛЮС;игрокавыигрышапозицияесть-если,
)(
DCLDCL
NNNNNN
Р
Р
PE
где +∞
∞∞
∞ − очень большое положительное число; −
−−
−∞
∞∞
∞ − очень маленькое
отрицательное число;
+++
DCL
NNN ,,
− соответственно число строк,

Страницы