Нехай, є два варіанти ходу. Довідавшись, що один з них явно гірший іншого, можна прийняти вірне рішення, не з'ясовуючи, наскільки він гірший.

Вибір( Поз0, Оц0, Поз1, Оц1, Поз1, Оц1).

Кращ( [Поз1 | СписПоз], КращаПоз, КращаОц) :- мінімакс( Поз1, _, Оц1),кращ( СписПоз, Поз2, Оц2), вибір( Поз1, Оц1, Поз2, Оц2, КращаПоз, КращаОц).

Кращ( [Поз], Поз, Оц) :- мінімакс( Поз, _, Оц), !.

Спрощена реалізація мінімаксного принципу

І

І

якщо P - позиція з ходом Макс'а.

 

V(Р) = mіn V(Рі ),

якщо Р - позиція з ходом Мін'а.

 

% Мінімаксна процедура: мінімакс(Поз,КращаПоз,Оц)

% Поз - позиція, Оц- її мінімаксна оцінка;

% кращий хід з Поз веде в позицію КращаПоз

% СписПоз- список дозволених ходів

 

мінімакс(Поз, КращаПоз, Оц) :-
ходи(Поз,СписПоз),!, кращ(СписПоз,КращаПоз,Оц);
стат_оц( Поз, Оц). % Поз не має спадкоємців

 

вибір( Поз0, Оц0, Поз1, Оц1, Поз0, Оц0) :-
хід_міна(Поз0), Оц0>Оц1, !;
%обирається кращою

позиція Поз0, якщо вона є позицієюз ходом Мін'а

хід_макса(Поз0),Оц0<Оц1,!.%обирається кращою

позиція Поз0, якщо вона є позицієюз ходом Макс'а

 

Основне відношення програми, що обчислює мінімаксну робочу оцінку для деякої заданої позиці -

мінімакс( Поз, КращаПоз, Оц)

де Оц - мінімаксна оцінка позиції Поз, а КращаПоз - найкраща позиція-спадкоємець позиції Поз (кращий хід, що дозволяє досягти оцінки Оц). Відношення

ходи( Поз, СписПоз)

задає дозволені ходи гри у списку СписПоз дозволених позицій-спадкоємців позиції Поз. Вважається, що ціль ходи неуспішна, якщо Поз є термінальною пошуковою позицією (листом дерева пошуку). Відношення

кращ( СписПоз, КращаПоз, КращаОц)

обирає зі списку позицій-кандидатів СписПоз "найкращу" позицію КращаПоз. КращаОц - оцінка позиції КращаПоз, а отже, і позиції Поз. Під "найкращою" оцінкою розуміють або максимальну, або мінімальну оцінку, залежно від того, із чиєї сторони очікується хід.

 

3. Альфа-бета-алгоритм: ефективна реалізація принципу мінімакса

§ Перегляд дерева пошуку вглиб, проглядаючи всі можливі позиції, аж до термінальних з обчисленням статичних оцінок всіх термінальних позицій.

§ Як правило, для одержання вірної мінімаксної оцінки кореневої вершини, цю роботу не обов'язково проробляти повністю.

§ Тому алгоритм пошуку можна вдосконалити, використавши наступну ідею.

 

Використаймо цей принцип для скорочення дерева пошуку рис.2. Процес пошуку протікає в такий спосіб:

(1) Почати з позиції а.

(2) Перейти вниз до позиції b.

(3) Перейти вниз до позиції d.

(4) Вибрати максимальну з оцінок спадкоємців позиції d, що дає V(d) = 4.

(5) Повернення до позиції b і далі спуск вниз до позиції е.

(6) Отримаємо оцінку 5 першого спадкоємця позиції е, згідно до якої для МАКСа (який має ходити в позиції е) гарантована оцінка не менша, чим 5, незалежно від оцінок інших (можливо, кращих) варіантів ходу. Цього цілком достатньо, щоб МІН, навіть не знаючи точної оцінки позиції е, в позиції b обрав саме хід в d.

На підставі наведеного можна приписати е наближену оцінку 5. Наближений характер цієї оцінки не зробить ніякого впливу на оцінку позиції b, а отже, і позиції а.

На цій ідеї заснований знаменитий альфа-бета алгоритм щодо ефективної реалізації мінімаксного принципу. Результат його застосування до дерева рис. 2 показано на рис. 3, з якого видно, що деякі з робочих оцінок стали наближеними. Однак їх вистачило для точної оцінки кореневої позиції при зменшенні складності пошуку (відносно первісного дерева пошуку рис. 2) з восьми до п'яти звернень до оцінюючої функції.

Рис. 3. Дерево рис. 2 після застосування альфа-бета алгоритму. Пунктиром показано гілки, відсічені альфа-бета алгоритмом для економії обсягу пошуку. У результаті деякі з робочих оцінок стали наближеними, однак це не завадило обчисленню точної оцінки кореневої вершини й побудови основного варіанта.

 

Отже, ключова ідея альфа-бета відсікання полягає в пошуку не обов'язково кращого, але "досить гарного" ходу для прийняття вірного рішення.

Формалізують ідею два граничних значення Альфа і Бета, між якими має бути робоча оцінка позиції:

§ Альфа - це найменше значення оцінки, яке на цей момент гарантовано для гравця МАКС;

§ Бета - це найбільше значення оцінки, на яке МАКС поки ще може сподіватись. Звісно, з погляду Мін'а, Бета є найгіршою гарантованою для нього оцінкою.

§ Отже, дійсне значення оцінки (яке потрібно знайти) завжди лежить між Альфа і Бета.

§ Якщо ж стало відомо, що оцінка деякої позиції лежить поза інтервалом Альфа-Бета, то цього досить для висновку: дана позиція не входить в основний варіант. При цьому не потрібне точне значення оцінки такої позиції, його треба знати лише тоді, коли оцінка лежить між Альфа і Бета.

§ "Досить гарну" робочу оцінку V(Р, Альфа, Бета) позиції Р можна визначити формально як будь-яке значення, що задовольняє наступним обмеженням:

V( P, Альфа, Бета) <= Альфа якщо V( P) <= Альфа

V( P, Альфа, Бета) = V( P) якщо Альфа < V( P) < Бета

V( P, Альфа, Бета) >= Бета якщо V( P) >= Бета

 

Вочевидь, що, вміючи обчислювати "досить гарну" оцінку, завжди можна обчислити точну оцінку кореневої позиції Р, встановивши границі інтервалу в такий спосіб:

 

V( Р, - нескінченність, + нескінченність) = V( P)

 

Нижче наведено реалізацію альфа-бета алгоритму у формі програми Прологу. Тут основне відношення –

 

альфабета(Поз, Альфа, Бета, ХорПоз, Оц)

 

де ХорПоз - спадкоємець позиції Поз із "досить гарною" оцінкою Оц, що задовольняє всім вказаним обмеженням:

 

Оц= V( Поз, Альфа, Бета)

 

Процедура

 

прибл_кращ( СписПоз, Альфа, Бета, ХорПоз, Оц)

 

знаходить досить гарну позицію ХорПоз у списку позицій СписПоз; Оц - наближена (стосовно Альфа і Бета) робоча оцінка позиції ХорПоз. Інтервал між Альфа і Бета може звужуватись (але не розширюватись!) у міру заглиблення пошуку при рекурсивних зверненнях до альфа-бета процедури. Відношення

 

нов_границі(Альфа,Бета,Поз,Оц,НовАльфа,НовБета)

 

визначає новий інтервал (НовАльфа,НовБета), завжди вужчий за старий (Альфа, Бета), або дорівнює йому. Так що, чим глибше заглиблюємось в дереві пошуку, тим сильніше стискається інтервал Альфа-Бета, і в результаті оцінювання позицій на глибших рівнях відбувається за вужчих границь. При більш вузьких інтервалах допускається більша "приблизність" в обчисленні оцінок, а отже, відсікається більше гілок дерева.

Виникає цікаве питання: наскільки великою є економія, що досягається альфа-бета алгоритмом порівняно із програмою мінімаксного повного перебору рис. 2?

Ефективність альфа-бета процедури залежить від порядку, у якому проглядаються позиції. Завжди краще першими розглядати найсильніші ходи з кожної з сторін.

 

% Альфа-бета алгоритм

альфабета(Поз,Альфа,Бета,ХорПоз,Оц):-

ходи(Поз,СписПоз),!,

прибл_кращ(СписПоз,Альфа,Бета,ХорПоз,Оц);