Лекция 17
Алгоритм
альфа-бета отсечения
Нижеследующий алгоритм вычисляет 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.
|