Unelte utilizator
17:teme:racket-connect4
Diferențe
Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
| Both sides previous revision Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
|
17:teme:racket-connect4 [2017/03/18 15:31] Andrei Olaru [Racket: Connect4] |
17:teme:racket-connect4 [2017/03/28 18:34] (curent) Mihai Nan [Changelog] |
||
|---|---|---|---|
| Linia 5: | Linia 5: | ||
| * Deadline hard: __05.04.2017 ora 23.59__ | * Deadline hard: __05.04.2017 ora 23.59__ | ||
| * Data publicării: 18.03.2017 | * Data publicării: 18.03.2017 | ||
| - | * Data ultimei modificări: 18.03.2017 [[#changelog|changelog]] | + | * Data ultimei modificări: 28.03.2017 [[#changelog|changelog]] |
| * Tema se va încărca pe **vmchecker** | * Tema se va încărca pe **vmchecker** | ||
| - | * Data tester-ului: o să fie disponibil în câteva zile | + | * Data tester-ului: 28.03.2017 |
| * [[http://cs.curs.pub.ro/2016/mod/forum/view.php?id=5092|Forum tema 1]] | * [[http://cs.curs.pub.ro/2016/mod/forum/view.php?id=5092|Forum tema 1]] | ||
| + | * [[https://vmchecker.cs.pub.ro/ui/#PP| vmchecker]] | ||
| == Descriere == | == Descriere == | ||
| Linia 42: | Linia 43: | ||
| * ''init-board'' - primește dimensiunile tablei de joc și returnează reprezentarea tablei de joc în starea inițială, având toate coloanele goale; | * ''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; | * ''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; | * ''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ă; | * ''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-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-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 linia, respectiv coloana, și întoarce valoarea discului (**EMPTY** / **RED** / **YELLOW**) aflat pe poziția specificată . | + | * ''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 implementarea tablei de joc, aveți în vedere utilizarea unei reprezentări care să permită parcurgerea și inserarea ușoară a unui disc. | ||
| Linia 73: | Linia 75: | ||
| 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''. | 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 === | === Bonus: Negamax - 20 de puncte === | ||
| Linia 82: | Linia 86: | ||
| {{ :17:teme:arbore_de_joc.png }} | {{ :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. | 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. | ||
| Linia 96: | Linia 102: | ||
| * Este indicată utilizarea funcționalelor. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct). | * 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. | * Se va lucra exclusiv în fișierul ''connect4.rkt''. Elementele de implementat sunt clar indicate. | ||
| + | * **NU** este permisă folosirea tipului ''Matrix''. | ||
| == Resurse == | == Resurse == | ||
| * {{:17:teme:connect4.zip|Arhiva de pornire}} | * {{:17:teme:connect4.zip|Arhiva de pornire}} | ||
| + | * {{:17:teme:connect4-v1.zip|Arhiva de pornire - actualizată}} | ||
| == Changelog == | == 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. | ||
17/teme/racket-connect4.1489843908.txt.gz · Ultima modificare: 2017/03/18 15:31 de către Andrei Olaru
