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

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

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

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

Альфа-бета відсіканя(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, якщо 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);
ift > 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)}.
Loading...

 
 

Цікаве