ii3 (Шпоры), страница 2

***********************************************************;

[define VALUE_POS (lambda (Position Depth Deptype)

[prog (D %дочерняя позиция;

(Movelist()) %список ходов(дочерних позиций);

Pvalue Dvalue) %оценки текущей и дочерней позиций;

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

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

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

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

[cond ([empty .D]

[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 - аналогичная функция проверки выполнения

условия альфа-отсечения ;

2