|
Algoritmul minimax reprezinta o metoda de a selecta cel mai bun mod
de a actiona intr-o anumita situatie, sau joc, cand doua forte opuse, sau doi jucatori
incearca fiecare sa obtina victoria, jucand dupa aceleasi reguli. Este folosit cel mai
adesea pentru a determina cea mai buna mutare pe care un jucator o are la dispozitie
intr-un joc. Are la baza principiul ca la fiecare moment jucatorul aflat la mutare
va alege solutia cea mai buna.
Solutia este reprezentata sub forma unui arbore. Acest arbore contine toate
mutarile pe care un jucator le are la dispozitie sub forma unor succesori ai radacinii,
arborele avand un numar de nivele egal cu numarul de mutari prevazute ale adversarului.
Fiecare ramura a arborelui reprezinta o mutare posibila a jucatorului la un moment dat.
Prin evaluarea frunzelor arborelui se poate prevedea cum va evolua jocul pana in acel
moment.
Cu cat arborele are o adancime mai mare cu atat se poate prevedea mutarea cea
mai benefica la un moment dat.
In situatia jocului Puissance4, cu doi jucatori, rosu si verde, rosul cauta
in arbore nodurile cu valori cat mai mari, iar verdele pe cele cu valori cat mai mici.
Un algoritm de tip minimax determina toate continuarile posibile ale unui joc pana la
nivelul dorit, evaluand fiecare mutare posibila la o anumita valoare. Cautarea se
reduce apoi la a parcurge arborele si a cauta pe rand valorile cea mai mare si cea mai
mica. Acest lucru este echivalent cu a alterna cautarea celei mai bune mutari atat
pentru rosu cat si pentru verde.
Figura de mai jos arata un arbore care simuleaza jocul pe patru nivele, avand
rosu la mutare.Cum am aratat mai sus, in timp ce rosul poate obtine valori mai mari
alegand mutari care duc in stanga sau in drepta arborelui, in acelasi timp verdele
poate obtine valori foarte mici. De aceea valoarea obtinuta de rosu nu este cea mai
buna per total, ci numai avand in vedere conditiile actuale.
(Algoritmul in pseudocod)
Deoarece algoritmul minimax are un cost care creste exponential cu adancimea
de cautare, pentru a reduce timpul necesar unei mutari, cautarea trebuie restrictionata
astfel inca sa nu se ia in considerare mutarile care dezavantajeaza evident jucatorul
aflat la mutare. Un mod de a face acest lucru este de a implementa limitarea alfa beta.
Aceasta metoda functioneaza pe principiul prezentat anterior ca rosul nu va face o
mutare daca prin aceasta va permite verdelui sa faca o mutare si mai buna. Astfel,
daca este intalnita o mutare care are un scor mai mic decat cea mai buna mutare de pana
atunci nu se mai continua pe acea cale. Astfel, daca o mutare este evaluata ca fiind
avantajoasa pentru jucatorul curent, dar nu si pentru adversar, nu se mai continua pe
aceasta cale doarece celalalt jucator nu ar permite asa ceva.
(Algoritmul in pseudocod)
Exemplificarea algoritmului minimax:
Rezolvarea problemelor care presupun 2 adversari este des asociata
cu jocurile. Lumea noastra este plina de astfel de probleme de exemplu:
probleme politice, diplomatice, negocieri,afaceri, batalii militare, strategie.
Rezolvarea problemelor atunci cand ai de a face cu adversari necesita multa
inteligenta.
Vom avea nevoie de un evaluator static care sa caute in spatiul starilor
pentru a selecta cea mai buna mutare posibila. In functie de joc, putem avea o
multitudine de stari in care cel care se afla la mutare sa aiba jocul ca si castigat.
Telul este de a obtine starile de mai sus. Avem de asemenea si stari perdante, din
care jucatorul nu mai poate evolua spre a castiga jocul. O stare castigatoare
pentru unul dintre jucatori inseamna o stare perdanta pentru celalalt. Jucatorul
care se afla la mutare incearca sa identifice modul de joc cel mai profitabil.
Presupunand ca avem urmatorul arbore al jocului sa urmarim evolutia
algoritmului minimax
Cea mai buna mutare este de a juca la d, apoi la 1.In termeni de programare
expresia echivalenta este:
max( min(l,k,m), min(f,g,e), min(i,j,h) )
Pentru a calcula valoarea acestei expresii, s-ar putea sa nu
fie nevoie de evaluarea tuturor argumentelor. Sa presupunem ca am evaluat l,k,m si f astfel:
max( min(l,k,m), min(f,g,e), min(i,j,h) )
2 3 4 1
max( min(2,3,4), min(1,g,e), min(i,j,h) )
max( 2, min(1,g,e), min(i,j,h) )
Pentru ca se calculeaza maximul si s-a intalnit deja un 2, orice minim
intalnit ulterior si care are o valoare mai mica decat 2 nu este luat in calcul. De exemplu
min(1,g,e) trebuie sa fie 1 sau mai putin. Stim ca max(2,1 sau mai putin) trebuie sa fie 2,
de aceea nu mai este necesar sa evaluam 'g' sau 'e'. Similar, cand 'i' este
evaluat la 0, avem max (2, 1 sau mai putin, 0 sau mai putin), care este evaluat la 2.
Aceasta ordine a nodurilor a fost aleasa intamplator.
Sa ne intoarcem la pasii algoritmului minimax si sa vedem cum acesta decide nodurile
care trebuie luate in considerare.
Cautarea minimax cu limitare alfa/beta permite evitarea evaluarii
anumitor noduri irelevante. Pseudocodul ar fi urmatorul:
double maximize(node *n, action *a, double alpha, double beta)
{
generate children of n
for each child
evaluate it as a leaf, or recursively via minimize()
modify alpha locally to be the max of children so far
break out of this loop if alpha >= beta
return(alpha)
}
Acesta trebuie initial apelat in modul urmator:
v = maximize(root,&op,-99999.0,99999.0);
Functia de minimizare este similara:
double minimize(node *n, action *a, double alpha, double beta)
{
generate children of n
for each child
evaluate it as a leaf, or recursively via maximize()
modify beta locally to be the min of children so far
break out of this loop if alpha >= beta
return(beta)
}
Jucatorul care se minimizeaza salveaza valoarea nodului evaluat ca minim
in variabila beta. Functiile de maximizare si minimizare sunt recursive.
De exemplu pe urmatorul arbore de joc:
Sa presupunem ca evaluarea fiecarui succesor este realizata cu functia
de minimizare. De exeplu pentru 'b':
Alfa si beta sunt copiate de mai sus. Acum sa presupunem ca 'g' este
evaluat de catre functie la valoarea 2. Pentru ca functia de evaluare este cea
de minimizare, si pentru ca 2 este mai mic decat beta actual, acesta din urma
va lua valoarea 2, rezultand:
Sa presupunem acum ca 'f' este evaluat la 1. Valoarea lui beta este
coborata de la 2 la 1.
Faptul ca 'e' este evaluat la 4 nu afecteaza valoarea lui beta, rezultand:
Rezulta ca aceasta apelare a minimizarii returneaza beta=1, ceea ce inseamna
ca nodului 'b' ii este data valoarea 1. Avem acum urmatorul arbore:
De observat este faptul ca valoarea lui alfa este acum 1. Urmeaza o
apelare recursiva a minimizarii pentru nodul 'd'. Initial avem:
Observati ca alfa este initializat la 1 pentru ca este copiata valoarea de mai sus.
Dupa evaluarea nodurilor 'k','l','m' avem urmatorul arbore:
Deoarece beta=2 functia de minimizare returneaza 2, rezultand:
Acum, minimizarea pentru 'c' incepe astfel:
Frunza 'j' este evaluata la valoarea 3, rezultand:
Frunza 'i' este evaluata la valoarea 0, rezultand:
In acest moment, deoarece 2>=0, nu mai este nevoie sa evaluam 'h'.
Faptul ca alfa este 2 inseamna ca o alta mutare poate atinge acest scor. Deci
nu are rost sa continuam evaluarea aici, unde jucatorul care se maximizeaza
s-ar descurca mai prost (<=0).
In continuare vom urmari pasii unei variante oarecum diferite de minimax denumita
negamax. O problema care foloseste minimax in varianta de mai sus trebuie sa aiba
cod si pentru jucatorul care se maximizeaza si pentru cel care se minimizeaza.
Negamax realizeaza tocmai reunirea celor doua coduri intr-unul singur.
Se observa ca min(x,y,z)=-max(-x,-y,-z). Denumirea acestui algoritm vine de la
acest '-max'. Prin complementarea starii algoritmului la fiecare nivel, intotdeauna este
randul jucatorului care se maximizeaza. Bineinteles ca in continuare exista 2 jucatori
care alterneaza rundele, dar prin complementarea starii, amandoi pot folosi codul pentru
maximizare de fiecare data.
(Algoritmul in pseudocod)
Sa luam exemplul unui joc mai simplu decat cel implementat de noi, X si 0. Daca 'x'
joaca primul, se poate schimba valoarea lui 'x' in '0', si lasa ca x sa joace in continuare.
Dupa aceasta, se complementeaza din nou starea, 'x' revenind in '0' si invers. Cand este evaluata
starea complementara, se returneaza o valoare din punctul de vedere al celuilalt jucator. Deci,
evaluand o stare din punctul de vedere al jucatorului care se minimzeaza, folosind functIA de maximizare,
se obtine o valoare complementara (adica valoarea opusa celei reale). Astfel se pot maximiza aceste
valori folosind max(-x,-y,-z) si returnand pur si simplu -max. Sa luam exemplul de mai sus:
Acum sa adaugam la acest algoritm si limitarea alfa/beta. Este evident ca in loc sa transmitem ca pa
rametrii alfa si beta functiei max, ii interschimbam si ii negam. Aceasta inseamna a nega si a schimba
punctul de vedere.
(Algoritmul in pseudocod)
Vom lucra pe exemplul precedent:
Sa presupunem ca evaluarea fiecarui succesor a fost realizata folosind negamax. Pentru 'b':
Alfa si beta sunt luate de mai sus. Interschimbarea si negarea sunt dificil de observat, deoarece
perechea [-beta,alfa] = [-alfa,beta] in cazul de fata. Acum sa presupunem ca 'g' este evaluat la -2.
Deoarece -2 este mai mare decat valoarea actuala a lui alfa, alfa va lua valoarea -2, rezultand arborele:
Acum sa presupunem ca 'f' este evaluat la -1. Alfa creste de la -2 la -1, rezultand:
Deoarece 'e' este evaluat la -4 (<-1) el nu va afecta valoarea lui alfa:
Aceasta apelare a lui negamax returneaza -alfa (-(-1)), ceea ce inseamna ca lui 'b' i s-a atribuit
valoarea 1:
Sa observam ca alfa creste la 1. Acum urmeaza o noua apelare recursiva a lui negamax pentru
nodul 'd'. Initial avem:
Beta este initializat la -1 pentru ca este obtinut prin negarea valorii lui alfa. Dupa evaluarea
nodurilor 'k', 'l', 'm':
Deoarece alfa este 2, avem:
Cautand valoarea lui 'c' cu negamax, rezulta:
Frunza 'j' este evaluata la -3:
Frunza `i' este evaluata la 0, rezultand:
Sa observam acum ca deoarece 0>=-2 nu mai este nevoie de evaluarea lui 'h'.
Sa ne intoarcem la modul de ordonare al nodurilor. Am vazut mai sus ca unele
metode de ordonare produc mai multe apelari recursive decat altele. In arborele
din stanga au loc patru apelari, in timp ce in cel din dreapta nu are loc nici una:
Scaderea numarului de apelari recursive printr-o buna ordonare a nodurilor poate duce la
o imbunatatire a timpului de cautare. Aceasta ordonare a nodurilor poate fi realizata prin metoda
numita `static node ordering'. La fiecare nod, se genereaza succesorii, se evalueaza fiecare (chiar
daca nu sunt frunze), sunt sortati descrescator, si se cauta in aceasta ordine. Astfel, cautand mutarile
mai bune la inceput, alfa si beta se apropie una de cealalta mai rapid, ceea ce inseamna ca vom avea mai
putine apelari recursive.
|
