Methods of MCTS and the game Arimaa
| Thesis title in Czech: | MCTS techniky ve hře Arimaa |
|---|---|
| Thesis title in English: | Methods of MCTS and the game Arimaa |
| Academic year of topic announcement: | 2008/2009 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | RNDr. Jan Hric |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 27.11.2008 |
| Date of assignment: | 03.12.2008 |
| Date and time of defence: | 21.09.2009 00:00 |
| Date of electronic submission: | 21.09.2009 |
| Date of proceeded defence: | 21.09.2009 |
| Opponents: | Mgr. Vladan Majerech, Dr. |
| Guidelines |
| A student exploites possibilities of the MCTS method (Monte Carlo + UCT algorithm [1]) in the strategic board game Arimaa [2]. He suggests and implements computer player based on this techniques.
He investigates possibilities of integration a static evaluation function into Monte Carlo simulations. He tries variants and extensions of the MCTS method described in literature (e.g. for the game Go [3],[4],[5],[6]) or his own and adapts them for the game Arimaa. |
| References |
| [1] Levente Kocsis and Csaba Szepesvári: Bandit Based Monte-Carlo Planning. In: European Conference on Machine learning, ECML-06, LNCS 4212, Springer 2006, pp. 282-293
[2] Omar Syed: Arimaa: A New Game Designed to be Difficult for Computers. ICGA Journal Vol. 26, No.2, pp.138-139. [3] Sylvain Gelly and Yizao Wang. Exploration Exploitation in Go: UCT for Monte-Carlo Go, On-line Trading of Exploration and Exploitation, NIPS 2006 Workshop, Whistler, Canada, 2006 [4] Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier Teytaud: Modification of UCT with Patterns in Monte-Carlo Go, TR 6062, INRIA, November 2006 [5] Guillaume Chaslot, Mark H. M. Winands, H. Jaap van den Herik, Jos Uiterwijk, and Bruno Bouzy. Progressive Strategies for Monte-Carlo Tree Search. In: Joint Conference on Information Sciences, Salt Lake City 2007, 10th International Conference on Computer Science & Informatics (CSI), 2007, pp. 655-661 [6] Sylvain Gelly, David Silver: Combining Online and Offline Knowledge in UCT. International Conference on Machine Learning (ICML), ACM, 2007, pp.273-280 |
| Preliminary scope of work |
| Metody MCTS a hra Arimaa.
Prozkoumejte možnosti uplatnění MCTS metod (Monte Carlo + UCT algoritmus [1]) ve strategické deskové hře Arimaa [2], navrhněte a implementujte počítačového hráče postaveného na těchto technikách. Vyšetřete možnosti integrace statické ohodnocovací funkce do Monte Carlo simulací. Vyzkoušejte varianty a rozšíření MCTS (popsané v literatuře např. pro hru go [3],[4],[5],[6]) nebo vlastní a upravte je pro hru Arimaa. |