Negamaks algoritam
Negamaks pretraga je varijanta minimaks pretrage koja se oslanja na nultu-sumu prilikom igre u kojoj učestvuju dva igrača.
Ovaj algoritam se zasniva na činjenici da je maks(a, b) = -min(-a, -b) kako bi se pojednostavila implementacija minimaks algoritma. Preciznije, vrednost koja odgovara poziciji igrača A u toku igre jednaka je negaciji vrednosti koja odgovara poziciji igrača B. Prema tome, igrač koji je na potezu želi da maksimizuje negaciju vrednosti koja proizilazi iz tog poteza: pozicija naslednika mora, po definiciji, da bude vrednovana od strane protivnika. Prethodna rečenica je korektna nezavisno od toga koji igrač je na potezu, igrač A ili igrač B. Iz toga proizilazi da se jednim potezom mogu vrednovati obe pozicije. Ovo je pojednostavljena verzija minimaks algoritma koja zahteva da igrač A odabere potez sa maksimalnom vrednošću naslednika, dok igrač B odabere potez sa minimalnom vrednošću naslednika.
Ovaj algoritam ne bi trebalo mešati sa negaskaut algoritmom, koji veoma brzo izračunava minimaks ili negamaks vrednost, mudro koristeći alfa-beta pretragu, otkrivenu 1980—ih godina.[1] Potrebno je imati na umu da je alfa-beta pretraga, sama po sebi, jedan od načina da se izračuna minimaks ili negamaks vrednost pozicije, brzo, izbegavajući pretragu konkretnih neintersantnih pozicija.
Većina algoritama pretraživanja su zasnovani na negamaks pretrazi.
Osnovni negamaks algoritam
[uredi | uredi izvor]Negamaks radi nad istom vrstom stabla (game tree) koja se koristi prilikom algoritma minimaks pretrage. Svaki čvor i koren stabla predstavljaju određene faze igre u kojoj učestvuju dva igrača. Prelazak na čvorove potomaka predstavlja poteze koji su na raspolaganju igraču koji se nalazi na datom čvoru, odnosno igraču koji je na potezu.
Cilj negamaks pretrage je pronaći čvor ciljne vrednosti za igrača koji se nalazi na korenu stabla.[2] Naredni pesudokod prikazuje osnovni negamaks algoritam, sa mogućnošću pedašavanja maksimalne dubine pretrage.
01 function negamax(čvor, dubina, boja) 02 if dubina = 0 ili čvor je terminalni čvor 03 return boja * heuristička vrednost čvora 04 najboljaVrednost := −∞ 05 foreach potomak čvora 06 v := −negamax(potomak, dubina − 1, −boja) 07 najboljaVrednost := max( najboljaVrednost, v ) 08 return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostKorena := negamax( koren, dubina, 1) minimaxVrednostKorena := negamaxVrednostKorena
Inicijalni poziv za koren igrača B negamaxVrednostKorena := negamax( koren, dubina, −1) minimaxVrednostKorena := −negamaxVrednostKorena
Koren nasleđuje vrednost jednog od svojih neposrednih potomaka, odnosno sinova. Na kraju, onaj potomak čiju je vrednost koren nasledio predstavlja ujedno i najbolji potez koji je moguće odigrati. Iako se u pseudokodu u okviru promenljive najboljaVrednost čuva samo najbolji rezultat, praktična implementacija će takođe čuvati i najbolji potez, zajedno sa najboljaVrednost.
Ono što može biti zbunjujuće je način izračunavanja heurističke vrednosti trenutnog čvora. U ovoj implementaciji, ova vrednost se uvek izračunava sa tačke gledišta igrača A, čija boja je 1. Drugim rečima, veća heuristička vrednost uvek predstavlja situaciju koja je povoljnija za igrača A. Ovo je ponašanje koje odgovara i minimaks algoritmu. Heuristička vrednost se ne mora nužno poklapati sa povratnom vrednošću čvora, najboljaVrednost, usled negacije vrednosti koja se javlja prilikom primene negamaks agoritma, kao i zbog parametra boja. Negamaks povratna vrednost čvora je heuristička sa tačke gledišta čvora igrača koji je trenutno na potezu.
Negamaks rezultat se poklapa sa minimaks rezultatom koji se odnosi na čvorove gde je igrač A na potezu, kao i onde gde je igrač A maksimizujući igrač u minimaks ekvivalentu. Negamaks uvek pretražuje maksimum vrednosti za sve svoje čvorove. Otuda, kada su čvorovi igrača B u pitanju, minimaks rezultat predstavlja negaciju njihovih negamaks rezultata. Igrač B je minimizujući igrač u minimaks ekvivalentu.
Određene varijacije negamaks algoritma mogu da izostave parametre boja. U tom slučaju, funkcija koja izračunava heurističku vrednost vraća vrednost sa tačke gledišta čvora trenutnog igrača.
Negamaks algoritam sa alfa-beta pretragom
[uredi | uredi izvor]Određene optimizacije minimaks algoritma su jednako primenjive za negamaks algoritam. Alfa-beta pretraga može smanjiti broj čvorova koji negamaks algoritam obrađuje u pretrazi na sličan način kao u minimaks algoritmu.
Ovaj pseudokod prikazuje negamaks algoritam sa alfa-beta pretragom ograničene dubine.
01 function negamax(čvor, dubina, α, β, boja) 02 if dubina = 0 ili čvor je terminalni čvor 03 return boja * heuristička vrednost čvora 04 potomciČvora := GenerišiPoteze(čvor) 05 potomciČvora := RedosledPoteza(potomciČvora) 06 najboljaVrednost := −∞ 07 foreach potomak u potomciČvora 08 v := −negamax(potomak, dubina − 1, −β, −α, −boja) 09 najboljaVrednost := max( najboljaVrednost, v ) 10 α := max( α, v ) 11 if α ≥ β 12 return β 13 return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostČvora := negamax( koren, dubina, −∞, +∞, 1)
Alfa (α) i beta (β) predstavljaju gornje i donje granice za vrednosti čvorova potomaka za datu dubinu stabla. Negamaks postavlja argumente α i β za koren stabla na najmanju i najveću moguću vrednost. Ostali algoritmi pretrage, kao što su negaskaut i MTD, mogu inicijalizovati α i β određenim alternativnim vrednostima kako bi se kasnije unapredile performanse pretrage stabla.
Kada negamaks naiđe na vrednost čvora potomka izvan alfa-beta granica, tada se odsecaju određeni delovi stabla i eliminišu se iz dalje pretrage. Odsecanja su implicitno zasnovana na povratnim vrednostima čvorova, najboljaVrednost. Vrednost čvora koja odgovara inicijalnom intervalu od α do β predstavlja konkretnu (pravu) vrednost čvora. Ta vrednost se poklapa sa vrednošću koju bi vratio i osnovni negamaks algoritam, bez odsecanja i bez ikakvih α i β granica. Ukoliko je povratna vrednost čvora izvan intervala, onda ta vrednost predstavlja gornju (ukoliko je vrednost ≤ α) ili donju (ukoliko je vrednost ≥ β) granicu za pravu vrednost datog čvora. Alfa-beta pretraga na kraju odbacuje sve vrednosti koje proizilaze iz granica. Te vrednosti ne doprinose i ne utiču na krajnji rezultat algoritma.
Pseudokod prikazuje fail-soft varijacije alfa-beta pretrage. Fail-soft nikada ne vraća α ili β direktno kao vrednost čvora. Tako, vrednost čvora može biti izvan inicjalnih granica α-β intervala. Sa druge strane, fail-hard alfa-beta pretraga uvek ograničava vrednost čvora alfa-beta intervalom.
Ova implementacija takođe prikazuje opcioni redosled poteza u odnosu na forič petlju koja obrađuje čvorove potomaka. Redosled poteza je optimizacija alfa-beta pretrage koja pokušava da pogodi čvorove potomaka koji imaju vrednost najpribližniju vrednosti datog čvora. Algoritam najpre pretražuje te čvorove. Rezultat dobrog nagađanja je poboljšanje vremena, a česta alfa-beta odsecanja utiču na odsecanje dodatnih grana i preostalih potomaka čvorova u stablu.
Negamaks algoritam sa alfa-beta pretragom i transpozicionim tabelama
[uredi | uredi izvor]Transpozicione tabele selektivno pamte vrednosti čvorova u stablu. Transpozicija je termin koji podrazumeva da se do date pozicije na tabli igre (game board) može doći primenjujući niz različitih poteza u igri.
Kada negamaks pretražuje stablo, i nailazi na isti čvor više puta, transpoziciona tabela može vratiti prethodno izračunatu vrednost čvora, preskačući potencijalno dug proces ponovnog izračunavanja vrednosti čvora. Efikasnost negamaks algoritma se naročito poboljšava za ona stabla sa mnogo puteva do datog čvora.
Ispod je prikazan pseudokod koji dodaje transpozicione tabele u algoritam sa alfa-beta pretragom:
function negamax(čvor, dubina, α, β, boa)
alfaOrig := α
// Transpoziciona Lukap Tabela, čvor je lukap ključ za ttUnos
ttUnos := TranspozicionLukapTabela( čvor )
if ttUnos je validan i ttUnos.dubina ≥ dubina
if ttUnos.Flag = EXACT
return ttUnos.Vrednost
else if ttUnos.Flag = LOWERBOUND
α := max( α, ttUnos.Vrednost)
else if ttUnos.Flag = UPPERBOUND
β := min( β, ttUnos.Vrednost)
endif
if α ≥ β
return ttUnos.Vrednost
endif
if dubina = 0 ili čvor je terminalni čvor
return boja * heuristička vrednost čvora
najboljaVrednost := -∞
potomciČvora := GenerišiPoteze(čvor)
potomciČvora := RedosledPoteza(potomciČvora)
foreach potomak u potomciČvora
vr := -negamax(potomak, dubina - 1, -β, -α, -boja)
najboljaVrednost := max( najboljaVrednost, vr )
α := max( α, vr )
if α ≥ β
break
// Transpoziciona Tabela Store; čvor je lukap ključ za ttUnos
ttUnos.Vrednost := najboljaVrednost
if najboljaVrednost ≤ alfaOrig
ttUnos.Flag := UPPERBOUND
else if najboljaVrednost ≥ β
ttUnos.Flag := LOWERBOUND
else
ttUnos.Flag := EXACT
endif
ttUnos.dubina := dubina
TranspozicionaTabelaStore( čvor, ttUnos )
return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostČvora := negamax( koren, dubina, −∞, +∞, 1)
Alfa-beta odsecanja, kao i ograničena maksimalna dubina pretrage u negamaks algoritmu mogu dovesti do delimično netačne, i u potpunosti zanemarene procene čvorova u stablu. Ovo komplikuje dodavanje transpozicione tabele zarad optimizacije negamaks algoritma. Nedovoljno je pratiti samo najboljaVrednost datog čvora u tabeli, zato što najboljaVrednost ne mora ujedno biti i prava vrednost čvora. Kod stoga mora sačuvati i povratiti vezu najboljaVrednost sa određenim alfa-beta parametrima i dubinom pretrage za svaku stavku transpozicione tabele.
Transpozicione tabele će obično izostaviti ili zameniti prethodne vrednosti određenih čvorova u svojim tabelama. Ovo je neophodno pošto je broj čvorova koji negamaks posećuje često veći od veličine same tabele. Izgubljene ili izostavljene stavke u tabeli neće uticati na krajnji negamaks rezultat. Međutim, izgubljene stavke mogu zahtevati od negamaks pretrage češće ponovno izračunavanje određenih vrednosti čvorova stabla, što utiče na njegovu efikasnost.
Vidi još
[uredi | uredi izvor]Reference
[uredi | uredi izvor]- ^ Schaeffer, Jonathan. „The History Heuristic and Alpha-Beta Search Enhancements in Practice”. CiteSeerX 10.1.1.56.9124
., IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989
- ^ Breuker, Dennis M. Memory versus Search in Games Arhivirano na sajtu Wayback Machine (10. avgust 2013), Maastricht University, October 16, 1998
Literatura
[uredi | uredi izvor]- Heineman, George T., Gary Pollice, and Stanley Selkow (2008). „Chapter 7:Path Finding in AI”. Algorithms in a Nutshell. Oreilly Media. str. 213—217. ISBN 978-0-596-51624-6.
- Fishburn, John P. (1984). „Appendix A: Some Optimizations of α-β Search”. Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. str. 107–111. ISBN 978-0-8357-1527-0.