Unelte utilizator
15:teme:haskell-kalah
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 | ||
|
15:teme:haskell-kalah [2015/04/08 11:16] Lucian Mogoșanu [Resurse] |
15:teme:haskell-kalah [2016/04/05 09:59] (curent) Mihnea Muraru [Precizări] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| = Haskell: Kalah = | = Haskell: Kalah = | ||
| - | * Responsabil: [[mmihnea@gmail.com|Mihnea Muraru]] | + | * Responsabili: [[mmihnea@gmail.com|Mihnea Muraru]], [[lucian.mogosanu@cs.pub.ro|Lucian Mogoșanu]] |
| - | * Deadline: TODO | + | * Deadline: 06.05.2015 |
| - | * Data publicării: TODO | + | * Data publicării: 09.04.2015 |
| - | * Data ultimei modificări: TODO | + | * Data ultimei modificări: 09.04.2015 |
| - | * Data arhivei: TODO | + | * Data arhivei: 09.04.2015 |
| == Obiective == | == Obiective == | ||
| * utilizarea mecanismelor **funcționale** și de **tipuri** ale limbajului Haskell pentru implementarea unui **joc** (//[[http://developoid.com/g/pocketmancala/|Kalah/Mancala]]//) | * utilizarea mecanismelor **funcționale** și de **tipuri** ale limbajului Haskell pentru implementarea unui **joc** (//[[http://developoid.com/g/pocketmancala/|Kalah/Mancala]]//) | ||
| - | * pentru bonus: exploatarea evaluării **leneșe** pentru explorarea controlată a spațiului stărilor într-un algoritm de inteligență artificială (//TODO//). | + | * pentru bonus: exploatarea evaluării **leneșe** pentru explorarea controlată a spațiului stărilor într-un algoritm de inteligență artificială (//Minimax//). |
| == Descriere == | == Descriere == | ||
| Linia 20: | Linia 20: | ||
| # va permite jocul între **doi utilizatori umani** | # va permite jocul între **doi utilizatori umani** | ||
| # îi va da posibilitatea unui jucător uman să joace **împotriva calculatorului**, AI-ul fiind bazat pe o euristică simplă | # îi va da posibilitatea unui jucător uman să joace **împotriva calculatorului**, AI-ul fiind bazat pe o euristică simplă | ||
| - | # pentru **bonus**, AI-ul va implementa o euristică mai complexă, bazată pe algoritmul //minimax// (TODO). | + | # pentru **bonus**, AI-ul va implementa o euristică mai complexă, bazată pe algoritmul //minimax//. |
| == Cerințe == | == Cerințe == | ||
| Linia 26: | Linia 26: | ||
| Rezolvarea temei este structurată pe etapele de mai jos. Începeți prin a vă familiariza cu structura **arhivei** de [[#Resurse|resurse]]. În rezolvare, exploatați **testele** drept cazuri de utilizare a funcțiilor pe care le implementați. | Rezolvarea temei este structurată pe etapele de mai jos. Începeți prin a vă familiariza cu structura **arhivei** de [[#Resurse|resurse]]. În rezolvare, exploatați **testele** drept cazuri de utilizare a funcțiilor pe care le implementați. | ||
| - | === Tabla și mutările (80p) === | + | === Tabla și mutările (90p) === |
| Implementați tipurile de date și funcțiile din fișierul ''Board.hs'', conform indicațiilor locale. Testele aferente se găsesc în fișierul ''BoardTest.hs''. După implementarea (eventual parțială) a tablei și a mutărilor, puteți utiliza funcția ''twoHumans'' din fișierul ''Interactive.hs'': introduceți numărul casei (de la ''1'' la ''6'', numerotat de la stânga la dreapta), urmat de ''Enter'', pentru precizarea mutărilor. | Implementați tipurile de date și funcțiile din fișierul ''Board.hs'', conform indicațiilor locale. Testele aferente se găsesc în fișierul ''BoardTest.hs''. După implementarea (eventual parțială) a tablei și a mutărilor, puteți utiliza funcția ''twoHumans'' din fișierul ''Interactive.hs'': introduceți numărul casei (de la ''1'' la ''6'', numerotat de la stânga la dreapta), urmat de ''Enter'', pentru precizarea mutărilor. | ||
| Pentru implementarea tablei de joc, aveți în vedere utilizarea unei structuri de date care să permită parcurgerea și actualizarea ușoară a numărului de semințe din fiecare casă. De asemenea, gândiți structura ''Board'' astfel încât să vă faciliteze implementarea funcțiilor exportate de ''Board.hs''. | Pentru implementarea tablei de joc, aveți în vedere utilizarea unei structuri de date care să permită parcurgerea și actualizarea ușoară a numărului de semințe din fiecare casă. De asemenea, gândiți structura ''Board'' astfel încât să vă faciliteze implementarea funcțiilor exportate de ''Board.hs''. | ||
| - | === Euristică simplă (20p) === | + | === Euristică simplă (10p) === |
| - | Implementați funcția ''step'' din fișierul ''AIEmpty.hs'', conform specificațiilor locale. Euristica propusă este de aplicare a acelei mutări care conduce la **scorul maxim** al calculatorului în pasul următor. Testele aferente se găsesc în fișierul ''AIEmptyTest.hs''. Pentru testare, utilizați funcția ''humanVsAI'' din fișierul ''Interactive.hs''. | + | Implementați funcția ''step'' din fișierul ''AISimple.hs'', conform specificațiilor locale. Euristica propusă este de aplicare a acelei mutări care conduce la **scorul maxim** al calculatorului în pasul următor. Testele aferente se găsesc în fișierul ''AISimpleTest.hs''. Pentru testare, utilizați funcția ''userMode'' din fișierul ''AISimple.hs''. |
| === Bonus: Minimax (20p) === | === Bonus: Minimax (20p) === | ||
| - | TODO | + | Abordarea precedentă are neajunsul că este o soluție **lacomă** de explorare a posibilităților de joc. O soluție care mărește șansele de câștig al jucătorului artificial este aceea care ia în calcul posibila evoluție ulterioară a jocului. Astfel, algoritmul [[http://en.wikipedia.org/wiki/Minimax|Minimax]] explorează mutările posibile **viitoare** (până la un număr dat), atât ale jucătorului curent cât și ale adversarului, căutând să îi maximizeze celui dintâi șansele de câștig. Dat fiind faptul că dimensiunea spațiului de explorare poate fi intractabilă, deseori algoritmul include o componentă de limitare (//pruning//) a adâncimii de căutare. |
| + | |||
| + | În cazul Kalah, o posibilă abordare implică aplicarea Minimax pentru maximizarea **câștigului** AI-ului atunci când acesta mută, și minimizarea **pierderii** atunci când jucătorul uman mută. O particularitate a arborelui de stări generat în cazul acesta este faptul că un jucător poate juca două ture consecutive, caz în care vor fi efectuați doi pași consecutivi de maximizare sau de minimizare, în funcție de jucătorul curent. | ||
| + | |||
| + | Astfel, implementarea voastră va avea în vedere următoarele funcționalități: | ||
| + | |||
| + | * **Generarea** arborelui (posibil infinit) Minimax de stări (//expand//) | ||
| + | * **Limitarea** numărului de niveluri ale arborelui la o valoare dată (//prune//) | ||
| + | * **Evaluarea** trade-off-ului câștig/pierdere după o euristică dată și alegerea pierderii minime în condițiile în care adversarul joacă să își maximizeze câștigul, conform Minimax (//pick//) | ||
| + | |||
| + | În cazul particular al Kalah, funcția de evaluare euristică se va folosi atât de scorul AI-ului, cât și de cel al jucătorului uman, pentru a determina **câștigul** adus de stare dată celui dintâi. Spre exemplu, o stare în care scorul jucătorului uman este mai mare decât cel al AI-ului ar putea fi considerată ca aducând un câștig negativ celui din urmă. | ||
| + | |||
| + | Pentru o modularizare și reutilizare mai bună a codului, implementarea va înrola tipul de date ''Board'' în clasa de tipuri ''Consecutive'', definită în ''Consecutive.hs''. Este cerută apoi implementarea generică a algoritmului Minimax în fișierul ''AIMinimax.hs'', cât și particularizarea acestei implementări în funcția ''step''. Pentru a observa pas cu pas evoluția jocului, utilizați funcția ''userMode'' din același fișier. Testele aferente se găsesc în fișierul ''AIMinimaxTest.hs''. | ||
| == Precizări == | == Precizări == | ||
| * Unde este adecvat, se vor utiliza **funcționale**, în locul recursivității explicite. Cazurile evidente vor fi **depunctate**. | * Unde este adecvat, se vor utiliza **funcționale**, în locul recursivității explicite. Cazurile evidente vor fi **depunctate**. | ||
| * Încercați să exploatați la maxim **bibliotecile** ''[[http://hackage.haskell.org/package/base-4.7.0.0/docs/Data-List.html|Data.List]]'' și ''[[http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Sequence.html|Data.Sequence]]''. Ambele biblioteci vă pot fi utile atât pentru construirea tablei de joc, cât și pentru proiectarea algoritmilor de parcurgere a acesteia. | * Încercați să exploatați la maxim **bibliotecile** ''[[http://hackage.haskell.org/package/base-4.7.0.0/docs/Data-List.html|Data.List]]'' și ''[[http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Sequence.html|Data.Sequence]]''. Ambele biblioteci vă pot fi utile atât pentru construirea tablei de joc, cât și pentru proiectarea algoritmilor de parcurgere a acesteia. | ||
| + | |||
| == Resurse == | == Resurse == | ||
| - | * {{TODO|Arhiva de pornire}} | + | * {{15:teme:haskell-kalah:haskell-kalah.zip|Arhiva de pornire}} |
| Organizarea arhivei și modalitatea de rulare a testelor sunt descrise în fișierul ''readme.txt''. | Organizarea arhivei și modalitatea de rulare a testelor sunt descrise în fișierul ''readme.txt''. | ||
| Linia 51: | Linia 64: | ||
| * [[http://en.wikipedia.org/wiki/Kalah|Kalah]] | * [[http://en.wikipedia.org/wiki/Kalah|Kalah]] | ||
| * [[http://developoid.com/g/pocketmancala/|Pocket Mancala]] | * [[http://developoid.com/g/pocketmancala/|Pocket Mancala]] | ||
| + | * [[http://www.flashanywhere.net/en/puzzlegames/1450-mancala.html|Mancala Flash Game]] | ||
| * [[http://en.wikipedia.org/wiki/Minimax|Minimax]] | * [[http://en.wikipedia.org/wiki/Minimax|Minimax]] | ||
15/teme/haskell-kalah.1428480977.txt.gz · Ultima modificare: 2015/04/08 11:16 de către Lucian Mogoșanu
