Википедија

Алфа-бета претрага

Алфа-бета претрага је алгоритам за претраживање који покушава да смањи број чворова који су дати од стране МИНИМАX алгоритма у стаблу претраге. Овај алгоритам се често користи за игре у којима учествују два играча, као што су X-О и Шах. Алгоритам зауставља комплетну претрагу ако наиђе на бар један потез који може бити лошији од претходно испитаних потеза. Такви потези се не требају даље испитивати. Алфа-бета алгоритам одстрањује гране стабла које не могу имати утицај на коначни резултат.[1][2][3]

Историја уреди

Аллен Неwелл и Херберт А. Симон су применили оно што Јохн МцЦартхy назива "апроксимација"[4] и 1958 су написали да је алфа-бета "створена изнова више пута".[5] Артхур Самуел је имао ранију верзију, а Рицхардс, Харт, Левине и/или Едwардс су самостално преносили алфа-бета у САД.[6] МцЦартхy је предложио сличну идеју за време Дартмоутх конференције одржане 1956 коју је изнео групи својих студената међу којима је био Алан Коток на МИТ-у 1961.[7] Алеxандер Брудно је самостално открио алфа-бета алгоритам и своје резултате објављује 1963.[8] Доналд Кнутх и Роналд W. Мооре су унапредили алгоритам 1975[9][10], а Јудеа Пеарл је доказао његову оптималност 1982 године.[11]

Побољшања МИНИМАX-а уреди

 
Илустрација алфа-бета алгоритма. Затамљена подстабла никада неће бита претражена (када се крене са лева на десно). Маx и мин нивои представљају потезе играча и његовог противника.

Бенефиција алфа-бета претраге лежи у чињеници да се неке гране стабла могу елиминисати. На овај начин мање времена може бити утрошено на одговарајуће подстабло, а у исто време се може извршити детаљна претрага истог. Ако су чворови у правилном или приближно правилном редоследу, онда се дубина ове претраге може смањити за пола (најбољи избор почетног чвора).

Са просечним (константним) фактором грањања б, и дубљом претрагом д слојева, максимални број листова које један чвор може да има је О (б*б*...*б) = О(бд) – исто као и код МИНИМАX претраге. Ако је оптималан режим претраге (првобитно се тражи најбоље могуће решење), процена броја листова чворова је О(б*1*б*1*...*б) за дубљу претрагу, за још детаљнију је О(б*1*б*1*...*1) или  . У другом случају, када су слојеви претраге једнаки, фактор грањања претраге је сведен на његов квадратни корен, или еквивалентно томе, претрага може ићи дупло дубље за исто време претраге. Објашњење за б*1*б*1*... је то да први потез у претрази мора бити онај најбољи, али и сваки следећи потез мора бити такав да побије све преостале могућности(сем прве), први алфа-бета потез је толико поуздан да други потези не требају бити узети у обзир. Када су чворови насумично поређани, просечан број потеза се приближно процењује са  .[4]

За време алфа-бета претраге, подстабла су привремено подређена првом најбољем потезу или обрнуто. Ова такозвана предност може да мења стране претраге више пута ако је редослед потеза нетачан, све ово води до неефикасности. Како број претражених места експоненцијално опада, сваки потез ближи тренутној позицији је вредан сваког напора раније извршених потеза.

Овај алгоритам садржи две вредности, алфа и бета, који представљају минимални и максимални резултат које играчи могу да добију. Алфа је негативна, а бета је позитивна бесконачност. Када бета постане мање од алфа, значи да тренутна позиција не може бити резултат најбољег потеза и ту се претрага завршава.

Алфа-бета алгоритам може бити модификован да враћа читаву главну варијацију као додатак резултату. Други алгоритми као што је МТД(ф) не дозвољавају такве модификације.

Псеудокод уреди 

function alphabeta(node, depth, α, β, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        for each child of node
            α := max(α, alphabeta(child, depth - 1, α, β, not(maximizingPlayer)))
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth - 1, α, β, not(maximizingPlayer)))
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, TRUE)

Истраживачка побољшања уреди

Даља побољшања могу бити постигнута коришћењем истраживачке претраге делова дрвета који ће вероватно натерати алфа-бета алгоритам да раније заврши са радом. На пример, у шаху, први играч, пре него што начини свој потез може да размотри да ли уопште и да га начини, да ли су ти кораци довели до високог резултата у ранијој фази игре. Још један прост и јефтин начин да се спроведе истраживање јесу такозвана убилачка истраживања, где последњи потез који проузрокује бета одсецање, на истом нивоу у претрази стабла се увек испитује прво. Ова идеја се може наћи у оквиру табела оповргавања.

Алфа-бета претрага може бити још бржа узимајући у обзир мали претраживачки простор (обично представљају нагађања на основу искуства). У екстремном случају претрага се може извршити уз помоћ алфа и бета једначина, техника позната као нулта претрага. Ово је посебно корисно код добитних/лоших претрага где је додатна ширина претраге добијена из уског прозора и једноставна победничка/губитничка евалуација може довести до крајњег резултата. У случају неуспешне претраге мора се детектовати да ли је грешка велика или мала. У зависности од грешке можемо знати одакле опет да кренемо(започнемо) претрагу.

Остали алгоритми уреди

Напреднији алгоритми који иако су бржи у стању су да израчунају тачну вредност МИНИМАX-а познати су као СЦОУТ,[12] Негасцоут и МТД-ф.

С'обзиром да су МИНИМАX алгоритам и његове варијације својствене ДФС претрази, стратегија као што је шира ДФС претрага се обицно користи заједно са алфа-бета тако да се добар потез може начинити чак и ако је алгоритам прекинут пре него што је завршио претрагу. Још једна предност овог алгорима јесте да плиће претраге дају више наговештаја, као и уже алфа-бета процене које омогућују одсецање много раније него што би то иначе било могуће.

Алгоритам као што је ССС*, користи стратегију најбољи први потез. Ово потенцијално може довести до вишка времена, али уз високу цену просторне ефикасности.

Види још уреди

Референце уреди

  1. ^ Русселл, Стуарт Ј.; Норвиг, Петер (2010). Артифициал Интеллигенце: А Модерн Аппроацх (3рд изд.). Уппер Саддле Ривер, Неw Јерсеy: Пеарсон Едуцатион, Инц. стр. 167. ISBN 978-0-13-604259-4.. 
  2. ^ Хеинеман, Георге Т., Гарy Поллице, анд Станлеy Селкоw (2008). „Цхаптер 7: Патх Финдинг ин АИ”. Алгоритхмс ин а Нутсхелл. Ореиллy Медиа. стр. 217—223. ИСБН 978-0-596-51624-6. 
  3. ^ Јудеа Пеарл, Хеуристицс, Аддисон-Wеслеy, 1984
  4. ^ а б МцЦартхy, Јохн (27. 2. 2006). „Хуман Левел АИ Ис Хардер Тхан Ит Сеемед ин 1955”. Приступљено 20. 12. 2006. 
  5. ^ Неwелл, Аллен & Херберт А. Симон (1976). „Цомпутер Сциенце ас Емпирицал Инqуирy: Сyмболс анд Сеарцх” (ПДФ). Цоммуницатионс оф тхе АЦМ. 19 (3). Архивирано из оригинала (ПДФ) 28. 06. 2007. г. Приступљено 21. 12. 2006. 
  6. ^ Едwардс, D.Ј. & Харт, Т.П. (4. 12. 1961). „Тхе Алпха–бета Хеуристиц (АИМ-030)”. Массацхусеттс Институте оф Тецхнологy. Приступљено 21. 12. 2006. 
  7. ^ Коток, Алан (3. 12. 2004). „МИТ Артифициал Интеллигенце Мемо 41”. Архивирано из оригинала 06. 11. 2020. г. Приступљено 1. 7. 2006. 
  8. ^ Марсланд, Т.А. (1987). „Цомпутер Цхесс Метходс (ПДФ) фром Енцyцлопедиа оф Артифициал Интеллигенце. С. Схапиро (едитор)” (ПДФ). Ј. Wилеy & Сонс. стр. 159—171. Архивирано из оригинала (ПДФ) 6. 9. 2003. г. Приступљено 21. 12. 2006. 
  9. ^ * Кнутх, D. Е. & Мооре, Р. W. (1975). „Ан Аналyсис оф Алпха–Бета Прунинг” (ПДФ). Артифициал Интеллигенце. 6 (4): 293—326. дои:10.1016/0004-3702(75)90019-3. [мртва веза]
  10. ^ Абрамсон, Бруце (1989). „Цонтрол Стратегиес фор Тwо-Плаyер Гамес”. АЦМ Цомпутинг Сурвеyс. 21 (2): 137. дои:10.1145/66443.66444. Приступљено 20. 8. 2008. 
  11. ^ Пеарл, Јудеа (1982). „Тхе Солутион фор тхе Бранцхинг Фацтор оф тхе Алпха–бета Прунинг Алгоритхм анд итс Оптималитy”. Цоммуницатионс оф тхе АЦМ. 25 (8): 559—564. 
  12. ^ Пеарл, Ј., "СЦОУТ: А Симпле Гаме-Сеарцхинг Алгоритхм Wитх Провен Оптимал Пропертиес," Процеедингс оф тхе Фирст Аннуал Натионал Цонференце он Артифициал Интеллигенце, Станфорд Университy, Аугуст 18–21, (1980). стр. 143-145.

Литература уреди

Спољашње везе уреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Alfa-beta_pretraga&oldid=26848717”