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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

38
может быть проведена как с помощью статической оценочной функ-
ции, так и более простой, хотя и менее надежной эвристической функ-
ции);
− динамическое упорядочение вершин, при котором каждый
раз после уточнения минимаксных оценок и проведения отсечений
производится переупорядочивание вершин во всем построенном к
текущему моменту дереве (с помощью некоторой эвристической
функции) и для дальнейшего раскрытия выбирается наиболее перспек-
тивная вершина (заметим, что по существу это означает переход от
классического перебора вглубь к алгоритму упорядоченного перебора
на И/ИЛИ-графах).
Для усиления игры могут быть также использованы библиотеки
типовых игровых ситуаций.
3.8.4. ПЛЭНЕР-АЛГОРИТМ, РЕАЛИЗУЮЩИЙ
МИНИМАКСНУЮ ПРОЦЕДУРУ
Рассмотрим сначала написанную на плэнере функцию
MIN_MAX, реализующую минимаксную процедуру. Аргументы этой
функции: Instate − исходная позиция игры, для которой ищется наи-
лучший ход; N − глубина поиска, т.е. количество ходов вперед. Выра-
батываемое функцией значение − это дочерняя для Instate позиция,
соответствующая искомому наилучшему ходу:
[define MIN_MAX (lambda (Instate N)
[SELECT_MAX [MM_EVALP .Instate 0 T]])]
Функция MIN_MAX использует две вспомогательные функции:
SELECT_MAX и MM_EVALP. Первая функция, SELECT_MAX, вы-
бирает из своего единственного аргумента-списка, состоящего из по-
зиций и их оценок, позицию с наибольшей оценкой:
[define SELECT_MAX (lambda (List)
[prog (Elem Max_elem)
[fin Max_elem .List]
SM [cond([fin Elem List] [return [2 .Max_elem]])
([gt [1 .Elem] [1 .Max_elem]]
[set Max_elem .Elem]) ]
[go SM]])]
Функция MM_EVALP с тремя аргументами является главной ре-
курсивной функцией, оценивающей вершины дерева игры по мини-
максному принципу. На каждом шаге рекурсии она оценивает верши-
ну-позицию Position, находящуюся на глубине Depth и имеющую тип
Deptype: "ИЛИ" при Deptype=Т и "И" при Deptype=(). Исходная пози-
ция (корневая вершина дерева) имеет тип Т и находится на глубине 0.

Страницы