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:haskell-mcts [2017/04/08 22:38] Mihnea Muraru [Precizări] |
17:teme:haskell-mcts [2017/04/19 15:33] (curent) Mihnea Muraru [Haskell: Monte Carlo Tree Search] |
||
---|---|---|---|
Linia 2: | Linia 2: | ||
* Responsabil: [[mmihnea@gmail.com|Mihnea Muraru]] | * Responsabil: [[mmihnea@gmail.com|Mihnea Muraru]] | ||
- | * Deadline soft: **24.04.2017**, apoi depunctare 0.5p/ zi | + | * Deadline soft: **30.04.2017**, apoi depunctare 0.5p/ zi |
- | * Deadline hard: __29.04.2017 ora 23.59__ | + | * Deadline hard: __03.05.2017 ora 23.59__ |
* Data publicării: 08.04.2017 | * Data publicării: 08.04.2017 | ||
* Data ultimei modificări: 08.04.2017 | * Data ultimei modificări: 08.04.2017 | ||
* Tema se va încărca pe **[[https://elf.cs.pub.ro/vmchecker/ui/#PP|vmchecker]]** | * Tema se va încărca pe **[[https://elf.cs.pub.ro/vmchecker/ui/#PP|vmchecker]]** | ||
- | * Data tester-ului: în curând | + | * Data tester-ului: 17.04.2017 |
- | * Forum temă | + | * [[http://cs.curs.pub.ro/2016/mod/forum/view.php?id=5487|Forum temă]] |
== Obiective == | == Obiective == | ||
- | * Utilizarea mecanismelor **funcționale**, de **tipuri**, și de **evaluare leneșă** din limbajul Haskell pentru rezolvarea unei probleme de **căutare** în spațiul stărilor unei probleme. | + | * Utilizarea mecanismelor **funcționale**, de **tipuri**, și de **evaluare leneșă** din limbajul Haskell pentru rezolvarea unei probleme de **căutare** în spațiul stărilor. |
* Exploatarea evaluării leneșe pentru **decuplarea** etapelor de construcție și de explorare a arborelui de căutare. | * Exploatarea evaluării leneșe pentru **decuplarea** etapelor de construcție și de explorare a arborelui de căutare. | ||
* Utilizarea unor mecanisme eficiente, **//zipper//**-e, pentru alterarea unor structuri nemodificabile, caracteristice limbajelor funcționale. | * Utilizarea unor mecanisme eficiente, **//zipper//**-e, pentru alterarea unor structuri nemodificabile, caracteristice limbajelor funcționale. | ||
Linia 24: | Linia 24: | ||
//[[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|Monte Carlo Tree Search]]// (MCTS) este un algoritm de **căutare** în spațiul stărilor unei probleme, având drept scop alegerea unei acțiuni de realizat, pornind dintr-o stare oarecare. Este un algoritm des utilizat, fiind implicat și în sistemul //[[https://en.wikipedia.org/wiki/AlphaGo|Alpha Go]]//, care a obținut în 2015 prima victorie semnificativă a unui jucător artificial de Go împotriva unui expert uman. | //[[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|Monte Carlo Tree Search]]// (MCTS) este un algoritm de **căutare** în spațiul stărilor unei probleme, având drept scop alegerea unei acțiuni de realizat, pornind dintr-o stare oarecare. Este un algoritm des utilizat, fiind implicat și în sistemul //[[https://en.wikipedia.org/wiki/AlphaGo|Alpha Go]]//, care a obținut în 2015 prima victorie semnificativă a unui jucător artificial de Go împotriva unui expert uman. | ||
- | Spre deosebire de algoritmul Minimax, care uitilizează o funcție de evaluare a unei stări oarecare, și presupune cunoștințe despre specificul jocului respectiv, MCTS nu necesită astfel de informații. În schimb, el implică **simularea** unui număr mare de jocuri aleatoare, pornind din starea curentă, **până la final**, și alegerea ulterioară a acelei acțiuni care maximizează o anumită măsură, precum numărul mediu de victorii obținute realizând acea acțiune, ținând cont de numărul total de simulări ale acțiunii respective. | + | Spre deosebire de algoritmul Minimax, care utilizează o funcție de evaluare a unei stări oarecare, și presupune cunoștințe despre specificul jocului respectiv, MCTS nu necesită astfel de informații. În schimb, el implică **simularea** unui număr mare de jocuri aleatoare, pornind din starea curentă, **până la final**, și alegerea ulterioară a acelei acțiuni care maximizează o anumită măsură, precum numărul mediu de victorii obținute realizând acea acțiune, ținând cont de numărul total de simulări ale acțiunii respective. |
O explicație excelentă a algoritmului, pentru cazul unui **singur** jucător, alături de un exemplu de aplicare, se găsește în acest **[[https://www.youtube.com/watch?v=UXW2yZndl7U|filmuleț]]**, pe care vă rugăm să îl urmăriți. | O explicație excelentă a algoritmului, pentru cazul unui **singur** jucător, alături de un exemplu de aplicare, se găsește în acest **[[https://www.youtube.com/watch?v=UXW2yZndl7U|filmuleț]]**, pe care vă rugăm să îl urmăriți. | ||
Linia 52: | Linia 52: | ||
=== MCTS pentru oricâți jucători (20p) === | === MCTS pentru oricâți jucători (20p) === | ||
- | Această cerință solicită ca implementarea voastră să fie suficient de flexibilă, încât să permită existența **oricâtor** jucători. **Singura diferență** față de cazul unui singur jucător este întâlnită în cadrul pasului de **//backpropagation//**. Spre deosebire de situația anterioară, în care erau actualizate toate nodurile de pe calea către rădăcină, acum, vor fi actualizate **selectiv** doar nodurile aferente mutărilor jucătorului care a câștigat, sau toate nodurile, în caz de remiză. Toate nodurile vor fi marcate ca vizitate. Explicațiile detaliate se găsesc direct în surse. | + | Această cerință solicită ca implementarea voastră să fie suficient de flexibilă, încât să permită existența **oricâtor** jucători. **Singura diferență** față de cazul unui singur jucător este întâlnită în cadrul pasului de **//backpropagation//**. Spre deosebire de situația anterioară, în care erau actualizate scorurile tuturor nodurilor de pe calea către rădăcină, acum, vor fi actualizate **selectiv** doar scorurile nodurilor aferente mutărilor jucătorului care a câștigat, sau ale tuturor nodurilor, în caz de remiză. Toate nodurile vor fi marcate ca vizitate. Explicațiile detaliate se găsesc direct în surse. |
Nici pentru această cerință nu este necesar să instanțiați clasa ''GameState'', cu toate că veți utiliza **și** funcțiile ''playerIndex'' și ''maxPlayers'' definite de ea. | Nici pentru această cerință nu este necesar să instanțiați clasa ''GameState'', cu toate că veți utiliza **și** funcțiile ''playerIndex'' și ''maxPlayers'' definite de ea. | ||
=== Bonus: Aplicare MCTS pentru jocul „X și 0” (20p) === | === Bonus: Aplicare MCTS pentru jocul „X și 0” (20p) === | ||
- | Pentru bonus, vi se propune să **aplicați** algoritmul MCTS implementat în cazul jocului **„X și 0”**, astfel încât utilizatorul (X) să poată juca cu calculatorul (0). Pentru aceasta, veți implementa funcțiile din fișierul ''TicTacToe.hs''. | + | Pentru bonus, vi se propune să **aplicați** algoritmul MCTS implementat în cazul jocului **„X și 0”**, astfel încât utilizatorul (X) să poată juca cu calculatorul (0). Pentru aceasta, veți implementa funcțiile din fișierul ''TicTacToe.hs'', dar, de data aceasta, veți instanția şi clasa **''GameState''**. |
Funcțiile din fișierul ''Interactive.hs'' pot fi folosite pentru a **interacționa** cu programul. Odată ce ați implementat jocul de „X și 0”, utilizați ''twoHumans'' pentru doi utilizatori umani, sau ''humanVsAI step'', pentru jocul utilizatorului cu calculatorul, unde ''step'' este funcția de alegere a următoarei mutări, pe care trebuie să o implementați pe baza MCTS. | Funcțiile din fișierul ''Interactive.hs'' pot fi folosite pentru a **interacționa** cu programul. Odată ce ați implementat jocul de „X și 0”, utilizați ''twoHumans'' pentru doi utilizatori umani, sau ''humanVsAI step'', pentru jocul utilizatorului cu calculatorul, unde ''step'' este funcția de alegere a următoarei mutări, pe care trebuie să o implementați pe baza MCTS. | ||
Linia 63: | Linia 63: | ||
* Este indicată utilizarea **funcționalelor**. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct). Implementarea se poate realiza **în întregime fără** recursivitate explicită, utilizând funcționale și alte funcții de bibliotecă. | * Este indicată utilizarea **funcționalelor**. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct). Implementarea se poate realiza **în întregime fără** recursivitate explicită, utilizând funcționale și alte funcții de bibliotecă. | ||
+ | * Având în vedere că multe dintre funcțiile din fișierul ''MCTS.hs'' presupun repetarea unei operații până la validarea unei condiții, puteți utiliza funcționala **''[[http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:until|until]]''**. | ||
+ | * Utilizați **''[[http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:fromIntegral|fromIntegral]]''** pentru conversia de la ''Int'' la ''Float''. | ||
== Resurse == | == Resurse == | ||
+ | |||
+ | * {{:17:teme:haskell-mcts.zip|Arhiva de pornire}} (schelet + tester) | ||
== Referințe == | == Referințe == | ||
+ | |||
+ | * //[[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|Monte Carlo Tree Search]]//, Wikipedia | ||
+ | * [[https://www.youtube.com/watch?v=UXW2yZndl7U|Tutorial MCTS]], Youtube | ||
+ | * [[http://learnyouahaskell.com/zippers|Tutorial Zipper-e]], Learn You a Haskell | ||
+ | |||
+ | == Changelog == | ||
+ | |||
+ | * [11.04 11:25] A fost adăugată funcția de acces ''treeChildren'' în fișierul ''MCTS.hs''. | ||
+ | * [17.04 18:45] A fost adăugat tester-ul. |