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

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

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

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

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

Список файлов учебной работы