5.12. АЛЬФА-БЕТА ПРОЦЕДУРА

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

Рассмотрим дерево перебора, изображенное на рис. 5.12 (последний этап нашего перебора в игре тик-так-ту). Предположим, что концевая вершина оценивается, как только она построена. Тогда после построения и оценки вершины А нет

(кликните для просмотра скана)

(кликните для просмотра скана)

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

Рис. 5.13. Часть дерева первого этапа игры тик-так-ту.

Важно отметить, что тот факт, что вершины В, С и D не строятся, никак не может повлиять на ход, который окажется для игрока ПЛЮС наилучшим первым ходом.

В этом примере экономия затрат на перебор связана с тем, что позиция А выигрышна для игрока МИНУС. Однако экономии такого же типа можно добиться даже и тогда, когда ни одна из позиций дерева перебора не является выигрышной ни для игрока ПЛЮС, ни для игрока МИНУС.

Рассмотрим дерево для игры тик-так-ту, изображенное на рис. 5.10. Часть этого дерева воспроизведена на рис. 5.13. Предположим, что производится перебор на заданную глубину, и как только строится некоторая концевая вершина, вычисляется ее статическая оценка. Предположим также, что, как только позиции может быть приписана обращенная величина, эта величина

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

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

Это уменьшение затрат на перебор достигается благодаря прослеживанию предварительных обращенных величин. В общем случае, как только дочерним вершинам некоторой вершины приписаны обращенные величины, следует пересмотреть ПОВ этой вершины. Следует учесть, что

1) ПОВ «И» вершин (включая начальную вершину) не может уменьшаться.

2) ПОВ «ИЛИ» вершин не может увеличиваться.

Учитывая эти замечания, сформулируем следующие правила прерывания перебора:

а) Перебор можно прервать ниже любой «ИЛИ» вершины, ПОВ которой не больше, чем ПОВ любой предшествующей ей вершины «И» (включая начальную вершину). Этой вершине «ИЛИ» затем можно присвоить ее ПОВ в качестве окончательной обращенной величины.

б) Перебор может быть прерван ниже любой «И» вершины, ПОВ которой не меньше, чем ПОВ любой предшествующей ей «ИЛИ» вершины. Этой «И» вершине затем можно присвоить ее ПОВ в качестве окончательной обращенной величины.

(кликните для просмотра скана)

В процессе поиска ПОВ вычисляются следующим образом:

1) ПОВ для «И» вершины (включая начальную вершину) полагается равной наибольшей из имеющихся в данный момент обращенных величин ее дочерних вершин.

2) ПОВ для вершины «ИЛИ» полагается равной наименьшей из имеющихся в данный момент обращенных величин ее дочерних вершин.

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

Применение альфа-бета процедуры иллюстрируется на дереве, изображенном на рис. 5.14. Это дерево перебора, построенное на глубину 6. (Для удобства «И» вершины изображены квадратиками, а вершины «ИЛИ» — кружками.) Концевые вершины имеют указанные статические значения. Предположим, что мы ведем перебор с использованием альфа-бета процедуры. (Мы опять договариваемся строить в первую очередь вершины, расположенные слева.) Поддерево, получающееся в результате альфа-бета процедуры, выделено жирными линиями. Отсеченные вершины зачеркнуты. Заметим, что пришлось оценить только 18 из. первоначальных 41 вершин. Читатель может на этом примере проконтролировать свое понимание смысла альфа-бета процедуры, попробовав повторить перебор.