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

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

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

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

пошуку на фіксовану глибину можна досліджувати деякі галузі (послідовності дуг-ходів) дерева докладніше, скажемо, досліджувати до кінця розміни. Цікавий підхід запропонував у 1965 р. Р.Флойд [6], хоча поки що його не досліджували досить широко. Кожному ходу в схемі Флойда привласнюється деяке "правдоподібність" відповідно до наступного загальному плану. "Правдоподібність" змушеного ходу дорівнює 1, у той час як малоймовірним ходам (таким, як жертва ферзя в шахах) привласнюється "правдоподібність", рівне, скажемо, 0.01 чи біля того. У шахах відповідне узяття має правдоподібність, більше 0.5, а найгірші ходи - біля, скажемо, 0.02. Коли добуток правдоподібних ходів, що ведуть у деяку позицію, стає менше обраного порога - наприклад, менше 10-8), ця позиція розглядається як термінальна, пошук далі не ведеться й обчислюється її оцінка. У цій схемі "найбільш ймовірним" галузям дерева приділяється найбільша увага.
Який би метод ні використовувався для одержання дерева прийнятних розмірів, сама альфа-бета процедура припускає поліпшення, якщо ми уявляємо собі, чому може бути дорівнює оцінка вихідної позиції. Якщо ми думаємо, що оцінка позиції більше a і менше b, то замість F2(p, - , + ) ми можемо випробувати F2(p,a,b). Скажемо, у прикладі на мал. 3 можна замість F2(p,-10,+10) використовувати F2(p,0,4) - при цьому "-4" на рівні 3 і підлеглі позиції будуть відсічені. Якщо наше припущення вірне, ми відітнемо велику частину дерева; з іншого боку, якщо отримана оцінка виявиться занадто низкою, скажемо F2(p,a,b) = v, де v a, ми можемо повторити пошук з F2(p,- ,v), щоб одержати вірну оцінку. Ця ідея використана в деяких версіях шахової програми Гринблатта [8].
5. Історія
Перш ніж ми приступимо до кількісного аналізу ефективності альфа-бета процедури, коротко розглянемо основні етапи її розвитку. Її рання історія досить мрячна, тому що вона ґрунтується на недокументованих спогадах, а також тому, що іноді плутають процедуру F1 з більш могутньою процедурою F2, тому нижченаведений виклад використовує найбільш точну інформацію, доступний авторам.
Мак-Карти думав про подібний метод у 1965 р. під час Дартмутської літньої дослідницької конференції по штучному інтелекті, де Бернстайн розповів про одній із самих ранніх шахових програм [3], у якій не використовувалися ніякі відсікання. Мак-Карти "критикував за це програму, але не переконав Бернстайна. У той час специфікації алгоритму підготовлені не були". Дуже імовірно, що зауваження Мак-Карти, зроблені на цій конференції, привели до того, що наприкінці 50-х рр. альфа-бета відсікання стали використовувати в шахових програмах.
Першою публікацією, у якій містилося обговорення відсікань у дереві гри, була стаття Ньюелла, Саймона і Шоу [16] з описом їхньої ранньої шахової програми. Однак, вони привели приклади роботи лише "однобічного" методу, реалізованого в процедурі F1, так що неясно, чи були використані "нижні" відсікання.
Мак-Карти ввів ідентифікатори alpha і beta у своїй першій програмі на LISP'е, що реалізує цей метод. Його програма працювала навіть більш витончено, чим вищеописаний метод, оскільки він припускав існування двох функцій "оптимістична оцінка (p)" і "песимістична оцінка (p)", що доставляли верхню і нижню границі оцінки позиції. Програму Мак-Карти, що виконує тієї ж дії, що приведена вище процедура F2, можна представити в наступному виді:
if optimistic value(p) alpha then F2 := alpha
else if pessimistic value(p) beta then F2 := beta
else begin end.
Через ці додавання Мак-Карти вважав альфа-бета відсікання (можливо, що дає помилку) евристичним прийомом, не усвідомивши, що точне значення оцінки виходить, коли для всіх p
optimistic value(p) = +
і
pessimistic value(p) = -
Він подарував відкриття цього факту Харту і Эдвардсу, що у 1961 році підготували з цього приводу звіт [10]. У цьому неопублікованому звіті вони приводять приклади роботи загального методу, у тому числі, нижніх відсікань. Однак (як це було прийнято в 1961 р.), у ньому немає ні обґрунтування методу, ні вказівки умов, при яких він працює.
Перша публікація з описом альфа-бета відсікань з'явився російською мовою в 1963 р. зовсім незалежно від робіт американців. Брудно один з розроблювачів перших версій російської шахової програми, запропонував алгоритм, що збігається з альфа-бета методом, і дав - таки складне - доказ його правильності.
Повний опис альфа-бета відсікань з'явився в "західній" літературі по обчисленнях і комп'ютерам у 1968 р. у статті Слейгла і Бурського про стратегії доказу теорем, однак, цей опис страждало нечіткістю і не містило обговорення нижніх відсікань. Таким чином, можна затверджувати, що перший чіткий виклад методу англійською мовою з'явилося в 1969 р. у статтях Слейгла і Діксону [25] і Самуэля [22]; в обох статтях явно згадується можливість нижніх відсікань і обговорення ідеї включає необхідні деталі.
Практика показує, що дуже важко пояснити метод побудови альфа-бета відсікань "на словах" чи на звичайній математичній мові, тому автори цитованих вище робіт були змушені прибігати до довгих і складних описів. Більш того, при першому знайомстві з методом дуже важко змусити себе повірити в те, що він дійсно працює, особливо тоді, коли методи описують на "звичайному" мові і намагаються обґрунтувати можливість нижніх відсікань. Бути може, саме тому опис методу з'явився через багато років після того, як він був винайдений. Однак, у розд. 2 ми бачили, що метод легко зрозуміти й обґрунтувати, якщо виразити його алгоритмічною мовою; це являє гарний приклад случаючи, у якому "динамічний" підхід до опису процесу виявляється значно більш кращим, чим звичайний математичний.
Дуже добре метод описаний у недавніх книгах Нільсона [18, разд.4] і Слейгла [23, pp.16-24], однак, вони представляють метод "у прозі", а не в більш легкій для розуміння алгоритмічній формі. Альфа-бета відсікання стали "широко відомими", однак, наскільки відомо авторам, лише в двох публікаціях процедура описана алгоритмічною мовою. Насправді, у першій з них [27, раз. 4.3.3], Уеллс приводить не повну альфа-бета процедуру, а щось навіть більш слабке, чим процедура F1. (Його алгоритм не тільки не робить нижні відсікання, але і верхні відсікання робитьлише при виконанні строгої нерівності.) Інша версія алгоритму, що належить Далу і Белснису [5, разд. 8.1], з'явилася в недавно вийшли норвезькою мовою підручнику по структурах даних; однак, альфа-бета метод представлена в ній з використанням параметрів-міток, так що доказ правильності стає досить важким. В іншому недавньому підручнику міститься неформальний опис того, що там названо "альфа-бета відсіканнями", але знову приведений лише метод, реалізований процедурою F1; очевидно, багато хто не знають, що бета процедура здатна робити нижні відсікання. (Коли один з авторів статті (Д.Е.Батіг) близько 5 років тому проробив деякі дослідження, описані в розд. 7, він знав, що нижні відсікання можливі. Однак, процедуру F1 легко прийняти за "альфа-бета відсікання", про які говорять ваші колеги, так і не відкривши F2. -Прим. авторів.) Через усього цього автории даної статті упевнені в тім, що новий виклад методу виявиться корисним, - і це незважаючи на те, що альфа-бета відсікання використовують уже більш 15 років!
Loading...

 
 

Цікаве