Unelte utilizator
17:teme:haskell-mcts
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:haskell-mcts [2017/04/08 22:45] 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 67: | Linia 67: | ||
| == 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. | ||
17/teme/haskell-mcts.1491680729.txt.gz · Ultima modificare: 2017/04/08 22:45 de către Mihnea Muraru
