Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) [Е. И. Большакова] (doc) читать постранично, страница - 13

вспомогательные функции: SELECT_MAX и AB_EVALP. Первая из этих функций была определена выше, она выбирает из своего аргумента-списка позицию с наибольшей оценкой.
Вторая функция, AB_EVALP - главная рекурсивная функция, которая эффективно оценивает вершины дерева игры по минимаксному принципу с выполнением отсечений. Она имеет пять аргументов: Pos, Depth, Deptype, Amax, Bmin, и на каждом шаге рекурсии вычисляет оценку вершины-позиции Pos, находящейся на глубине Depth и имеющей тип Deptype ("ИЛИ" при Deptype=Т и "И" при Deptype=()). Для проведения отсечений функция использует вспомогательные величины Amax и Bmin, являющиеся соответственно максимальной из альфа-величин и минимальной из бета-величин вершин, предшествующих оцениваемой вершине Pos. Значением функции AB_EVALP (как и MM_EVALP) является либо вычисленная оценка позиции Pos (при Depth>0), либо список дочерних для Pos позиций с их числовыми оценками (при Depth=0).
При первом обращении к функции AB_EVALP (внутри функции ALPHA_BETA) смысл ее аргументов такой: исходная позиция Pos (т.е. корневая вершина) имеет тип Т, находится на глубине 0, величины Amax и Bmin неизвестны. Эти величины необходимы для проверки условий правил отсечений, поэтому отсечения не могут быть выполнены, пока величины не определены (альфа-отсечение – пока неизвестна величина Bmin, а бета-отсечение – пока неизвестна Amaх ). Эти значения станут известны только лишь когда часть дерева игры будет просмотрена до заданной глубины.
Функция AB_EVALP (как и MM_EVALP) использует вспомогательные функции, определение которых зависит от конкретной игры: OPENING, вычисляющую для заданной позиции игры список дочерних вершин-позиций, и STAT_EST  статическую оценочную функцию.

[define AB_EVALP (lambda (Pos Depth Deptype Amax Bmin)
[prog (D (Movelist ()) Pvalue Dvalue)
 1: установка развилки из всех дочерних для Pos вершин (список () добавлен в развилку, чтобы "поймать" момент ее закрытия);
[set D [among ( ())]]
 2: если развилка закрыта, то возврат функцией подсчитанной оценки;
[cond ([empty .D]
[return [cond ([eq .Depth 0] .Movelist)
(t .Pvalue)] ] )]
 3: проверка возможности отсечения и отсечение - возврат на предыдущий уровень рекурсии (встроенная функция permex реализует досрочный выход с заданным значением из заданной функции, при этом уничтожает все развилки, возникшие после входа в заданную функцию);
[cond ([and [neq .Depth 0] [hasval Pvalue]]
[cond (.Deptype
[cond ([and [num .Bmin] [ge .Pvalue .Bmin]]
[permex .Pvalue AB_EVALP]) ])
(t
[cond ([and [num .Amax] [le .Pvalue .Amax]]
[permex .Pvalue AB_EVALP])] )])]
 4: вычисление оценки очередной дочерней вершины: либо применение статической оценочной функции, либо рекурсивное обращение к рассматриваемой функции;
[cond ([eq .Depth [- .N 1]]
[set Dvalue [STAT_EST .D]])
(t [set Dvalue [AB_EVALP .D [+ 1 .Depth]
[not .Deptype]
[cond ([and [hasval Pvalue] .Deptype]
[cond ([num .Amax] [max .Amax .Pvalue])
(t .Pvalue)])
(t .Amax)]
[cond ([and [hasval Pvalue] [not .Deptype]]
[cond ([num .Bmin] [min .Bmin .Pvalue])
(t .Pvalue) ])
(t .Bmin)] ]] )]
 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] ])]

Обе рассмотренные процедуры, MIN_MAX и ALPHA_BETA, должны быть соответствующим образом модифицированы, если при просмотре позиций на заданную глубину N возможно появление выигрышной или проигрышной позиции, обрывающих некоторые ветви игрового дерева. В этом случае к таким позициям необходимо сразу применить статическую оценочную функцию.
Заметим в заключении, что в случае выбора языка Лисп для реализации процедур поиска на игровых деревьях минимаксная процедура может быть запрограммировано весьма кратко и понятно, особенно при использовании функционалов. Что же касается альфа-бета процедуры, то программа на Лиспе [Уинстон, глава 13] существенно более громоздка и трудна для понимания, чем приведенная выше плэнер-функция, поскольку в последней применяется встроенный механизм возвратов.

​ Глава 4. Краткие сведения о языках Лисп и Плэнер
​ 4.1 Язык программирования Лисп
В языке Лисп все действия описываются в виде функций. С точки зрения синтаксиса, обращения к функциям, как и обрабатываемые ими данные, представ­ляют собой так называемые S-выражения. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном – список, который представляет собой заключенную в круглые скобки последовательность элементов списка. Лисповские списки имеют рекурсивную структуру, поскольку элементом списка может быть произвольное S-выражение – как атом, так и список. Примеры списков:
(()(a b 1(c))class)
(45 89 (()()))
Пустой список () имеет в Лиспе и другое обозначение – nil, причем он одновременно относится и к атомам, и к спискам.
Некоторые S-выражения можно вычислять, такие выражения называются формами. Простейшими формами