стало відомо, що 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, оскільки з них випливає, що
(7) F1(p,+ ) = F(p).
Ідею методу галузей і границь реалізує наступний алгоритм:
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-оператора виконана "інваріантне" умова
(8) m = max { -F(p1), ..., -F(pi-1)}.
Тут передбачається, що максимум по порожній безлічі дасть - . Тому, якщо -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 цілком, однак, з них випливає, що
(10) F2(p,- , + ) = F(p).
Виявляється, представлення цього поліпшеного алгоритму мовою програмування лише мало-мало відрізняється від алгоритмів 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 mbeta then goto done;
end;
done: F2 := m;
end;
end.
3. Приклади й уточнення
Роботу цих процедур проілюструємо на прикладі дерева (мал. 1), з коренем у позиції з трьома підлеглими позиціями, у кожної з який також маються три підлеглі позиції, і т.д. доти, поки ми не одержимо 3**4 = 81 позицій, досяжних за 4 ходи. Цим термінальним позиціям приписані "випадкові" оцінки, що рівні першими 81 цифрам десяткового розкладання числа pi. Таким чином, корінь дерева (розташований угорі) має оцінку 2, рівну виграшу першого гравця, якщо обоє гравця роблять оптимальні ходи.
Рис.1. Цілком оцінене дерево гри.
На мал. 2 представлена ситуація, що відповідає перебору, що робить процедура F1. Помітимо, що з 81 термінальних позицій вона "відвідує" тільки 36. Крім того, одна з вершин 2-го рівня має "наближену" оцінку 3 замість щирого значення 7; ця приблизність, звичайно, не впливає на кінцеву оцінку кореня.
Рис.2. Дерево гри, представлене на мал. 1, після оцінки процедурою F1 (метод галузей і границь).
На мал. 3 представлена та ж задача, розв'язувана альфа-бета процедурою. Зверніть увагу на те, що F2(p,- , + ) завжди досліджує ті ж вузли, що і F1(p,+ ), поки не досягне вершин четвертого рівня; це є наслідок теорії, що нижче розвивається. На рівнях 4, 5, ..., однак, процедура F2 здатна робити "нижні відсікання", на які нездатна F1. Порівняння мал. 3 і мал. 2 показує, що в цьому прикладі зроблено 5 нижніх відсікань.
Рис3. Дерево гри, представлене на мал. 1, після оцінки процедурою F2 (альфа-бета стратегія).
Всі ілюстрації представлені в термінах "негативно-максимальної" моделі, розглянутої в розд. 1; тим, хто полюбляє "минимаксную" термінологію, досить ігнорувати на мал. 1-3 мінуси. Процедури розд. 2 легко представити в мінімаксному виді, замінивши, наприклад, F2 наступними двома процедурами:
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 := G2(pi, m, beta);
if t > m then m := t;
if mbeta then goto done;
end;
done: F2 := m;
end;
end;
integer
