MCTS a heuristiky

• Thesis title in Czech: MCTS a heuristiky
• Thesis title in English: MCTS and heuristics
• Academic year of topic announcement: 2012/2013
• 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: 23.09.2013
• Date of assignment: 23.09.2013
• Confirmed by Study dept. on: 21.10.2013

Guidelines

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.

References

[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.