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 19:52] Mihai Nan [Definirea funcțiilor de control - 20 de puncte] |
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 74: | 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 83: | 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 97: | 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. | + | * 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.1489859560.txt.gz · Ultima modificare: 2017/03/18 19:52 de către Mihai Nan
