Strategia Minimax

La modul general, strategia Minimax se bazeaza pe utilizarea unei functii care decide cat de buna este o pozitie, atribuindu-i o valoare numerica. De exemplu, daca pozitia e castigatoare pentru calculator, aceasta ar putea avea scorul 1000, daca e remiza, atunic zero, iar daca calculatorul pierde -1000. Vom numi o pozitie pentru care se poate spune cert care e scorul o pozitie terminala.

Daca o pozitie nu e terminala, valoarea pozitiei e determinata recursiv, presupunand ca ambii jucatori vor juca optim. De aici provine numele Minimax, deoarece unul din jucatori (omul) incearca mereu sa minimizeze scorul pozitiei, in timp ce calculatorul incearca sa-l maximizeze.

O pozitie succesor a lui P este orice pozitie Ps la care se poate ajunge din P efectuand o mutare. Daca calculatorul e la mutare, intr-o pozitie oarecare P, atunci el evalueaza in mod recursiv valoarea tuturor pozitiilor succesor. El va alege pozitia cu valoarea cea mai mare. Aceasta e valoarea lui P. Pentru a evalua orice pozitie succesor P_s, toti succesorii lui P_s sunt evaluati recursiv, si se alege valoarea cea mai mica. Aceasta reprezinta mutarea cea mai buna cu care omul poate raspunde.

Daca la un joc simplu, precum X-0, calculatorul poate evalua toate pozitiile şi alege astfel mutarea cea mai buna, pentru jocuri mai complexe cum e Moara, acest lucru nu e posibil. In acest caz, trebuie sa oprim analiza dupa un anumit numar de mutari. Nodurile unde s-a oprit recursivitatea devin noduri terminale. Aceste noduri sunt evaluate cu o functie care estimeaza valoarea pozitiei. De exemplu, la jocul de Moara, functia ar putea numara piesele de pe tabla, numarul de locuri unde mai poate muta fiecare piesa, numarul de mori ale fiecarui jucator etc. Functia de evaluare este foarte importanta pentru ca mutarea cea mai buna sa fie aleasa.

Pentru a mari adancimea recursivitatii, trebuie sa aplicam diferite tehnici. Mai exact trebuie sa generam mai putine pozitii, fara a pierde informatie.

O astfel de metoda este alpha-beta pruning.

Alpha-beta Pruning

Cea mai importanta imbunatatire ce se poate aduce algoritmului Minimax este alpha-beta pruning.

Strategia consta in a renunta la a mai evalua pozitiile care in mod clar sunt mai defavorabile decat ceea ce a fost gasit pana in prezent. Sa luam ca exemplu urmatoarea figura:

Sa consideram nodul E. Figura arata informatia care a fost adunata pana in momentul de fata. Nodul E nu a fost evaluat inca, dar daca privim atent, nu e necesar sa-l evaluam. Aceasta deoarece din nodul C, omul, care e la mutare va alege valoarea minima. Deci el ar putea sa aleaga 5 sau chiar mai putin daca nodul E are valoare mai mica. In orice caz, calculatorul, din nodul A va prefera sa aleaga varianta B, unde castigul este de 10. Asadar, indiferent ce valoare are nodul E, acesta nu va influenta alegerea calculatorului, deci nu mai e necesar sa-l evaluam. Aceasta strategie poarta numele de alfa. Similar, se poate construi o strategie pentru om, care se numeste beta. Combinand cele doua strategii obtinem alfa-beta pruning, care inseamna asadar a renunta la evaluarea unor pozitii care nu vor modifica alegerea ce trebuie facuta.

Pentru a profita la maxim de aceasta strategie, uneori e bine sa ordonam nodurile inainte sa incepem sa le evaluam. Aceasta deoarece, exista o probabilitate destul de mare ca o pozitie care pare buna in momentul de fata, sa fie intr-adevar buna, in timp ce o mutare proasta, doar rareori se dovedeste a fi buna la o analiza mai adanca.

Codul care implementeaza algoritmul Minimax impreuna cu strategia alpha-beta pruning este definit in fisierul GameEngine.java.

Aplicarea algoritmului Minimax in jocul „Moara”

1. Descrierea jocului

Moara este jucata de doi jucatori. Fiecare jucator are la inceputul partidei disponibile 9 piese pe care le poate plasa pe tabla. Scopul jocului este capturarea tuturor pieselor adversarului, sau blocarea sa in asa fel incat sa nu mai poata muta, caz in care acesta pierde.

Tabla de moara arata ca in figura urmatoare:

O piesa poate fi asezata in unul din cercurile de pe tabla, daca acesta e liber.

Atunci cand trei piese de aceiasi culoare se afla in linie, structura poarta numele de „moara”. Jucatorul care a facut „moara” are dreptul sa captureze o piesa adversara de pe tabla, cu conditia ca aceasta sa nu faca parte la randul ei dintr-o „moara”.

In prima etapa a jocului jucatorii aseaza alternativ piese pe tabla. Daca fac „moara”, captureaza o piesa adversa. Dupa ce toate piesele au fost introduse, urmeaza faza a doua a jocului, cand fiecare jucator poate muta cu piesele sale. Piesele pot fi mutate de pe un cerc pe altul cate un pas, cu conditia ca cercul destinatie sa fie liber. Cei dor jucatori vor urmari sa construiasca alte mori pentru a captura piese, sau pot incerca sa-l blocheze pe celalalt jucator. O moara poate fi „deschisa” apoi „inchisa” din nou pentru a captura piese.

Cand unul din jucatori ramane doar cu trei piese, acestea pot „sari”, adica pot fi mutate oriunde pe tabla.

2. Implementarea jocului

Pentru a implementa acest joc avem nevoie sa construim urmatoarele functii, pe care algoritmul general Minimax le foloseste:

- functia de evaluare a unei pozitii;

- functia de generare a tuturor pozitiilor succesoare.

a) Functia de evaluare

Trebuie sa tinem cont de urmatoarele aspecte cand evaluam o pozitie: numarul de piese ale calculatorului, numarul de piese ale jucatorului, libertatea de miscare a calculatorului, libertatea de miscare a jucatorului.

Pentru fiecare piesa in plus pe care o are calculatorul acesta va primi un bonus de 50 de puncte. Pentru fiecare piesa in minus va primi o penalizare de -5 de puncte.

De asemenea pentru fiecare grad de libertate in plus va primi 2 puncte, altfel va primi penalizari de -2 puncte.

b)Functia de generare.

E alcatuita de fapt din trei functii separate, corespunzatoare celor trei faze ale jocului: introducerea de piese pe tabla, mutari normale, salturi.

Implementarea acestor functii se gaseste in fisierul MillBoard.java

3. Moara in actiune

Mai jos sunt ilustrate principalele momente dintr-o partida:

Tabla de moara inaintea inceperii jocului.

Jucatorul poate seta diferiti parametrii care influenteaza puterea de

gandire a calculatorului.

Desfasurarea partidei

Rezultatul confruntarii