Jocuri ca probleme de căutare

Ne referim la jocuri cu 2 jucatori (care pe rand, alternativ, fac cate o mutare), cu informatie completa, adica ambii jucatori cunosc integral starea curenta a jocului si toate mutarile posibile din acea stare (contra-exemplu: jocurile de carti unde fiecare jucator stie doar cartile sale, dar nu si pe ale oponentului sau ordinea cartilor de pe masa, deci are informatie incompleta). Mutarile sunt deterministe, nu includ probabilitati (de exemplu nu depind de aruncarea unui zar). Jocul se incheie cand se ajunge intr-o stare „terminala” conform regulilor jocului. Aceleasi reguli determina care este rezultatul jocului (care jucator a castigat sau daca eventual a fost remiza).

Un joc va fi reprezentat printr-un arbore de joc in care nodurile corespund starilor de joc, iar arcele corespund mutarilor. Radacina arborelui este starea initiala a jocului, iar frunzele arborelui sunt starile terminale ale jocului. Cei doi jucatori vor fi numiti MAX si MIN. Jucatorul MAX este cel care face prima mutare, apoi cei doi jucatori muta alternativ pana se termina jocul. In arborele de joc, fiecare nivel contine mutarile unui anumit jucator: radacina pentru MAX, apoi toti fiii radacinii sunt pentru MIN, apoi nivelul urmator pentru MAX, si tot asa alternand nivelurile. La finalul jocului, se acorda puncte jucatorului castigator (sau penalizari celui care a pierdut). Pentru asta, se va folosi o functie de utilitate, care acorda o valoare numerica rezultatului unui joc (de exemplu 1 pentru castig, -1 pentru pierdere, 0 pentru remiza).

Jucatorul MAX incearca sa castige sau sa-si maximizeze scorul din acel moment. Jucatorul MIN, oponentul sau, incearca sa minimizeze scorul lui MAX. Deci la fiecare pas, jucatorul MIN va alege acea mutare care este cea mai nefavorabila pentru MAX. Jucatorul MAX trebuie sa gaseasca (folosind arborele de joc) o strategie care-l va conduce la castigarea jocului, indiferent de actiunile lui MIN.

In probleme, vom avea jucatorul MAX (calculatorul care isi alege mutarea folosind algoritmul) versus jucatorul MIN (omul care introduce de la tastatura mutarea dorita).

A se vedea algoritmii MinMax și Alpha-beta.

Structura de cod pe care vom lucra poate fi accesată aici: Ziua 10 - Jocuri