WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні комп’ютерних ігор - Реферат

Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні комп’ютерних ігор - Реферат


Тут передбачається, що максимум по порожній безлічі дасть - . Тому, якщо -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) 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 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-м рівні від оцінюваної, немає припустимих ходів (тобто вони термінальні). Для обчислення оцінок таких "штучно термінальних" позицій нам потрібно, звичайно, використовувати всі можливі дані, усю нашу догадливість, сподіваючись при цьому, що досить глибокий пошук зм'якшить наслідку допущених помилок. (Велика частина часу роботи програми буде витрачена на обчислення таких здогадів, тому приходиться використовувати швидкі оцінки. Інша можливість полдягає в розробці генератора припустимих ходів, однак, ця задача надзвичайно важка.)
Замість
Loading...

 
 

Цікаве