Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні комп’ютерних ігор
ВСТУП
При пошуку ходу в таких іграх, як шахи, програмам для ЕОМ необхідно робити перегляд великого дерева можливих продовжень. Щоб прискорити цей процес і не втратити інформацію, звичайно використовують метод, який називають альфа-бета відсіканнями. Нижче описуються результати аналізу цієї процедури, проведеного для того, щоб одержати хоч якісь чисельні оцінки якості її роботи.
Визначені основні поняття, зв'язані з деревом гри, описується процедура, називана альфа-бета відсіканнями (alpha-beta pruning), і тісно зв'язаний з нею метод, однак, не настільки ефективний, оскільки він не робить "нижніх відсікань"; тут же доведена коректність обох методів.
У розд. є аналіз роботи методу - отримана нижня оцінка трудомісткості пошуку, необхідного чи процедурі будь-якому іншому алгоритму, що вирішує ту ж задачу. Верхня оцінка трудомісткості отримана на основі аналізу роботи з випадковими деревами, коли не виробляються нижні відсікання. Показано, що навіть у цих умовах можуть бути отримані розумні результати. В аналіз включені нижні відсікання, показано, що ефективність зростає, якщо між послідовними ходами мається зв'язок. Ця робота в значній мірі замкнута, лише в останніх розділах з'являється трошки математики.
1. Ігри й оцінки позицій
Ігри “один на один”, а тільки з ними ми і маємо тут справу, звичайно описують безліччю "позицій" і сукупністю правил переходу з однієї позиції в іншу, причому припускають, що гравці ходять по черзі. Будемо вважати, що правилами дозволені лише кінцеві послідовності позицій і що в кожній позиції мається лише кінцеве число дозволених ходів. Тоді для кожної позиції p знайдеться число N(p) таке, що ніяка гра, що почалася в p, не може продовжуватися більш N(p)..
Термінальними називаються позиції, з яких немає дозволених ходів. На кожній з них визначена цілочисельна функція f(p), що задає виграш того з гравців, якому належить хід у цій позиції; виграш другого гравця вважається рівним -f(p).
Якщо з позиції p є d дозволених ходів p1,...,pd, виникає проблема вибору кращого з них. Будемо називати хід найкращим, якщо по закінченні гри він приносить найбільший можливий виграш за умови, що супротивник вибирає ходи, найкращі для нього (у тім же змісті). Нехай F(p) є найбільший виграш, досяжний у позиції p гравцем, якому належить черга ходу, проти оптимального захисту. Т.к. після ходу в позицію pi виграш цього гравця дорівнює -F(pi), маємо
(1)
Ця формула дозволяє индуктивно визначити F(p) для кожної позиції p.
У більшості роботи з теорії ігор використовується ледве інше формулювання; у ній гравці називаються Max і Min і виклад ведеться з "точки зору" гравця Max. Таким чином, якщо p є термінальна позиція з ходом Max, його виграш дорівнює, як і раніш f(p), якщо ж у термінальній позиції p ходити повинен Min, те його виграш дорівнює
(2) g(p) = -f(p).
Max намагається максимізувати свій кінцевий виграш, а Min намагається мінімізувати його. Співвідношенню (1) при цьому відповідають дві функції, саме
(1') ,
що задає максимальний гарантований виграш гравця Max у позиції p, і
,
що дорівнює оптимуму, досяжному для гравця Min. Як і раніш, тут передбачається, що p1,...,pd є дозволені в позиції p ходи. Індукцією по числу ходів легко показати, що функції, обумовлені співвідношеннями (1) і (3), збігаються і що для всіх p
(5) G(p) = -F(p).
Таким чином, обидва підходи еквівалентні.
Т.к. нам звичайно легше оцінювати позиції з погляду одного якогось гравця, іноді зручніше використовувати "мінімаксний" підхід (3) і (4), а не міркувати в "плюс-мінус-максимальних" термінах співвідношення (1). З іншого боку, співвідношення (1) переважніше, коли ми хочемо довести що-небудь, - при цьому нам не приходиться досліджувати два (чи більше - по числу гравців) різних випадку.
Функція F(p) дорівнює тому максимуму, що гарантований, якщо обоє гравця діють оптимально. Випливає, однак, видно, що вона відбиває результати дуже обережної стратегії, що не обов'язково гарна проти поганих чи гравців гравців, що діють відповідно до іншого принципу оптимальності. Нехай, наприклад, є два ходи в позиції p1 і p2, причому p1 гарантує нічию (виграш 0) і не дає можливості виграти, у той час, як p2 дає можливість виграти, якщо супротивник перегляне дуже тонкий хід, що виграє. У такій ситуації ми можемо віддати перевагу ризикованому ходу в p2, якщо тільки ми не упевнені в тім, що наш супротивник всемогутній. Дуже можливо, що люди виграють у шахових програм у такий саме спосіб.
2. Розробка алгоритму
Нижченаведений алгоритм (на спеціально придуманій алголоподібній мові), мабуть, обчислює 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) на основі "грубої сили": для кожної позиції він оцінює всі можливі продовження; "лема про нескінченність" гарантує закінчення обчислень за кінцеве число ходів.
Перебір, що здійснює цей алгоритм, можна зменшити, використовуючи ідею методу "галузей і границь" [14]. Ідея полягає в тому, що можна не шукати точну оцінку ходу, про который стало відомо, що він не може бути краще, ніж один з ходів, розглянутих раніш. Нехай, наприклад, у процесі перебору стало відомо, що 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 m beta 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 m beta then goto done;
end;
done: F2 := m;
end;
end;
integer procedure G2(position p, integer alpha, integer beta):
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 m beta 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 q NULL 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 l 0 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. Історія
Перш ніж ми приступимо до кількісного аналізу ефективності альфа-бета процедури, коротко розглянемо основні етапи її розвитку. Її рання історія досить мрячна, тому що вона ґрунтується на недокументованих спогадах, а також тому, що іноді плутають процедуру F1 з більш могутньою процедурою F2, тому нижченаведений виклад використовує найбільш точну інформацію, доступний авторам.
Мак-Карти думав про подібний метод у 1965 р. під час Дартмутської літньої дослідницької конференції по штучному інтелекті, де Бернстайн розповів про одній із самих ранніх шахових програм [3], у якій не використовувалися ніякі відсікання. Мак-Карти "критикував за це програму, але не переконав Бернстайна. У той час специфікації алгоритму підготовлені не були". Дуже імовірно, що зауваження Мак-Карти, зроблені на цій конференції, привели до того, що наприкінці 50-х рр. альфа-бета відсікання стали використовувати в шахових програмах.
Першою публікацією, у якій містилося обговорення відсікань у дереві гри, була стаття Ньюелла, Саймона і Шоу [16] з описом їхньої ранньої шахової програми. Однак, вони привели приклади роботи лише "однобічного" методу, реалізованого в процедурі F1, так що неясно, чи були використані "нижні" відсікання.
Мак-Карти ввів ідентифікатори alpha і beta у своїй першій програмі на LISP'е, що реалізує цей метод. Його програма працювала навіть більш витончено, чим вищеописаний метод, оскільки він припускав існування двох функцій "оптимістична оцінка (p)" і "песимістична оцінка (p)", що доставляли верхню і нижню границі оцінки позиції. Програму Мак-Карти, що виконує тієї ж дії, що приведена вище процедура F2, можна представити в наступному виді:
if optimistic value(p) alpha then F2 := alpha
else if pessimistic value(p) beta then F2 := beta
else begin
Через ці додавання Мак-Карти вважав альфа-бета відсікання (можливо, що дає помилку) евристичним прийомом, не усвідомивши, що точне значення оцінки виходить, коли для всіх p
optimistic value(p) = +
і
pessimistic value(p) = -Він подарував відкриття цього факту Харту і Эдвардсу, що у 1961 році підготували з цього приводу звіт [10]. У цьому неопублікованому звіті вони приводять приклади роботи загального методу, у тому числі, нижніх відсікань. Однак (як це було прийнято в 1961 р.), у ньому немає ні обґрунтування методу, ні вказівки умов, при яких він працює.
Перша публікація з описом альфа-бета відсікань з'явився російською мовою в 1963 р. зовсім незалежно від робіт американців. Брудно один з розроблювачів перших версій російської шахової програми, запропонував алгоритм, що збігається з альфа-бета методом, і дав - таки складне - доказ його правильності.
Повний опис альфа-бета відсікань з'явився в "західній" літературі по обчисленнях і комп'ютерам у 1968 р. у статті Слейгла і Бурського про стратегії доказу теорем, однак, цей опис страждало нечіткістю і не містило обговорення нижніх відсікань. Таким чином, можна затверджувати, що перший чіткий виклад методу англійською мовою з'явилося в 1969 р. у статтях Слейгла і Діксону [25] і Самуэля [22]; в обох статтях явно згадується можливість нижніх відсікань і обговорення ідеї включає необхідні деталі.
Практика показує, що дуже важко пояснити метод побудови альфа-бета відсікань "на словах" чи на звичайній математичній мові, тому автори цитованих вище робіт були змушені прибігати до довгих і складних описів. Більш того, при першому знайомстві з методом дуже важко змусити себе повірити в те, що він дійсно працює, особливо тоді, коли методи описують на "звичайному" мові і намагаються обґрунтувати можливість нижніх відсікань. Бути може, саме тому опис методу з'явився через багато років після того, як він був винайдений. Однак, у розд. 2 ми бачили, що метод легко зрозуміти й обґрунтувати, якщо виразити його алгоритмічною мовою; це являє гарний приклад случаючи, у якому "динамічний" підхід до опису процесу виявляється значно більш кращим, чим звичайний математичний.
Дуже добре метод описаний у недавніх книгах Нільсона [18, разд.4] і Слейгла [23, pp.16-24], однак, вони представляють метод "у прозі", а не в більш легкій для розуміння алгоритмічній формі. Альфа-бета відсікання стали "широко відомими", однак, наскільки відомо авторам, лише в двох публікаціях процедура описана алгоритмічною мовою. Насправді, у першій з них [27, раз. 4.3.3], Уеллс приводить не повну альфа-бета процедуру, а щось навіть більш слабке, чим процедура F1. (Його алгоритм не тільки не робить нижні відсікання, але і верхні відсікання робить лише при виконанні строгої нерівності.) Інша версія алгоритму, що належить Далу і Белснису [5, разд. 8.1], з'явилася в недавно вийшли норвезькою мовою підручнику по структурах даних; однак, альфа-бета метод представлена в ній з використанням параметрів-міток, так що доказ правильності стає досить важким. В іншому недавньому підручнику міститься неформальний опис того, що там названо "альфа-бета відсіканнями", але знову приведений лише метод, реалізований процедурою F1; очевидно, багато хто не знають, що бета процедура здатна робити нижні відсікання. (Коли один з авторів статті (Д.Е.Батіг) близько 5 років тому проробив деякі дослідження, описані в розд. 7, він знав, що нижні відсікання можливі. Однак, процедуру F1 легко прийняти за "альфа-бета відсікання", про які говорять ваші колеги, так і не відкривши F2. -Прим. авторів.) Через усього цього автории даної статті упевнені в тім, що новий виклад методу виявиться корисним, - і це незважаючи на те, що альфа-бета відсікання використовують уже більш 15 років!