Основные алгоритмы эвристического поиска (1156634), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

[return [cond ([eq .Depth 0] .Movelist)

(t .Pvalue) ]] )]

% 3: вычисление оценки очередной дочерней позиции ;

[cond ([eq .Depth [- .N 1]] [set Dvalue [STAT_EST .D]])

(t [set Dvalue [VALUE_POS .D

[+ 1 .Depth]

[not .Deptype]]] )]

% 4: пересчет предварительной оценки текущей позиции по

минимаксному принципу ;

[cond ([hasval Pvalue] [pset Pvalue

[cond(.Deptype [max .Pvalue .Dvalue])

(t [min .Pvalue .Dvalue]) ]])

(t [pset Pvalue .Dvalue]) ]

% 5: для исходной позиции пересчитываем список ходов

(дочерних позиций) с их оценками ;

[cond ([eq .Depth 0]

[pset Movelist (!.Movelist (.Dvalue .D)) ])]

% 6: возврат к другой альтернативе развилки ;

[fail] ] )]

%

SELECT_MAX - вспомогательная процедура выбора из списка List, содержащего ходы-позиции c их оценками, элемента с наибольшей оценкой

[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] ] )]

%

АЛЬФА-БЕТА ПРОЦЕДУРА. Instate - позиция игры, для которой ищется лучший ход. N - глубина поиска (количество ходов вперед). Значение функции ALPHA_BETA - дочерняя для Instate позиция, соответствующая наилучшему ходу

[define ALPHA_BETA (lambda (Instate N)

[SELECT_MAX [NEXT_MOVE .Instate 0 T () ]] )]

%

NEXT_MOVE - основная рекурсивная функция, которая оценивает позицию Pos, находящуюся на глубине Depth и имеющую тип Deptype ("И" при Deptype=Т и "ИЛИ" при Deptype=()). Последний аргумент функции, Way, - это список-путь из всех позиций (вместе с их предварительными оценками, если они уже есть), начиная от позиции, предшествующей Pos, двигаясь вверх в дереве игры до исходной позиции Instate.

Значение функции NEXT_MOVE:

• числовая оценка позиции Pos при Depth>0

• список ходов (точнее, дочерних для Pos позиций) с их числовыми оценками при Depth=0

При работе используются вспомогательные функции, определение которых зависит от конкретной игры:

• OPENING - вычисление списка дочерних вершин/позиций;

• STAT_EST - статическая оценка заданной позиции.

[define NEXT_MOVE (lambda (Pos Depth Deptype Way)

[prog(D (Movelist()) Pvalue Dvalue)

% 1: развилка, включающая все дочерние позиции ( список ()

добавлен в развилку, чтобы "поймать" момент ее закрытия);

[set D [among (<OPENING .Pos> ())]]

% 2: закрытие развилки и возврат подсчитанной оценки ;

[cond ([empty .D]

[return[cond([eq .Depth 0] .Movelist)

(t .Pvalue)] ] )]

% 3: проверка возможности отсечения и отсечение-возврат на

предыдущий уровень рекурсии (встроенная функция tempex

реализует досрочный выход с заданным значением из заданной

функции, при этом уничтожает все развилки и выполняет все

обратные операторы,возникшие после входа в заданную функцию;

[cond([and [neq .Depth 0] [hasval Pvalue]]

[cond(.Deptype [cond([NOT_LESS .Pvalue .Way]

[темрex .Pvalue NEXT_MOVE])])

(t [cond([NOT_GREATER .Pvalue .Way]

[темрex .Pvalue NEXT_MOVE])] )])]

% 4: вычисление оценки очередной дочерней позиции ;

[cond ([eq .Depth[- .N 1]] [set Dvalue [STAT_EST .D]])

(t [set Dvalue [NEXT_MOVE .D [+ 1 .Depth]

[not .Deptype]

[cond([hasval Pvalue]

((.Pvalue .Pos) !.Way))

(t ((.Pos) !.Way))] ]])]

% 5: пересчет предварительной оценки текущей позиции по

минимаксному принципу ;

[cond([hasval Pvalue] [Pset Pvalue

[cond(.Deptype[max .Pvalue .Dvalue])

(t [min .Pvalue .Dvalue])] ])

(t[pset Pvalue .Dvalue] )]

% 6: для начальной позиции пересчитываем список ходов

(дочерних позиций) с их оценками ;

[cond([eq .Depth 0]

[pset Movelist (!.Movelist(.Dvalue .D))] )]

% 7: возврат к другой альтернативе развилки ;

[fail] ] )]

%

NOT_LESS - вспомогательная функция проверки выполнения условия бета-отсечения, List - список предыдущих позиций с оценками (если они есть).

Замечание: вместо условия [eq[length .Elem]2] (имеет ли позиция-элемент списка List предварительную оценку?) можно использовать более эффективное [num[1 .Elem]] , эти условия эквивалентны, если описание позиции для конкретной игры имеет списочный вид

[define NOT_LESS (lambda (Value List)

[prog (Elem)

[fin Elem List]

NL [cond([and [eq[length .Elem]2] [le[1 .Elem] .Value]]

[return t] )

([fin Elem List] [return ()] )

([fin Elem List] [return ()] )]

[go NL] ] )]

%

NOT_GREATER - аналогичная функция проверки выполнения условия альфа-отсечения

[define NOT_GREATER (lambda (Value List)

[prog (Elem)

[fin Elem List]

NG [cond([and [eq[length .Elem]2] [ge[1 .Elem] .Value]]

[return t] )

([fin Elem List] [return ()] )

([fin Elem List] [return ()] )]

[go NG] ] )]

Характеристики

Список файлов ответов (шпаргалок)