5.14. КОМБИНИРОВАННЫЕ АЛЬФА-БЕТА ПРОЦЕДУРЫ И ПРОЦЕДУРЫ УПОРЯДОЧЕНИЯ

Сразу приходят на ум две процедуры построения дочерних вершин в той последовательности, которая оценивается как наилучшая.

Фиксиррванное упорядочение

Можно использовать процедуру перебора в глубину, в которой в первую очередь строится дочерняя вершина, оцениваемая как лучший ход (для любого игрока). Мы будем говорить, что в такой процедуре используется фиксированное упорядочение. Так, если, скажем, вершина 1 оценивается как наилучшая из дочерних вершин начальной вершины (с точки зрения игрока ПЛЮС), то следующей строится она, и она же выбирается для очередного раскрытия. Тогда если, скажем, вершина 11 оценивается как наилучшая из дочерних вершин вершины 1 (с точки зрения игрока МИНУС), то она строится следующей и выбирается для раскрытия. Этот процесс продолжается до тех пор, пока не будет достигнута концевая вершина, после чего становятся возможными отсечения. Перебор в глубину (с использованием альфа-бета процедуры) продолжается обычным образом, причем построение вершин по-прежнему производится в порядке их оцениваемого достоинства.

Оценку достоинства вершины можно производить различными способами. Для ранжирования дочерних вершин можно взять саму статическую оценочную функцию или, быть может, какую-нибудь более простую (и менее надежную) оценочную функцию. С другой стороны, под каждой из дочерних вершин можно произвести менее глубокий перебор, а потом упорядочить дочерние вершины, исходя из их обращенных величин, полученных в результате такого неглубокого перебора. Конечно, в каждом из этих методов следует сопоставить дополнительные затраты на перебор, связанные с упорядочением, с той экономией, которая вызывается возрастающим при этом числом отсечений ветвей в дереве перебора. Обычно для того, чтобы выбрать правильное соотношение между этими факторами, нужно произвести эксперимент.

Динамическое упорядочение

Достоинство описанной альфа-бета процедуры с фиксированным упорядочением заключается в том, что она довольно проста. Но может случиться, что в ходе перебора, идущего по определенному пути в дереве перебора, становится очевидно, что этот перебор следовало бы продолжить, отправляясь от некоторой более высокой вершины, которая теперь более эффективна. Осуществлять перебор в той части дерева, которая представляется наиболее перспективной, до тех пор пока не будет достигнута максимальная глубина, можно будет, слегка изменив алгоритм упорядоченного перебора на деревьях «И/ИЛИ». Мы будем говорить, что модифицированный алгоритм упорядоченного перебора использует в этом случае динамическое упорядочение.

Изменения весьма просты. На каждом этапе в процессе перебора в дереве перебора будут концевые вершины. Вместо того чтобы подсчитывать для этих вершин значения Н (измеряющие оцениваемую стоимость), можно для измерения достоинства соответствующих позиций игры привлечь некоторую оценочную функцию е. Тогда, по аналогии с подсчетом значений для неконцевых вершин дерева перебора будут вычисляться обращенные величины, или -значения. (Заметим, что стоимости дуг в дереве игры обычно не задаются; поэтому обращенные величины будут вычисляться точно так же, как в минимаксной про цедуре.)

На основе обращенных -значений в дереве выделяется цепочка наилучших ходов, ведущая к одной из его концевых вершин. Эта вершина и раскрывается в следующую очередь. (Наилучшим ходом под вершиной и будет выбор дочерней «ИЛИ» вершины, имеющей наибольшее обращенное -значение; наилучшим ходом под «ИЛИ» вершиной будет выбор дочерней «И» вершины, имеющей наименьшее обращенное -значение.) Когда в конечном итоге достигается максимальная глубина, у нас появляется возможность подсчитать предварительные обращенные величины, и тогда можно начать искать возможные отсечения. (Выполнение отсечений аналогично удалению вершин из списка ОТКРЫТ на шагах (7) и (12) алгоритма упорядоченного перебора (стр. 144, 145).)

Здесь снова можно оценить достоинства позиции, соответствующей этой концевой вершине дерева перебора, с помощью статической оценочной функции или посредством неглубокого перебора. Можно допустить также, чтобы до того, как будут производиться вычисления, связанные с получением нового дерева то, под вершиной, выбранной для раскрытия, вырастал целый кусок дерева. В ряде экспериментов (Слейджл и Диксон, 1969) на примере игры калах было показано, что метод альфа-бета, использующий определенный вид динамического упорядочения, более эффективен по сравнению с альфа-бета процедурой с фиксированным упорядочением или же (естественно) по сравнению с простой минимаксной процедурой без альфа-бета.