Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Вибір(Поз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?

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

 

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

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

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

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




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 336; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.023 сек.