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

Метод ветвей и границ

Перебор, который осуществляет поиск с возвратом, можно уменьшить, используя идею метода «ветвей и границ». Эта идея состоит в том, что можно не искать точную оценку хода, про который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных раньше. Пусть, например, в процессе перебора стало известно, что f (p ₁) = -10. Отсюда заключаем, что f (p) ³ 10, и потому не нужно знать точное значение f (p ₂), если каким-либо образом узнали, что f (p ₂) ³ -10 (поскольку отсюда следует, что - f (p ₂) £ 10). Итак, если p ₂₁ допустимый ход из p ₂ и f (p ₂₁) £ 10, можно не исследовать другие ходы из p ₂. Говорят, что ход в позицию p ₂«опровергается» (ходом в p ₁), если у противника в позиции p ₂ есть ответ, по крайней мере, столь же хороший, как его лучший ответ в позиции p ₁. Ясно, что если ход можно опровергнуть, можно не искать наилучшее опровержение.

Эти рассуждения приводят к методу «ветвей и границ», гораздо более экономному, чем поиск с возвратом. Определим метод «ветвей и границ» как процедуру с двумя параметрами p и bound, вычисляющую f ’(p, bound). Цель алгоритма – удовлетворить следующим условиям:

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

f ’(p, bound) > bound, если f (p) ³ bound.

Идею метода ветвей и границ реализует следующий алгоритм.

function B&B(p: position, bound: integer): integer;

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

label done;

var

m,i,t,d: integer;

begin

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

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

m:= -¥;

for i:= 1 to d do begin

t:= - B&B(pi, -m);

if t > m then m:= t;

if m >= bound then goto done;

end;

done: B&B:= m;

end;

end;

Листинг 5.17 – Алгоритм, использующий метод ветвей и границ

Метод «ветвей и границ» можно еще улучшить, если ввести не только верхнюю, но и нижнюю границу. Эта идея – ее называют минимаксной альфа-бета процедурой или просто альфа-бета отсечением – является значительным продвижением по сравнению с односторонним методом ветвей и границ. Определим процедуру 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 – количество уровней дерева. Это намного меньше, чем перебор с возвратом. Данное отсечение позволяет достигать примерно вдвое большей глубины за то же самое время.