5.6.4 Метод альфа-бета отсечения

Метод «ветвей и границ» можно еще улучшить, если ввести не только верхнюю, но и нижнюю границу. Эта идея – ее называют минимаксной альфа-бета процедурой или просто альфа-бета отсечением – является значительным продвижением по сравнению с односторонним методом ветвей и границ. Определим процедуру f’’ с тремя параметрами p, alpha и beta (причем всегда будет выполнено alpha < beta), которая удовлетворяет следующим условиям:

f’’(p, alpha, beta)  alpha, если f(p) < alpha,

f’’(p, alpha, beta) = f(p), если alpha < f(p) < beta,

f’’(p, alpha, beta)  beta, если f(p)  beta.

Идею метода альфа-бета отсечения реализует следующий алгоритм.

function AB(p: position; alpha, beta: integer): integer;

{оценивает и возвращает выигрыш F’’(p) для позиции p}

var

m,i,t,d: integer;

begin

Определить позиции p1,...,pd, подчиненные p;

if d = 0 then AB := f(p) else begin

m := alpha;

for i:= 1 to d do begin

t := -AB(pi, -beta, -m);

if t > m then m := t;

if m >= beta then goto done;

end;

done: AB := m;

end;

end;

Листинг 5.18 – Алгоритм, использующий альфа-бета отсечение

Выгода от альфа-бета отсечения заключается в более раннем выходе из цикла. Эти отсечения полностью безопасны (корректны), потому что они гарантируют, что отсекаема часть дерева хуже, чем основной вариант.

При оптимальных обстоятельствах перебор с альфа-бета отсечением должен просмотреть W^(L+1)/2 + W^L/2 – 1 позицию, где W – среднее количество ходов в позиции, а L – количество уровней дерева. Это намного меньше, чем перебор с возвратом. Данное отсечение позволяет достигать примерно вдвое большей глубины за то же самое время.