begin integer m,i,t,d;

Визначити позиції p1,...,pd, підлеглі p;

if d = 0 then G2 := g(p) else

begin m := alpha;

for i:= 1 step 1 until d do

begin t := F2(pi, alpha, m);

if( t > m then m := t;

if mbeta then goto done;

end;

done: F2 := m;

end;

end.

Як легеню, але повчальної вправи пропонується довести, що G2(p,alpha,beta) завжди дорівнює -F2(p,-beta,-alhpa).

У приведених процедурах використовується чарівна підпрограма, що визначає позиції p1,...,pd, підлеглі позиції p. Якщо ми захочемо більш точно описати спосіб представлення позицій, нам природно використовувати списковую структуру. Нехай p є посилання на запис, що відповідає вихідної позиції, тоді first(p) є посилання на першу підлеглу чи позицію NULL (порожнє посилання), якщо позиція p термінальна. Аналогічно, якщо q є посилання на запис, що відповідає pi, те next(q) є посилання на наступну підлеглу позицію pi+1 чи NULL, якщо i = d. Нарешті, через generate(p) позначимо процедуру, що створює записи, що відповідають позиціям p1,...,pd, встановлює в цих записах полючи next і робить так, що first(p) указує на p1 чи дорівнює NULL, якщо d = 0. Тоді альфа-бета процедуру можна представити в наступній більш точній формі:

integer procedure F2(ref(position) p,integer alpha,integer beta):

begin integer m,t; ref(position) q;

generate(p);

q := first(p);

if q = NULL then F2 := f(p) else

begin m := alpha;

while qNULL and m < beta do

begin t := -F2(q, -beta, -m);

if t > m then m := t;

q := next(q);

end;

F2 := m;

end;

end.

Цікаво представити цю рекуррентну процедуру в ітеративному (нерекуррентному) вигляді і випробувати прості оптимізуючі перетворення, що зберігають коректність програми (див. [13]). Результуюча процедура дивно проста, хоча доказ її правильності не настільки очевидно, як для рекуррентного представлення:

integer procedure alphabeta(ref(position p);

begin integer l; comment level of recursion;

integer array a[-2:L];

comment stack for recursion where a[l-2], a[l-1], a[l]

denote respectively alpha, beta, m, -t in procedure F2;

ref (position) array r[0:L+1];

comment another stack for recursion where r[l] and r[l+1]

denote respectively p and q in F2;

l := 0; a[-2] := a[-1] := -; r[0] := p;

F2: generate(r[l]);

r[l+1] := first(r[l]);

if r[l+1] = NIL then a[l] := f(r[l]) else

begin a[l] := a[l-2];

loop: l := l+1; goto F2;

resume: if -a[l+1] > a[l] then

begin a[l] := -a[l+1];

if a[l+1]a[l-1] then go to done;

end;

r[l+1] := next(r[l+1]);

if r[l+1]NIL then goto loop;

end;

done: l := l-1; if l0 then goto resume;

alphabeta := a[0];

end.

Ця процедура обчислює те ж значення, що і F2(p,- ,+ ); значення L потрібно вибрати настільки великим, щоб рівень рекурсії ніколи не перевершував L.

4. Додатки

Розробляючи ігрову програму, ми рідко можемо сподіватися, що при оцінці чергового ходу вона зможе добиратися до термінальних вузлів - навіть альфа-бета відсікання недостатньо швидкі, щоб грати в "оптимальні" шахи! Проте, описані процедури застосовувати можна, якщо підпрограму, що генерує чергові позиції (ходи) змінити так, щоб досить глибокі позиції вона повідомляла термінальними. Нехай, наприклад, ми хочемо вести перебір на глибину в 6 напівходів (по 3 на кожного гравця). У цьому випадку ми можемо прикинутися, що в позиціях, що знаходяться на 6-м рівні від оцінюваної, немає припустимих ходів (тобто вони термінальні). Для обчислення оцінок таких "штучно термінальних" позицій нам потрібно, звичайно, використовувати всі можливі дані, усю нашу догадливість, сподіваючись при цьому, що досить глибокий пошук зм'якшить наслідку допущених помилок. (Велика частина часу роботи програми буде витрачена на обчислення таких здогадів, тому приходиться використовувати швидкі оцінки. Інша можливість полдягає в розробці генератора припустимих ходів, однак, ця задача надзвичайно важка.)

Замість пошуку на фіксовану глибину можна досліджувати деякі галузі (послідовності дуг-ходів) дерева докладніше, скажемо, досліджувати до кінця розміни. Цікавий підхід запропонував у 1965 р. Р.Флойд [6], хоча поки що його не досліджували досить широко. Кожному ходу в схемі Флойда привласнюється деяке "правдоподібність" відповідно до наступного загальному плану. "Правдоподібність" змушеного ходу дорівнює 1, у той час як малоймовірним ходам (таким, як жертва ферзя в шахах) привласнюється "правдоподібність", рівне, скажемо, 0.01 чи біля того. У шахах відповідне узяття має правдоподібність, більше 0.5, а найгірші ходи - біля, скажемо, 0.02. Коли добуток правдоподібних ходів, що ведуть у деяку позицію, стає менше обраного порога - наприклад, менше 10-8), ця позиція розглядається як термінальна, пошук далі не ведеться й обчислюється її оцінка. У цій схемі "найбільш ймовірним" галузям дерева приділяється найбільша увага.

Який би метод ні використовувався для одержання дерева прийнятних розмірів, сама альфа-бета процедура припускає поліпшення, якщо ми уявляємо собі, чому може бути дорівнює оцінка вихідної позиції. Якщо ми думаємо, що оцінка позиції більше a і менше b, то замість F2(p, - , + ) ми можемо випробувати F2(p,a,b). Скажемо, у прикладі на мал. 3 можна замість F2(p,-10,+10) використовувати F2(p,0,4) - при цьому "-4" на рівні 3 і підлеглі позиції будуть відсічені. Якщо наше припущення вірне, ми відітнемо велику частину дерева; з іншого боку, якщо отримана оцінка виявиться занадто низкою, скажемо F2(p,a,b) = v, де v a, ми можемо повторити пошук з F2(p,- ,v), щоб одержати вірну оцінку. Ця ідея використана в деяких версіях шахової програми Гринблатта [8].

5. Історія

Перш ніж ми приступимо до кількісного аналізу ефективності альфа-бета процедури, коротко