Cuprins

Racket: Connect4

Descriere

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:

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:

Cerințe

Definirea funcțiilor de control - 20 de puncte

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

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.

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.

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

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

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:

Precizări

Resurse

Changelog