Нехай, є два варіанти ходу. Довідавшись, що один з них явно гірший іншого, можна прийняти вірне рішення, не з'ясовуючи, наскільки він гірший.
Вибір( Поз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?
Ефективність альфа-бета процедури залежить від порядку, у якому проглядаються позиції. Завжди краще першими розглядати найсильніші ходи з кожної з сторін.
% Альфа-бета алгоритм
альфабета(Поз,Альфа,Бета,ХорПоз,Оц):-
ходи(Поз,СписПоз),!,
прибл_кращ(СписПоз,Альфа,Бета,ХорПоз,Оц);