= Racket: Connect4 =

* Responsabil: [[mihai.nan.cti@gmail.com|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|changelog]]
* Tema se va încărca pe **vmchecker**
* Data tester-ului: 28.03.2017
* [[http://cs.curs.pub.ro/2016/mod/forum/view.php?id=5092|Forum tema 1]]
* [[https://vmchecker.cs.pub.ro/ui/#PP| vmchecker]]

== Descriere ==

Scopul temei este implementarea jocului [[https://en.wikipedia.org/wiki/Connect_Four|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ă.

{{https://upload.wikimedia.org/wikipedia/commons/a/ad/Connect_Four.gif}}

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ă.

== Cerințe ==

=== Definirea funcțiilor de control - 20 de puncte ===


Î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''.

{{ :17:teme:state_test.png }}

=== Mutările și determinarea stării finale - 50 de puncte ===


==== Determinarea acțiunilor posibile ====

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.
==== Aplicarea unei acțiuni ====

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.
==== Verificarea stării finale ====

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.
=== Euristică simplă - 30 de puncte ===

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''.

<fc #9400d3>**Observație:** În cazul funcției ''play-game'', prima strategie este cea care se va aplica jucătorului care este primul la rând.</fc>
=== Bonus: Negamax - 20 de puncte ===

Î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ă.

{{ :17:teme:arbore_de_joc.png }}

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.

{{ :17:teme:negamax.png }}

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

{{ :17:teme:evaluare.png }}
== Precizări ==
* Î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''.

== Resurse ==

* {{:17:teme:connect4.zip|Arhiva de pornire}}
* {{:17:teme:connect4-v1.zip|Arhiva de pornire - actualizată}}

== Changelog ==

* 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.