Řešení problémů pomocí MCTS
| Název práce v češtině: | Řešení problémů pomocí MCTS |
|---|---|
| Název v anglickém jazyce: | Solving of Problems using MCTS |
| Klíčová slova: | MCTS, Go, Sudoku, SameGame, UCT |
| Klíčová slova anglicky: | MCTS, Go, Sudoku, SameGame, UCT |
| Akademický rok vypsání: | 2009/2010 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Jan Hric |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 17.12.2009 |
| Datum zadání: | 17.12.2009 |
| Datum a čas obhajoby: | 06.09.2010 00:00 |
| Datum odevzdání elektronické podoby: | 05.08.2010 |
| Datum odevzdání tištěné podoby: | 05.08.2010 |
| Datum proběhlé obhajoby: | 06.09.2010 |
| Oponenti: | Mgr. Vladan Majerech, Dr. |
| Zásady pro vypracování |
| 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í. |
| Seznam odborné literatury |
| 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 |
| Předběžná náplň práce |
| 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. |