Řízení prohledávání stromů hry
| Thesis title in Czech: | Řízení prohledávání stromů hry |
|---|---|
| Thesis title in English: | A Controlled Searching of Game Trees |
| Key words: | MCTS, UCT, BMCTS, RAVE |
| English key words: | MCTS, UCT, BMCTS, RAVE |
| Academic year of topic announcement: | 2015/2016 |
| Thesis type: | Bachelor's 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: | 28.02.2016 |
| Date of assignment: | 08.04.2016 |
| Confirmed by Study dept. on: | 02.05.2016 |
| Date and time of defence: | 31.01.2018 00:00 |
| Date of electronic submission: | 03.01.2018 |
| Date of submission of printed version: | 01.01.2018 |
| Date of proceeded defence: | 31.01.2018 |
| Opponents: | Mgr. Vladan Majerech, Dr. |
| Guidelines |
| Klasická metoda prohledávání a rozvíjení stromu v MCTS (Monte carlo tree search) pro nějakou hru nebo situaci je založena na metodě UCT (Upper confidence bound for trees) [2], která vyvažuje zkoumání nových možností (tj. tahů) a využívání již známé informace (tzv. exploration vs. exploitation dilema). Tato metoda přitom nevyužívá explicitních informací např. o tvaru stromu (hloubka, šířka), ani o případných heuristických hodnotách jako alfa-beta prohledávání. Dále tato metoda při rozvíjení vrcholu každý možný tah nejdřív jednou vyzkouší a to způsobuje velké paměťové nároky.
Cílem práce je integrovat do MCTS metody, které umožní uživateli a/anebo vlastnímu programu na základě výsledků vykonaných playoutů (náhodných Monte carlo sehrávek) nastavovat parametry stromu a tím regulovat paměťovou náročnost. Použitelnost a chování těchto metod bude otestováno na modelových problémech her dvou nebo jednoho hráče. |
| References |
| [1] P. Norvig, S. Russell, Artificial Intelligence - A Modern Approach, Prentice Hall, 2003
[2] C. Browne, E. Powley, D. Whitehouse et. al., A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, IEEE, vol. 4, No. 1, 2012 [3] Sylvain Gelly, David Silver, Combining online and offline knowledge in UCT. In: ICML'07: Proceedings of the 24th International Conference on Machine Learning, New York, USA, ACM 2007, pp. 273-280 |