MCTS a heuristiky

• Název práce v češtině: MCTS a heuristiky
• Název v anglickém jazyce: MCTS and heuristics
• Akademický rok vypsání: 2012/2013
• 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í: 23.09.2013
• Datum zadání: 23.09.2013
• Datum potvrzení stud. oddělením: 21.10.2013

Zásady pro vypracování

Monte Carlo Tree Search (MCTS) používá v zakladní variantě pro prohledávání prostoru řešení náhodné dohrání, tzv. playout. Pro některé optimalizační problémy (tj. hry 1 hráče) je ale možné nalézt pro playout heuristiky, které zvýhodňují lepší řešení.

Cílem práce je pro vhodný problém (nebo problémy) zjistit výhodné možnosti kombinování heuristik, které zlepší celkové chování MCTS prohledávání, resp. ukáže možné trade-off (mezi časem, pamětí, režií, počtem vyhodnocení, složitostí heuristiky ...).

Práce by měla prozkoumat možnosti kombinování několika heuristik (staticky i dynamicky) a porovnat s vnořeným MCTS. Heuristiky je možno používat vcelku anebo rozložit na jednotlivá rozhodnutí a způsobem založeným například na RAVE preferovat výhodnější rozhodnutí (ve stromě a/anebo playoutech).

Další, navazující části může být ověřit získané poznatky/hypotézy na syntetických datech.

Seznam odborné literatury

[1] S. Russell, P. Norvig: Artificial Intelligence, A Modern Approach, Prentice Hall, Englewood Cliffs, USA, 2003

[2] C. B. Browne, E. Powley, D. Whitehouse et al.; A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, vol 4, No 1, pp. 1-43, IEEE, 2012.