Řešení problémů pomocí MCTS
| Thesis title in Czech: | Řešení problémů pomocí MCTS |
|---|---|
| Thesis title in English: | Solving of Problems using MCTS |
| Key words: | MCTS, Go, Sudoku, SameGame, UCT |
| English key words: | MCTS, Go, Sudoku, SameGame, UCT |
| Academic year of topic announcement: | 2009/2010 |
| Thesis type: | diploma thesis |
| Thesis language: | češ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: | 17.12.2009 |
| Date of assignment: | 17.12.2009 |
| Date and time of defence: | 06.09.2010 00:00 |
| Date of electronic submission: | 05.08.2010 |
| Date of submission of printed version: | 05.08.2010 |
| Date of proceeded defence: | 06.09.2010 |
| Opponents: | Mgr. Vladan Majerech, Dr. |
| Guidelines |
| Metody založené na Monte Carlo Tree Search (MCTS) se uplatnili při vývoji programů pro počítačové go, t.j. pro hru dvou hráčů. Cílem práce je zjistit, jak lze tyto metody aplikovat na "hru" jednoho hráče, teda úlohy s prohledáváním stavového prostoru.
Diplomant se seznámí s MCTS a adaptuje tento přístup pro prohledávání stavového prostoru. V této nové doméně prozkoumá známé, případně navrhne nové varianty propagace ohodnocení a náhodných playoutů. Některé slibné varianty implementuje, experimentálně prověří a kriticky zhodnotí. |
| References |
| S. Russell, P. Norvig: Artificial Intelligence, A Modern Approach, Prentice Hall,
1995 Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud: Modification of UCT with patterns in Monte-Carlo Go. TR 6062, INRIA, France, 2006 Sylvain Gelly, David Silber: Combining online and offline knowledge in uct, Proc. ICML'07, ACM, New York, NY, USA, pp. 273-280 |
| Preliminary scope of work |
| Metody založené na Monte Carlo Tree Search se uplatnili při vývoji programů pro počítačové go, t.j. pro hru dvou hráčů. Cílem práce je zjistit, zda lze tyto metody s výhodou aplikovat na "hru" jednoho hráče, ať už v existenční nebo optimalizační variantě.
Varianty: Dále/vedle je možné zkoumat, jak tuto metodu sloučit s jinými známými metodami a/anebo heuristikami pro řešení problémů, ať z hlediska implementace sloučení anebo synergického výsledku sloučení. Které techniky (a jak) lze aplikovat na některý konkrétní (optimalizační) problém. |