Inteligenta Artificiala

Barem

Rezolvati problema urmatoare folosind algoritmii:

• min-max
• alpha-beta

Toate cerintele se rezolva intr-un singur fisier python.

Linkuri utile

• https://repl.it/@IrinaCiocan/xsi0exemplu#main.py
• https://repl.it/@IrinaCiocan/x-si-0-interf-grafica#main.py
• https://repl.it/@IrinaCiocan/x-si-0-interf-grafica-matrice#main.py
• https://replit.com/@IrinaCiocan/4inline-interfatagrafica (aici aveti exemplul cu butoanele de la inceput, cum trebuie sa faceti voi in tema)
• https://replit.com/@IrinaCiocan/interfata-joc-celule-ziduri
• https://replit.com/@IrinaCiocan/interfata-joc-graf
• Hint: pentru calcularea statisticilor legate de numarul de noduri si de timpi, veti face cate un vector pentru fiecare tip de date (un vector cu toti timpii, un vector cu toate numerele de noduri) Pentru calcularea medianei puteti folosi: https://docs.python.org/3/library/statistics.html#statistics.median

Mod de punctare (punctajul e dat in procentaje din punctajul maxim al temei; procentajul maxim este 100%):

1. (5%) Să se păstreze următoare lucruri deja implementate în exemplu (sau să se implementeze daca cineva decide să refacă programul de la zero):
   • La inceputul programului utilizatorul va fi intrebat ce algoritm doreste sa foloseasca (minimax sau alpha-beta)
   • Utilizatorul va fi întrebat cu ce simbol sa joace (la jocurile unde are sens aceasta intrebare)
   • Se va încerca evitarea sau tratarea situației în care utilizatorul ar putea răspunde greșit (de exemplu, nu poate selecta decât opțiunile corecte dintre care sunt selectate valorile default; sau, unde nu se poate așa ceva, jocul nu pornește până nu se primește un răspuns corect).
   • Afisarea a cui este rândul să mute.
   • Indicarea, la finalul jocului, a câstigatorului sau a remizei daca este cazul.
2. (5%) Utilizatorul va fi întrebat care sa fie nivelul de dificultate a jocului (incepator, mediu, avansat). In functie de nivelul ales se va seta adancimea arborelui de mutari (cu cat nivelul ales e mai mare, cu atat adancimea trebuie sa fie mai mare ca sa fie mai precisa predictia jocului). Posibilitatea utilizatorului de a face eventuale alte setări cerute de enunț. Se va verifica dacă utilizatorul a oferit un input corect, iar dacă nu se va trata acest caz (i se poate reafișa ecranul cu setările afișând și un mesaj de atenționare cu privire la inputul greșit).
3. (5%) Generarea starii initiale
4. (10%) Desenarea tablei de joc (interfața grafică) si afișarea în consolă a tablei (pentru debug; în ce format vreți voi). Titlul ferestrei de joc va fi numele vostru + numele jocului.
5. (15%) Functia de generare a mutarilor (succesorilor) + eventuala functie de testare a validitatii unei mutari (care poate fi folosita si pentru a verifica mutarea utilizatorului)
6. (5%) Realizarea mutarii utilizatorului. Utilizatorul va realiza un eveniment în interfață pentru a muta (de exemplu, click). Va trebui verificata corectitudinea mutarilor utilizatorului: nu a facut o mutare invalida.
7. (10%) Functia de testare a starii finale, stabilirea castigatorului și, dacă e cazul conform cerinței, calcularea scorului. Se va marca în interfața grafică configurația câștigătoare (sau simbolurile câștigătoare, în funcție de regulile jocului). Marcarea se poate face colorând, de exemplu, simbolurile sau culoare de fundal a eventualelor căsuțe în care se află.
8. (20%=10+10) Doua moduri diferite de estimare a scorului (pentru stari care nu sunt inca finale)
9. (15% impărtit după cum urmează) Afisari (în consolă).
   1. (5%) Afisarea timpului de gandire, dupa fiecare mutare, atat pentru calculator (deja implementat în exemplu) cat si pentru utilizator. Pentru timpul de găndire al calculatorului: afișarea la final a timpului minim, maxim, mediu și a medianei.
   2. (2%) Afișarea scorurilor (dacă jocul e cu scor), atat pentru jucator cat si pentru calculator și a estimărilor date de minimax și alpha-beta (estimarea pentru rădacina arborelui; deci cât de favorabilă e configurația pentru calculator, în urma mutării sale - nu se va afișa estimarea și când mută utilizatorul).
   3. (5%) Afișarea numărului de noduri generate (în arborele minimax, respectiv alpha-beta) la fiecare mutare. La final se va afișa numărul minim, maxim, mediu și mediana pentru numarul de noduri generat pentru fiecare mutare.
   4. (3%) Afisarea timpului final de joc (cat a rulat programul) si a numarului total de mutari atat pentru jucator cat si pentru calculator (la unele jocuri se mai poate sari peste un rand și atunci să difere numărul de mutări).
10. (5%) La fiecare mutare utilizatorul sa poata si sa opreasca jocul daca vrea, caz in care se vor afisa toate informațiile cerute pentru finalul jocului ( scorul lui si al calculatorului,numărul minim, maxim, mediu și mediana pentru numarul de noduri generat pentru fiecare mutare, timpul final de joc și a numarului total de mutari atat pentru jucator cat si pentru calculator) Punctajul pentru calcularea efectivă a acestor date e cel de mai sus; aici se punctează strict afișarea lor în cazul cerut.
11. (5%) Comentarii. Explicarea algoritmului de generare a mutarilor, explicarea estimarii scorului si dovedirea faptului ca ordoneaza starile cu adevarat in functie de cat de prielnice ii sunt lui MAX (nu trebuie demonstratie matematica, doar explicat clar). Explicarea pe scurt a fiecarei functii si a parametrilor.
12. Bonus (5%) Dacă faceți mai multe estimări ale scorului dar diferite ca idee (cu alt mod de abordare a jocului).
13. Bonus (5%). Ordonarea succesorilor înainte de expandare (bazat pe estimare) astfel încât alpha-beta să taie cât mai mult din arbore.
14. Bonus (10%). Opțiuni în meniu (cu butoane adăugate) cu:
    • Jucator vs jucător
    • Jucător vs calculator (selectată default)
    • Calculator (cu prima funcție de estimare) vs calculator (cu a doua funcție de estimare)
15. Bonus (5%) - propus de Andrei Cerbulescu. Cand vine randul jucatorului sa mute, sa se marcheze pe interfata grafica pozitiile valide in care poate plasa un simbol.
16. Bonus (15%) Pentru adancimi mai mari de 3 sa se salveze arborele alphabeta si sa se plece de la ce este calculat deja pentru aflarea urmatoarei mutari a calculatorului (ca sa nu fie recalculate mutarile la urmatoarea iteratie). Practic memoram subarborele mutarii alese din arborele alpha-beta generat anterior. Apoi jucatorul face mutarea M. Cautam in subarborele salvat mutarea jucatorului si pornim de la subarborele generat deja pentru ea si il continuam pentru a afla noua mutare a calculatorului.
17. Bonus (5%). Implementati optiunea de undo. La apasarea tastei u, se da undo ultimei mutari facute a utilizatorului. De la al doilea "undo" incolo se anuleaza mutarea calculatorului + mutarea jucatorului (practic se anuleaza mutarea jucatorului si raspunsul calculatorului).
18. Bonus (5%). Implementati optiunea de restartare joc. La apasarea tastei r, se genereaza din nou tabla initiala, se reseteaza scorurile si alte valori ce tineau de jocul anterior.
19. Bonus (5%) La apasarea tastei n la inceputul turn-ului jucatorului (cand jucatorul inca nu a facut vreo mutare) calculatorul isi va schimba (inlocui) mutarea cu urmatoarea cea mai buna dintre mutarile posibile. Apasari succesive ale lui n, ar afisa pe tabla pe rand de la cea mai buna mutare la cea mai slaba. Daca se apasa n si dupa cea mai slaba se reafiseaza cea mai buna (lista e luata de la inceput).
20. Bonus (10%) Optiunile de inrerupere, salvare si continuare joc. La apasarea tastei s, starea jocului se va salva intr-un fisier text (numele fisierului va fi cerut utilizatorului - acesta poate introduce numele fie in interfata grafica fie in consola). Fisierul va fi salvat intr-un folder numit "salvari" al jocului. La intrarea in joc, utulizatorul va primi ca prima intrebare din partea programului daca vrea sa incarce un joc si i se va afisa continutul fiserului de salvari, fiecare fisier avand un numar de ordine. Utilizatorul va raspunde cu numarul de ordine si va putea continua jocul din stadiul in care l-a lasat (tabla si alti parametri se vor incarca din fisier).
21. Bonus (1-10%) Diverse implementari deosebite, optimizari speciale.