Building of Searching Tree by the Technique Using Monte-Carlo Tree Search Method with Tree Shape Control
Keywords:
game trees, tree search, Monte-Carlo method, MCTS, MCTS parallelizing techniques, grid-systemsAbstract
The paper describes in details mechanism of the tree-shape control technique influence onto searching process with usage of the Monte-Carlo tree search (MCTS) method. Comparison of the tree-shape control technique for MCTS implementation with the standard technique of this method implementation is done. It is shown that in case when coefficients are taken well, usage of the MCTS implementation with tree-shape control follows in increasing of the search performance and better decisions.
References
1. A Survey of Monte Carlo Tree Search Methods / [Cameron Browne, Edward Powley, Daniel Whitehouse, and others] // IEEE Trans. on Computational Intelligence and AI in Games. — March 2012. — Vol. 4. — No. 1. — P. 1—49.
2. Марченко О. І. Структура та критерії класифікації способів реалізації та покращення пошуку по дереву методом Монте-Карло / О. І. Марченко, О. О. Марченко, М. М. Орлова // Комп’ютерно-інтегровані технології: освіта, наука, виробництво. — 2015. — № 21. — С. 51—57.
3. Марченко О. І. Класифікація способів реалізації та покращення пошуку по дереву методом Монте-Карло / О. І. Марченко, О. О. Марченко, М. М. Орлова // Штучний інтелект. — 2016. — № 2 (72). — С. 59—69.
4. Alan Levinovitz. The Mystery of Go, the Ancient Game That Computers Still Can't Win. [Електронний ресурс] / Alan Levinovitz. — Режим доступу: https://www.wired.com/2014/05/the-world-of-computer-go/ .
5. Marchenko O. I. Monte-Carlo Tree Search with Tree Shape Control / Oleksandr I. Marchenko, Oleksii O. Marchenko // 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). Conference Proceedings. May 29 — June 2, 2017., Kyiv, Ukraine. — 2017. — P. 812—8173.
6. Hilmar Finnsson. Game-Tree Properties and MCTS Performance / Hilmar Finnsson and Yngvi Björnsson // GIGA 2011: Proceedings of the 2nd International General Game Playing Workshop, 2011. Pp. 23—30.
7. Марченко О. О. Критерій «глибина-ширина» для контролю форми дерева пошуку при використанні методу Монте-Карло / О. І. Марченко, О. О. Марченко // Комп’ютерно-інтегровані технології: освіта, наука, виробництво. — 2016. — № 24—25. — С. 42—47.
8. G. M. J. Williams. Determining Game Quality Through UCT Tree Shape Analysis / G. M. J. Williams // M.S. thesis, Imperial Coll., London. — 2010.
9. Yizao Wang. Modifications of UCT and sequence-like simulations for Monte-Carlo Go / Yizao Wang, Sylvain Gelly // Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Games. — 2007. — P. 175—182.
10. Connect Four [Електронний ресурс]. — Режим доступу: https://en.wikipedia.org/wiki/Connect_Four .
2. Марченко О. І. Структура та критерії класифікації способів реалізації та покращення пошуку по дереву методом Монте-Карло / О. І. Марченко, О. О. Марченко, М. М. Орлова // Комп’ютерно-інтегровані технології: освіта, наука, виробництво. — 2015. — № 21. — С. 51—57.
3. Марченко О. І. Класифікація способів реалізації та покращення пошуку по дереву методом Монте-Карло / О. І. Марченко, О. О. Марченко, М. М. Орлова // Штучний інтелект. — 2016. — № 2 (72). — С. 59—69.
4. Alan Levinovitz. The Mystery of Go, the Ancient Game That Computers Still Can't Win. [Електронний ресурс] / Alan Levinovitz. — Режим доступу: https://www.wired.com/2014/05/the-world-of-computer-go/ .
5. Marchenko O. I. Monte-Carlo Tree Search with Tree Shape Control / Oleksandr I. Marchenko, Oleksii O. Marchenko // 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). Conference Proceedings. May 29 — June 2, 2017., Kyiv, Ukraine. — 2017. — P. 812—8173.
6. Hilmar Finnsson. Game-Tree Properties and MCTS Performance / Hilmar Finnsson and Yngvi Björnsson // GIGA 2011: Proceedings of the 2nd International General Game Playing Workshop, 2011. Pp. 23—30.
7. Марченко О. О. Критерій «глибина-ширина» для контролю форми дерева пошуку при використанні методу Монте-Карло / О. І. Марченко, О. О. Марченко // Комп’ютерно-інтегровані технології: освіта, наука, виробництво. — 2016. — № 24—25. — С. 42—47.
8. G. M. J. Williams. Determining Game Quality Through UCT Tree Shape Analysis / G. M. J. Williams // M.S. thesis, Imperial Coll., London. — 2010.
9. Yizao Wang. Modifications of UCT and sequence-like simulations for Monte-Carlo Go / Yizao Wang, Sylvain Gelly // Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Games. — 2007. — P. 175—182.
10. Connect Four [Електронний ресурс]. — Режим доступу: https://en.wikipedia.org/wiki/Connect_Four .
Downloads
-
PDF (Українська)
Downloads: 212
Abstract views: 148
Published
2017-08-31
How to Cite
[1]
O. O. Marchenko, O. I. Marchenko, and B. O. Shcherbyna, “Building of Searching Tree by the Technique Using Monte-Carlo Tree Search Method with Tree Shape Control”, Вісник ВПІ, no. 4, pp. 65–69, Aug. 2017.
Issue
Section
Information technologies and computer sciences
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
