Альфа-бета відсікання при програмуванні комп’ютерних ігор
ВСТУП
При пошуку ходу в таких іграх, як шахи, програмам для ЕОМ необхідно робити перегляд великого дерева можливих продовжень. Щоб прискорити цей процес і не втратити інформацію, звичайно використовують метод, який називають альфа-бета відсіканнями. Нижче описуються результати аналізу цієї процедури, проведеного для того, щоб одержати хоч якісь чисельні оцінки якості її роботи.
Визначені основні поняття, зв'язані з деревом гри, описується процедура, називана альфа-бета відсіканнями (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]. Ідея полягає в тому, що можна не шукати точну оцінку ходу, про который стало відомо, що він не може бути краще, ніж один з ходів, розглянутих раніш. Нехай, наприклад, у процесі перебору стало