Inteligenta Artificiala

Algoritmul Minimax

In mod clasic, algoritmul minimax se foloseste pentru jocuri de 2 jucatori, turn based (fiecare executa o mutare cand ii vine randul), fara factori aleatori (precum miscari influentate de aruncarea unui zar), cu o stare finala bine determinata.

Calculatorul la fiecare pas face un arbore de mutari pentru a "prevedea" viitorul. La fiecare pas genereaza toate mutarile jucatorului curent, si apoi pentru fiecare dezvolta mai departe subarborele de mutari, pana ajunge la stari finale sau la o adancime maxima, moment in care evalueaza scorul acelei stari. Calculatorul, evident, vede scorul din perspectiva lui, astfel ca isi va calcula mereu propriul scor si va face mutarile astfel incat acest scor sa creasca. In rationamentul lui noteaza cei doi jucatori cu min si max.

• max - este vorba de eticheta corespunzatoare calculatorului, care face mutarile de asa natura incat sa isi maximizeze scorul
• min - este vorba de eticheta corespunzatoare jucatorului adversar (de obicei uman), care face mutarile de asa natura incat sa il incurce pe max, adica sa minimizeze scorul lui max

In momentul in care pentru o stare are toti succesorii cu scorul cunoscut, seteaza scorul acestei stari cu:

• minimul dintre scorurile succesorilor, daca era randul lui min sa mute
• maximul dintre scorurile succesorilor, daca era randul lui max sa mute

Sa presupunem ca avem o stare curenta, in care e randul lui Max sa mute. Vom presupune in acest exemplu ca are doar doua mutari posibile (desi poate sa aiba orice alt numar de mutari, in functie de joc).

Luam succesorii generati si le calculam pe rand subarborii. Incepem cu cel mai din stanga:

Vom presupune ca ambii succesori ai ultimului nod extins sunt noduri terminale, moment in care le evaluam scorul (reamintim ca scorul calculat e intotdeauna al lui Max, indiferent al cui e randul sa mute):

Cum succesorii sunt ai unei stari in care urma sa mute Min (cu alte cuvinte sunt mutarile posibile pentru Min), Min va alege mutarea care ofera scorul cel mai mic, prin urmare completam nodul parinte cu acel scor (cu sensul ca din acea mutare, daca ambii jucatori joaca perfect, se va ajunge la o stare in care scorul lui Max va avea valoarea respectiva)

Extindem si al doilea succesor de sus in subarborele lui:

Calculam scorurile in subarborele nou:

Ca si mai devreme, succesorii sunt al unei stari in care urma sa mute Min, deci se va alege mutarea cu scorul cel mai mic:

Se completeaza acum si radacina. Fiind vorba de o stare in care muta Max, se va alege scorul cel mai mare:

In momentul in care revenim la radacina putem spune care este mutarea aleasa, si e cea care ofera cel mai mare scor pentru Max (evident, de pe nivelul 2 al arborelui):

Puteti citi pe wikipedia mai multe informatii despre algoritmul Minimax

Algoritmul Alpha-Beta

Alpha-Beta este doar o optimizare a algoritmului Minimax. Alpha si beta sunt capetele unui interval de scoruri. Se porneste initial cu scorul minim si scorul maxim posibil. In momentul in care se obtine un scor de la un descendent al starii curente, se actualizeaza intervalul de scoruri pentru frati in felul urmator:

• daca era pas de max, in cazul in care scorul e mai mare decat alpha, scorul este setat drept alpha-ul nou
• daca era pas de min, in cazul in care scorul e mai mic decat beta, scorul este setat drept beta-ul nou

Daca intalnim un interval invalid, ne oprim.

Puteti citi pe wikipedia mai multe informatii despre algoritmul Alpha-Beta