Řízení prohledávání stromů hry
| Název práce v češtině: | Řízení prohledávání stromů hry |
|---|---|
| Název v anglickém jazyce: | A Controlled Searching of Game Trees |
| Klíčová slova: | MCTS, UCT, BMCTS, RAVE |
| Klíčová slova anglicky: | MCTS, UCT, BMCTS, RAVE |
| Akademický rok vypsání: | 2015/2016 |
| Typ práce: | bakalářská 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í: | 28.02.2016 |
| Datum zadání: | 08.04.2016 |
| Datum potvrzení stud. oddělením: | 02.05.2016 |
| Datum a čas obhajoby: | 31.01.2018 00:00 |
| Datum odevzdání elektronické podoby: | 03.01.2018 |
| Datum odevzdání tištěné podoby: | 01.01.2018 |
| Datum proběhlé obhajoby: | 31.01.2018 |
| Oponenti: | Mgr. Vladan Majerech, Dr. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| [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 |