Википедија

Alfa-beta pretraga

Alfa-beta pretraga je algoritam za pretraživanje koji pokušava da smanji broj čvorova koji su dati od strane MINIMAX algoritma u stablu pretrage. Ovaj algoritam se često koristi za igre u kojima učestvuju dva igrača, kao što su X-O i Šah. Algoritam zaustavlja kompletnu pretragu ako naiđe na bar jedan potez koji može biti lošiji od prethodno ispitanih poteza. Takvi potezi se ne trebaju dalje ispitivati. Alfa-beta algoritam odstranjuje grane stabla koje ne mogu imati uticaj na konačni rezultat.[1][2][3]

Istorija уреди

Allen Newell i Herbert A. Simon su primenili ono što John McCarthy naziva "aproksimacija"[4] i 1958 su napisali da je alfa-beta "stvorena iznova više puta".[5] Arthur Samuel je imao raniju verziju, a Richards, Hart, Levine i/ili Edwards su samostalno prenosili alfa-beta u SAD.[6] McCarthy je predložio sličnu ideju za vreme Dartmouth konferencije održane 1956 koju je izneo grupi svojih studenata među kojima je bio Alan Kotok na MIT-u 1961.[7] Alexander Brudno je samostalno otkrio alfa-beta algoritam i svoje rezultate objavljuje 1963.[8] Donald Knuth i Ronald W. Moore su unapredili algoritam 1975[9][10], a Judea Pearl je dokazao njegovu optimalnost 1982 godine.[11]

Poboljšanja MINIMAX-a уреди

 
Ilustracija alfa-beta algoritma. Zatamljena podstabla nikada neće bita pretražena (kada se krene sa leva na desno). Max i min nivoi predstavljaju poteze igrača i njegovog protivnika.

Beneficija alfa-beta pretrage leži u činjenici da se neke grane stabla mogu eliminisati. Na ovaj način manje vremena može biti utrošeno na odgovarajuće podstablo, a u isto vreme se može izvršiti detaljna pretraga istog. Ako su čvorovi u pravilnom ili približno pravilnom redosledu, onda se dubina ove pretrage može smanjiti za pola (najbolji izbor početnog čvora).

Sa prosečnim (konstantnim) faktorom granjanja b, i dubljom pretragom d slojeva, maksimalni broj listova koje jedan čvor može da ima je O (b*b*...*b) = O(bd) – isto kao i kod MINIMAX pretrage. Ako je optimalan režim pretrage (prvobitno se traži najbolje moguće rešenje), procena broja listova čvorova je O(b*1*b*1*...*b) za dublju pretragu, za još detaljniju je O(b*1*b*1*...*1) ili  . U drugom slučaju, kada su slojevi pretrage jednaki, faktor granjanja pretrage je sveden na njegov kvadratni koren, ili ekvivalentno tome, pretraga može ići duplo dublje za isto vreme pretrage. Objašnjenje za b*1*b*1*... je to da prvi potez u pretrazi mora biti onaj najbolji, ali i svaki sledeći potez mora biti takav da pobije sve preostale mogućnosti(sem prve), prvi alfa-beta potez je toliko pouzdan da drugi potezi ne trebaju biti uzeti u obzir. Kada su čvorovi nasumično poređani, prosečan broj poteza se približno procenjuje sa  .[4]

Za vreme alfa-beta pretrage, podstabla su privremeno podređena prvom najboljem potezu ili obrnuto. Ova takozvana prednost može da menja strane pretrage više puta ako je redosled poteza netačan, sve ovo vodi do neefikasnosti. Kako broj pretraženih mesta eksponencijalno opada, svaki potez bliži trenutnoj poziciji je vredan svakog napora ranije izvršenih poteza.

Ovaj algoritam sadrži dve vrednosti, alfa i beta, koji predstavljaju minimalni i maksimalni rezultat koje igrači mogu da dobiju. Alfa je negativna, a beta je pozitivna beskonačnost. Kada beta postane manje od alfa, znači da trenutna pozicija ne može biti rezultat najboljeg poteza i tu se pretraga završava.

Alfa-beta algoritam može biti modifikovan da vraća čitavu glavnu varijaciju kao dodatak rezultatu. Drugi algoritmi kao što je MTD(f) ne dozvoljavaju takve modifikacije.

Pseudokod уреди 

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)

Istraživačka poboljšanja уреди

Dalja poboljšanja mogu biti postignuta korišćenjem istraživačke pretrage delova drveta koji će verovatno naterati alfa-beta algoritam da ranije završi sa radom. Na primer, u šahu, prvi igrač, pre nego što načini svoj potez može da razmotri da li uopšte i da ga načini, da li su ti koraci doveli do visokog rezultata u ranijoj fazi igre. Još jedan prost i jeftin način da se sprovede istraživanje jesu takozvana ubilačka istraživanja, gde poslednji potez koji prouzrokuje beta odsecanje, na istom nivou u pretrazi stabla se uvek ispituje prvo. Ova ideja se može naći u okviru tabela opovrgavanja.

Alfa-beta pretraga može biti još brža uzimajući u obzir mali pretraživački prostor (obično predstavljaju nagađanja na osnovu iskustva). U ekstremnom slučaju pretraga se može izvršiti uz pomoć alfa i beta jednačina, tehnika poznata kao nulta pretraga. Ovo je posebno korisno kod dobitnih/loših pretraga gde je dodatna širina pretrage dobijena iz uskog prozora i jednostavna pobednička/gubitnička evaluacija može dovesti do krajnjeg rezultata. U slučaju neuspešne pretrage mora se detektovati da li je greška velika ili mala. U zavisnosti od greške možemo znati odakle opet da krenemo(započnemo) pretragu.

Ostali algoritmi уреди

Napredniji algoritmi koji iako su brži u stanju su da izračunaju tačnu vrednost MINIMAX-a poznati su kao SCOUT,[12] Negascout i MTD-f.

S'obzirom da su MINIMAX algoritam i njegove varijacije svojstvene DFS pretrazi, strategija kao što je šira DFS pretraga se obicno koristi zajedno sa alfa-beta tako da se dobar potez može načiniti čak i ako je algoritam prekinut pre nego što je završio pretragu. Još jedna prednost ovog algorima jeste da pliće pretrage daju više nagoveštaja, kao i uže alfa-beta procene koje omogućuju odsecanje mnogo ranije nego što bi to inače bilo moguće.

Algoritam kao što je SSS*, koristi strategiju najbolji prvi potez. Ovo potencijalno može dovesti do viška vremena, ali uz visoku cenu prostorne efikasnosti.

Vidi još уреди

Reference уреди

  1. ^ Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (3rd изд.). Upper Saddle River, New Jersey: Pearson Education, Inc. стр. 167. ISBN 978-0-13-604259-4.. 
  2. ^ Heineman, George T., Gary Pollice, and Stanley Selkow (2008). „Chapter 7: Path Finding in AI”. Algorithms in a Nutshell. Oreilly Media. стр. 217—223. ISBN 978-0-596-51624-6. 
  3. ^ Judea Pearl, Heuristics, Addison-Wesley, 1984
  4. ^ а б McCarthy, John (27. 2. 2006). „Human Level AI Is Harder Than It Seemed in 1955”. Приступљено 20. 12. 2006. 
  5. ^ Newell, Allen & Herbert A. Simon (1976). „Computer Science as Empirical Inquiry: Symbols and Search” (PDF). Communications of the ACM. 19 (3). Архивирано из оригинала (PDF) 28. 06. 2007. г. Приступљено 21. 12. 2006. 
  6. ^ Edwards, D.J. & Hart, T.P. (4. 12. 1961). „The Alpha–beta Heuristic (AIM-030)”. Massachusetts Institute of Technology. Приступљено 21. 12. 2006. 
  7. ^ Kotok, Alan (3. 12. 2004). „MIT Artificial Intelligence Memo 41”. Архивирано из оригинала 06. 11. 2020. г. Приступљено 1. 7. 2006. 
  8. ^ Marsland, T.A. (1987). „Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)” (PDF). J. Wiley & Sons. стр. 159—171. Архивирано из оригинала (PDF) 6. 9. 2003. г. Приступљено 21. 12. 2006. 
  9. ^ * Knuth, D. E. & Moore, R. W. (1975). „An Analysis of Alpha–Beta Pruning” (PDF). Artificial Intelligence. 6 (4): 293—326. doi:10.1016/0004-3702(75)90019-3. [мртва веза]
  10. ^ Abramson, Bruce (1989). „Control Strategies for Two-Player Games”. ACM Computing Surveys. 21 (2): 137. doi:10.1145/66443.66444. Приступљено 20. 8. 2008. 
  11. ^ Pearl, Judea (1982). „The Solution for the Branching Factor of the Alpha–beta Pruning Algorithm and its Optimality”. Communications of the ACM. 25 (8): 559—564. 
  12. ^ Pearl, J., "SCOUT: A Simple Game-Searching Algorithm With Proven Optimal Properties," Proceedings of the First Annual National Conference on Artificial Intelligence, Stanford University, August 18–21, (1980). стр. 143-145.

Literatura уреди

Spoljašnje veze уреди

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