Нижеследующий алгоритм вычисляет F(p) в соответствии с определением (1):
integer procedure F(position p):
begin integer m,i,t,d;
Определить позиции p1,...,pd, подчиненные p;
if d = 0 then F := f(p) else
begin m := -;
for i:= 1 step 1 until d do
begin t := -F(pi);
if t > m then m:= t;
end;
F := m;
end;
end.
Здесь + обозначает число, которое не меньше abs(f(p)) для любой терминальной позиции p; поэтому - не больше F(p) и -F(p) для всех p. Этот алгоритм вычисляет F(p) на основе "грубой силы": для каждой позиции он оценивает все возможные продолжения; "лемма о бесконечности" гарантирует окончание вычислений за конечное число ходов.
Перебор, который осуществляет этот алгоритм, можно уменьшить, используя идею метода "ветвей и границ". Идея состоит в том, что можно не искать точную оценку хода, про который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных раньше. Пусть, например, в процессе перебора стало известно, что F(p1) = -10. Мы заключаем отсюда, что F(p)>=10, и потому нам не нужно знать точное значение F(p2), если каким-либо образом мы как-то узнали, что F(p2)>=-1 (и, таким образом, что -F(p2)<=10). Итак, если p21 допустимый ход из p2 и F(p21)<=10, мы можем не исследовать другие ходы из p2. В терминах теории игр ход в позицию p2 "опровергается" (относительно хода в p1), если у противника в позиции p2 есть ответ, по крайней мере столь же хороший, как его лучший ответ в позиции p1. Ясно, что если ход можно опровергнуть, мы можем не искать наилучшее опровержение.
Эти рассуждения приводят к алгоритму, гораздо более экономному, чем F. Определим F1 как процедуру с двумя параметрами p и bound; наша цель - удовлетворить следующим условиям:
F1(p, bound) = F(p), если F(p) < bound, (6)
F1(p, bound) > bound, если F(p) > bound.
Эти условия не определяют F1 полностью, однако, позволяют вычислить F(p) для любой начальной позиции p, поскольку из них следует, что
F1(p,+ ) = F(p). (7)
Идею метода ветвей и границ реализует следующий алгоритм:
integer procedure F1(position p, integer bound):
begin integer m,i,t,d;
Определить позиции p1,...,pd, подчиненные p;
if d = 0 then F1 := f(p) else
begin m := -;
for i:= 1 step 1 until d do
begin t := -F1(pi, -m);
if( t > m then m := t;
if m >= bound then goto done;
end;
done: F1 := m;
end;
end.
Правильность работы этой процедуры и то, что результат удовлетворяет соот-ношениям (6), можно доказать следующими рассуждениями. Легко видеть, что в начале i-го витка for-оператора выполнено "инвариантное" условие
m = max { -F(p1), ..., -F(pi-1)}. (8)
Здесь предполагается, что максимум по пустому множеству даст -. Поэтому, если -F(pi) > m, то, используя условие (6) и индукцию по длине игры, начинающейся в p, получаем F1(pi,-m) = F(pi). Следовательно, в начале следующего витка (8) также будет выполнено. Если же max {-F(p1,...,-F(pi)} >= bound при всех i, то F(p) >= bound. Отсюда следует, что (6) выполняется для всех p.
Эту процедуру можно еще улучшить, если ввести не только верхнюю, но и нижнюю границу. Эта идея - ее называют минимаксной альфа-бета процедурой или просто альфа-бета отсечениями - является значительным продвижением по сравнению с односторонним методом ветвей и границ. (К сожалению, она применима не во всех задачах, где используется метод ветвей и границ; она работает только при исследовании игровых деревьев.) Определим процедуру F2 с тремя параметрами p, alpha и beta (причем всегда будет выполнено alpha < beta), которая удовлетворяет следующим условиям, аналогичным (6):
F2(p,alpha,beta) <= alpha, если F(p) < alpha, (9)
F2(p,alpha,beta) = F(p), если alpha < F(p) < beta,
F2(p,alpha,beta) >= beta, если F(p) >= beta.
И снова эти условия не определяют F2 полностью, однако, из них следует, что
F2(p,-, +) = F(p). (10)
Оказывается, представление этого улучшенного алгоритма на языке программирования лишь чуть-чуть отличается от алгоритмов F и F1:
integer procedure F2(position p, integer alpha, integer beta):
begin integer m,i,t,d;
Определить позиции p1,...,pd, подчиненные p;
if d = 0 then F2 := f(p) else
begin m := alpha;
for i:= 1 step 1 until d do
begin t := -F2(pi, -beta, -m);
if t > m then m := t;
if m >= beta then goto done;
end;
done: F2 := m;
end;
end.