• Responsabil: Mihai Nan
• Deadline soft: 31.03.2017, apoi depunctare 0.5p/zi
• Deadline hard: 05.04.2017 ora 23.59
• Data publicării: 18.03.2017
• Data ultimei modificări: 28.03.2017 changelog
• Tema se va încărca pe vmchecker
• Data tester-ului: 28.03.2017
• Forum tema 1
• vmchecker

Scopul temei este implementarea jocului Connect4. Acest joc este unul destul de simplu și are la bază o tablă de joc sub forma unei matrice în care doi jucători dau drumul unor discuri, fiecare jucător având discuri de o anumită culoare. Astfel, la fiecare rundă, un jucător poate alege o coloană a matricei, care mai conține cel puțin o poziție liberă, și îi dă drumul discului, acesta poziționându-se pe prima celulă liberă din tabla de joc. Jocul se termină când nu mai sunt poziții libere disponibile sau unul din jucători a reușit să plaseze patru discuri (de aceeași culoare) într-o linie pe orizontală, verticală sau diagonală.

Se dorește implementarea unui program care:

• să îi permită unui utilizator uman să joace;
• va putea juca singur, realizând mutări aleatoare;
• pentru bonus, va implementa o euristică mai complexă, bazată pe algoritmul Negamax.

Reprezentarea internă a elementelor de joc va fi la alegere, însă va trebui să implementați conform specificațiilor setul de funcții de control.

Fazele pe care trebuie să le aveți în vedere pentru realizarea acestei teme sunt următoarele:

• decizia asupra reprezentării tablei de joc;
• implementarea funcțiilor de control;
• determinarea listei de acțiuni posibile pentru o anumită tablă de joc și aplicarea unei acțiuni;
• verificarea terminării jocului;
• implementarea unei euristici simple care să permită jocul automat;
• BONUS: aplicarea algoritmului Negamax pentru a selecta cea mai bună acțiune posibilă.

În continuare, se va descriere funcționalitatea fiecarei funcții.

• init-board - primește dimensiunile tablei de joc și returnează reprezentarea tablei de joc în starea inițială, având toate coloanele goale;
• init-state - primește dimensiunile tablei de joc și indicele jucătorului care va realiza prima mutare și returnează starea inițială de joc care va conține tabla de joc, indicele jucătorului curent și alte informații care v-ar putea fi utile în implementare;
• get-board - returnează tabla de joc a stării;
• get-player - returnează jucătorul curent al unei stări de joc;
• is-empty-board? - primește o tablă de joc și verifică dacă este goală;
• get-height - primește reprezentarea unei table de joc și întoarce înălțimea sa;
• get-width - primește reprezentarea unei table de joc și întoarce lățimea sa;
• get-disc - primește reprezentarea unei table de joc și o pereche formată din doi indici, reprezentând coloana, respectiv linia, și întoarce valoarea discului (EMPTY / RED / YELLOW) aflat pe poziția specificată (elementul cu indicii (0, 0) este cel din stânga jos). De exemplu, în figura de mai jos, discul aflat pe poziția (2, 0) are valoarea RED, cele de pe poziția (6, 0) și (6, 1) au valoare YELLOW, iar cele de pe pozițiile (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5) au valoare EMPTY.

Pentru implementarea tablei de joc, aveți în vedere utilizarea unei reprezentări care să permită parcurgerea și inserarea ușoară a unui disc.

Pentru testarea acestor funcții, se va defini (manual) următoarea stăre de joc, ce are ca și utilizator curent pe cel având indicele YELLOW, în fișierul connect4.rkt. Aceasta va avea identificatorul state-test.

Pentru a oferi posibilitatea programului să joace singur, trebuie să implementați funcția get-available-actions care va întoarce o listă cu acțiunile posibile pentru o anumită stare de joc. O acțiune validă va reprezenta indicele unei coloane care nu este încărcată complet cu discuri. Astfel, numărul maxim de acțiuni o să fie egal cu numărul de coloane, dacă toate mai au cel puțin un compartiment liber.

După cum se poate observa, pentru starea state-test lista de acțiuni posibile este următoarea '(0 1 3 4 5 6). 2 nu reprezintă o acțiune posibilă, deoarece coloana respectivă este încărcată complet.

Pentru această cerință va trebui să implementați funcțiile apply-action și apply-actions. Prima funcție primește o stare de joc și o mutare ce trebuie aplicată și realizează actualizarea tablei de joc, conform mutării, și modifică indicele jucătorului curent, iar a doua funcție primește, pe lângă starea de joc, și o listă de acțiuni pe care le va aplica succesiv.

Pentru a determina când s-a încheiat un joc, trebuie să implementați funcția is-game-over? care verifică dacă s-a ajuns într-o stare finală de joc (fie nu mai există acțiuni ce se pot realiza, fie unul din jucători a câștigat). Funcția va întoarce 3 dacă starea primită ca parametru este finală deoarece tabla de joc este completă, #f dacă starea nu este finală sau indicele jucătorului (RED / YELLOW) care a câștigat.

Euristica propusă este de verificare a existenței unei mutări prin care jucătorul curent poate câștiga jocul, iar în cazul în care o astfel de mutare există aceasta să fie selectată. Dacă nu are posibilitatea de a câștiga jocul, printr-o mutare finală, atunci trebuie verificat dacă la runda următoare ar putea adversarul să câștige, iar în cazul în care este posibil acest lucru se va alege mutarea care îl împiedică pe adversar să câștige. Altfel, se poate alege orice mutare validă.

Pentru a testa euristica implementată, veți realiza și o funcție (play-game) care va simula un joc, până se ajunge într-o stare finală. Funcția primește ca argumente o stare de joc (state) și două strategii, reprezentând ceea ce va folosi fiecare agent pentru a alege o acțiune într-o anumită stare de joc. Această funcție va avea ca rezultat o pereche formată dintr-o lista de acțiuni și indicele jucătorului care a câștigat ori valoarea 3, în caz de remiză. O strategie este reprezentată printr-o pereche ce conține numele funcției ce se va aplica pentru selectarea unei acțiuni și ultimul parametru al funcției (ex. '(negamax . 5) - se va apela funcția negamax de la bonus având maxDepth 5; sau '(select-random-action . (current-pseudo-random-generator)) - se va apela funcția select-random-action având ca generator pentru random (current-pseudo-random-generator)). Va trebui să implementați și funcția select-random-action care va selecta aleator o acțiune din lista celor posibile. Pentru a genera un număr random, veți folosi funcția random (ex. (random 5 rand-gen), unde rand-gen este al doilea parametru al funcției select-random-action). După ce ați implementat această funcție, modificați valoare pentru AI în #t.

Observație: În cazul funcției play-game, prima strategie este cea care se va aplica jucătorului care este primul la rând.

În cazul jocurilor cu doi jucători, în care oponenți își modifică pe rând poziția de joc sau starea, algoritmul Minimax este cel mai uzitat, împreună cu variantele sale îmbunătățite. În linii mari, acest algoritm folosește o funcție care decide cât de bună este o poziție, prin atribuirea unor scoruri. Algoritmul se bazează pe existența a doi jucători cu strategii diferite: jucătorul Max este cel care va încerca în permanență să-și maximizeze câștigul, în timp ce jucătorul Min dorește să minimizeze câștigul jucătorului Max la fiecare mutare. Având în vedere că în cazul jocurilor ce au un factor de ramificare mare arborele de căutare ar conține foarte multe noduri, algoritmul ajungând să fie aproape imposibil de aplicat, datorită timpului mare necesar analizării tuturor pozițiilor disponibile, în vederea selectării celei mai potrivite, s-a încercat optimizarea acestuia. Astfel, au apărut diverse variante echivalente optimizate cum ar fi Negascout, Negamax, Alpha-Beta.

Algoritmul Minimax realizează o căutare în adâncime în arborele de joc, unde nodurile reprezintă stări ale jocului, iar arcele definesc acțiuni posibile ce se pot realiza dintr-o stare de joc. Astfel, configurația inițială a jocului este rădăcina arborelui de joc, iar frunzele reprezintă stări finale pentru joc, pentru care se poate aplica o funcție de utilitate în vederea determinării unei valori, care este propagată spre nivelurile superioare ale arborelui.

În continuare, se va prezenta un exemplu pentru celebrul joc X și O, având ca și rădăcină o configurație diferită de cea inițială, reprezentând, astfel, un subarbore al întregului arbore de joc. În acest caz, funcția de utilitate atribuie valoarea 1 unei stări finale dacă jucătorul X a câștigat, -1 dacă jucătorul O a câștigat și 0 pentru remiză.

Algoritmul Negamax este o variantă a algoritmului Minimax pentru jocuri de sumă 0, cele în care există un învingător și un învins sau jocul se termină cu o remiză. Pentru un astfel de joc, putem considera câștigul unui jucator ca fiind egal cu modulul sumei pierdute de celălalt jucător, fiecare încercând să maximizez câștigul la fiecare pas. Cu alte cuvinte, o acțiune este cu atât mai bună pentru jucătorul care o execută cu cât este mai rea pentru adversarul său.

Pentru această cerință, va trebui să implementați funcția de evaluarea a unei stări și funcția care determină cea mai bună mutare, folosind algoritmul Negamax, prezentat mai jos în pseudocod.

Un exemplu de funcție de evaluare, pe care o putem folosi în cadrul algoritmului Negamax, este următoarea:

• Încărcarea temelor, ca și testarea și notarea lor, se va face pe vmchecker. Este suficient să includeți fișierul connect4.rkt (plus readme) în arhivă, testele există deja.
• În arhiva temei includeți un fișier README cu detalii despre cum ați implementat reprezentarea unei stări de joc.
• Sunt interzise efectele laterale de orice fel (set!, set-car! etc.).
• Este indicată utilizarea funcționalelor. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct).
• Se va lucra exclusiv în fișierul connect4.rkt. Elementele de implementat sunt clar indicate.
• NU este permisă folosirea tipului Matrix.

• Arhiva de pornire
• Arhiva de pornire - actualizată

• 18.03.2017 – am inclus în fișierul connect4-test.rkt două funcții (print-board și print-state) pentru afișarea tablei de joc și a unei stări de joc;
• 20.03.2017 – am corectat testul is-game-over?12;
• 20.03.2017 – am adăugat o precizare legată de tipul Matrix;
• 20.03.2017 – am adăugat o explicație suplimentară pentru algoritmul Negamax;
• 26.03.2017 – am adăugat o observație legată de cele două strategii pentru play-game;
• 28.03.2017 – am adăugat testerul și varianta actulizată a arhivei.