Введение усечения альфа-бета

До сих пор наша программа была простой. Альфа-бета значительно ее усложняет, но это расширение будет проделано в несколько этапов.

Альфа-бета вносит некоторые усложнения

Прежде всего ясно, что MAPCAR в функции BIGGEST3 должна уйти, потому что функция SMALLEST3 может применяться, а может и не применяться ко всем позициям в списке, возвращаемом функцией PLAUSIBLE-MOVES (ДОПУСТИМЫЕ-ХОДЫ). Это зависит от значений, возвращаемых функцией SMALLEST3 по мере ее работы над указанным списком. Вся цель использования методики альфа-бета состоит в том, чтобы избежать рассмотрения малообещающих частей дерева или даже избежать генерирования таких частей дерева.

Использование функции PROG является одним из путей замены функции MAPCAR. При этом мы вводим явным образом циклы:

Как и прежде, рекурсия прекращается по сигналу от функции QUIET. В противном случае обращение к SMALLEST3 внутри PROG приводит к продолжению дерева. Ключевой переменной, привносимой функцией PROG, является BOARD-LIST (СПИСОК- ПОЗИЦИЙ), которая начинает свое существование как список всех непосредственных последователей BOARD (ПОЗИЦИЯ), найденных функцией PLAUSIBLE-MOVES. С каждым циклом BOARD-LIST сокращается, пока тест повторений, расположенный непосредственно после метки START, не покажет, что этот список позиций совершенно истощен. В этом случае итерации прекращаются, при этом возвращается окончательное значение величины NEW-LIST (НОВЫЙ-СПИСОК). Ясно, что NEW-LIST расширяется по мере сокращения списка BOARD-LIST. На каждой итерации передний элемент BOARD-LIST подается через NEXT-BOARD (СЛЕДУЮЩАЯ-ПОЗИЦИЯ) функции SMALLEST3, причем результирующая величина пересаживается в начало списка NEW-LIST. Если функция SMALLEST3 (НАИМЕНЬШИЙЗ) возвращает число, как и в предыдущих версиях, то NEW-LIST будет списком чисел. Функция PROG по окончании своей работы возвращает этот список, а МАХ выбирает наибольшее число из этого списка, которое будет значением функции BIGGEST3 (НАИБОЛЬШИЙ3).

Итак, позиции на игровой доске передаются далее и раскрываются с помощью функции PLAUSIBLE-MOVES (ДОПУСТИМЫЕ- ХОДЫ); списки чисел передаются назад и сокращаются путем использования минимаксной процедуры с помощью функций BIG- GEST3 и SMALLEST3. Эта часть осуществляется так же, как и прежде, с той лишь разницей, что путешествие по списку ходов, созданному функцией PLAUSIBLE-MOVES, осуществляется путем использования явного цикла в функции PROG, а не путем скрытого цикла, ранее осуществлявшегося посредством функции MAPCAR. Это изменение обусловлено необходимостью прерывать обследование списка с применением альфа-бета процедуры.

Далее. Мы знаем, что альфа-бета усечение основывается на сравнении вновь подсчитанных значений для поддерева с уже установленными минимумом и максимумом. Наш следующий вариант несколько обобщен для подготовки к такого рода сравнению. Указанные минимумы и максимумы передаются функции BIG- GEST4 через входные переменные

NEW-VALUE (НОВОЕ-ЗНАЧЕНИЕ) - это новая переменная, которая хранит значение, поступающее снизу через функцию SMALLEST4. Пока что ничего нового, все изменения носяг подготовительный характер.

Теперь мы имеем переменные ALPHA и BETA, но их значения нигде не устанавливаются и нигде не используются. Во-первых, при подготовке к их использованию в PROG была включена функция МАХ, так что некоторый еще не организованный тест может остановить итерации и привести к тому, что значение функции PROG станет значением функции BIGGEST5, а не список значений- кандидатов, которые должны быть подвергнуты сравнению друг с другом с использованием функции МАХ. Возвращаемой величиной является не NEW-LIST, как раньше, a BIGGEST-VALUE (НАИБОЛЬШЕЕ-ЗНАЧЕНИЕ). Несколько расточительно, здесь новые значения определяются на каждом шаге цикла, а не в момент выхода из него.

Далее, следующий шаг связан с некоторым действием. Найденное к настоящему моменту наибольшее значение сравнивается G величиной BETA.

Если найденное наибольшее значение больше, чем величина BETA, то это показывает, что дальнейшее изучение допустимых ходов ниже позиции, представленной переменной BOARD (ПОЗИЦИЯ), является бесполезным. Почему? Потому что обращение к функции BIGGEST6 вызвано минимизирующим случаем функции SMALLEST6, изучающей ходы, относительно которых известно, что они ведут к счету BETA. Если эта минимизирующая функция SMALLEST6, отстоящая на несколько шагов от применения функции BIGGEST6, знает, что ситуация в игре, предъявляемая BIGGEST6, такова, что она приводит к худшему счету, чем BETA, то было бы глупо изучать эту ситуацию дальше. Происходит отсечение, и возвращается найденное к настоящему моменту наибольшее значение, то, которое показывает, что данный ход не перспективен.

Значения альфа и бета передаются вниз и вверх по дереву

Поскольку теперь мы можем использовать ALPHA и BETA, следует уделить внимание установке их значений. Это непросто. Прежде всего, все BIGGEST7, которые используют значение BETA сверху, будут как раз теми функциями, которые устанавливают значение ALPHA, которое будет использоваться снизу. Это верно, потому что применение функции SMALLEST7, когда исследуются альтернативы, проистекающие из BOARD, будет приостановлено, если станет очевидно, что ситуация ведет к счету худшему, чем

тот, который, как известно BIGGEST7, достижим. Но лучший счет, известный функции BIGGEST7,- это наибольшее значение ALPHA, приходящее через список аргумента, и наибольшее значение NEW-VALUE, найденное к настоящему моменту. Иными словами, передаваемое далее ALPHA - это либо то, которое было получено, либо же наибольшее на данный момент значение переменной NEW-VALUE. Эго означает, что переменные BIGGEST- VALUE и NEW-VALUE могут быть исключены с соответствующей установкой ALPHA на каждом шаге цикла.

Теперь процедура альфа-бета работает прекрасно. Значение, возвращаемое в результате применения функции верхнего уровня, является правильным, а дерево исследуется не более, чем это необходимо. Один дефект, однако, остается: нет никакой возможности узнать, какой же ход является правильным! Мы забыли, что необходимо запомнить, какие ходы из списка допустимых лежат на минимаксной траектории игры. Следующая совокупность изменений подготавливает решение этой проблемы путем введения переменной MOVE-NUMBER (НОМЕР-ХОДА), значение которой возрастает на каждом шаге цикла.

Теперь в механизме цикла функции PROG имеется номер MOVE- NUMBER, указывающий, над каким элементом списка допустимых ходов ведется работа. Теперь легко выделить те ходы, которые приводят к максимальному счету, постольку, поскольку они приводят к изменению величины ALPHA. Эти новые дополнения будут использованы для описания минимаксной линии игры, потому что в следующей версии функция BIGGEST9 строит список номеров ходов, который определяет верную последовательность. Этот список начинается внизу дерева перебора величиной NIL, поскольку ниже нижнего узла ходов нет.

При движении назад от основания дерева необходимо лишь добавить что-то к значению переменной MOVE-NUMBER, задающей предполагаемый выигрышный ход на каждом уровне. Единственной трудностью является то, что список верных ходов не может быть передан наверх в качестве значения BIGGEST9 и SMALLEST9 ввиду того, что они уже используются для передачи минимаксных значений. Решение, хотя и не очень изящное, состоит в том, чтобы объединить минимаксное значение и траекторию в единый двухэлементный список, который и будет возвращаемой величиной.

В конце рекурсии срабатывание величины QUIET приводит к тому, что возвращается значение, состоящее из статической оценки вместе с пустым списком пути по дереву. При возвращении наверх требуется более сложная функция SETQ, чтобы установить значения для NEW-VALUE (НОВОЕ-ЗНАЧЕНИЕ) и MOVE-LIST (СПИСОК-ХОДОВ), поскольку эти значения должны быть распакованы (извлечены) из двухэлементных списков, возвращаемых снизу. Переменная RESULT (РЕЗУЛЬТАТ) состоит из минимаксного значения, NEW-VALUE и MOVE-LIST плюс MOVE-NUMBER. Прежде чем ее значение будет возвращено, оно может поменяться много раз. Заметим, что такое возвращение значения происходит либо когда этого потребует альфа-бета сравнение, либо когда список возможных ходов оказывается пустым. Разумеется, значение переменной RESULT должно быть изначально установлено на случай, если ни одно значение переменной NEW-VALUE не превзойдет начального значения ALPHA. Если такое произойдет, то значение ALPHA в переменной RESULT обеспечит то, что этот путь использоваться не будет, и поэтому список пути по дереву, содержащий NIL, никогда не будет обследоваться.

Следующие изменения по существу не принципиальны, добавляется лишь переменная подсчета глубины и функция печати. Функция QUIET может точно так же использовать переменную DEPTH (ГЛУБИНА), чтобы содействовать решению вопроса о том, следует ли разветвлять дерево дальше.

Теперь как будто все в порядке, но внимательный анализ показывает, что программа затыкается, если PLAUSIBLE-MOVES (ДОПУСТИМЫЕ-ХОДЫ) возвращает пустой список. Это легко исправить, включив тест на пустой список и возвращая, если такое произойдет, статическую оценку текущей позиции в игре. Этот тест реализован в функции BIGGEST11 в комбинации с тестом QUIET. Оба теста осуществляются в пределах функции PROG, так что BOARD-LIST (СПИСОК-ПОЗИЦИЙ) может быть установлен в то же самое время.

Одна функция может служить обоим игрокам

Наконец, можно использовать симметрию BIGGEST11 (НАИБОЛЬШИЙ) и SMALLEST11 (НАИМЕНЬШИЙ), объединив их в единую функцию, MINIMAX (МИНИМАКС). Это делается путем изменения в функции MINIMAX знака и порядка переменных ALPHA и BETA в ходе рекурсии вниз, а также изменения знака счета при движении в обратном направлении. Здесь используется тот факт, что минимизирующая и максимизирующая части пользуются одной стратегией, но имеют противоположные определения перспективного направления.

Статическое значение STATIC-VALUE становится теперь NEW-STATIC-VALUE (НОВОЕ-СТАТИЧЕСКОЕ-ЗНАЧЕНИЕ) с лишним аргументом, так что система статической оценки может взглянуть на ситуацию с правильной точки зрения.

Будучи примененной к нашему прежнему простому примеру, представленному в виде списка на языке Лисп,

((3) (1 4) ((1 5 9) 2))

функция MINIMAX дает следующее:

Для значительно более сложного дерева, представленного списком

мы имеем

Для определения функции PRINT-MESSAGE (ПЕЧАТЬ-СООБЩЕНИЯ) требуются новые элементарные функции. Подробности здесь приводятся для читателей, которым это интересно, но следует иметь в виду, что функции ввода-вывода в высшей степени зависят от реализации системы Лисп, если идти глубже функций READ и PRINT.

Функция TERPRI вызывает возврат каретки. Функция PRINC печатает атом, но в отличие от функции PRINT не производится возврат каретки и после атома не делается пропуск. Символы означают, что последующие пробелы не разделяют атомов. Так, странная строка символов /TRIMS/AWAY / (ОТБРАСЫВАЕТ) означает один атом, но с пробелами перед ним, после него и внутри.