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.

Istorija 
Allen Newell i Herbert A. Simon su primenili ono što John McCarthy naziva "aproksimacija" i 1958 su napisali da je alfa-beta "stvorena iznova više puta". Arthur Samuel je imao raniju verziju, a Richards, Hart, Levine i/ili Edwards su samostalno prenosili alfa-beta u SAD. 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. Alexander Brudno je samostalno otkrio alfa-beta algoritam i svoje rezultate objavljuje 1963. Donald Knuth i Ronald W. Moore su unapredili algoritam 1975, a Judea Pearl je dokazao njegovu optimalnost 1982 godine.

Poboljšanja MINIMAX-a 

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
.

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, 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š 
 Pruning (algoritam)
 Raznovrsni optimalni algoritam (Branch and bound)
 Minimax
 Kombinatorne optimizacije
 Negamax
 Prenošenje tabela

Reference

Literatura

Spoljašnje veze 

 http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm
 http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_5B_McCullough_Melnyk/
 http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L2_5B_Lima_Neitz/search.html
 https://web.archive.org/web/20021223103359/http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html
 https://web.archive.org/web/20041123061044/http://chess.verhelst.org/search.html
 http://www.frayn.net/beowulf/index.html
 http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf
 Minimax (with or without alpha–beta pruning) algorithm visualization - game tree solving (Java Applet), for balance or off-balance trees 
 Demonstration/animation of minimax game search algorithm with alpha–beta pruning (using html5, canvas, javascript, css)

Графовски алгоритми
Алгоритми претраживања
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 . Istorija Allen Newell i Herbert A . Simon su primenili ono što John McCarthy naziva " aproksimacija " isu napisali da je alfa-beta " stvorena iznova više puta " . Arthur Samuel je imao raniju verziju , a Richards , Hart , Levine i / ili Edwards su samostalno prenosili alfa-beta u SAD . McCarthy je predložio sličnu ideju za vreme Dartmouth konferencije održanekoju je izneo grupi svojih studenata među kojima je bio Alan Kotok na MIT-u Alexander Brudno je samostalno otkrio alfa-beta algoritam i svoje rezultate objavljuje Donald Knuth i Ronald W. Moore su unapredili algoritam a Judea Pearl je dokazao njegovu optimalnostgodine . Poboljšanja MINIMAX-a 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 . 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 =or node is a terminal node return the heuristic value of node if maximizingPlayer for each child of node α \ := max( α , alphabeta( child , depth - α , β , not( maximizingPlayer ) ) ) if β ≤ α break ( * Beta cut-off * ) return α else for each child of node β \ := min( β , alphabeta( child , depth - α , β , 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 , 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š Pruning ( algoritam ) Raznovrsni optimalni algoritam ( Branch and bound ) Minimax Kombinatorne optimizacije Negamax Prenošenje tabela Reference Literatura Spoljašnje veze http://www.emunix.emich.edu/ ~evett / AI / AlphaBeta_movie / sld001.htm http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_5B_McCullough_Melnyk/ http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L2_5B_Lima_Neitz/search.html https://web.archive.org/web/20021223103359/http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html https://web.archive.org/web/20041123061044/http://chess.verhelst.org/search.html http://www.frayn.net/beowulf/index.html http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf Minimax ( with or without alpha–beta pruning ) algorithm visualization - game tree solving ( Java Applet ) , for balance or off-balance trees Demonstration / animation of minimax game search algorithm with alpha–beta pruning ( using html5 , canvas , javascript , css ) Графовски алгоритми Алгоритми претраживања