ПОБУДОВА ДЕРЕВА ПОШУКУ СПОСОБОМ З ВИКОРИСТАННЯМ МЕТОДУ МОНТЕ-КАРЛО І КОНТРОЛЕМ ФОРМИ ДЕРЕВА
Ключові слова:
дерева ігор, пошук в дереві, метод Монте-Карло, MCTS, способи покращення MCTSАнотація
Детально описано механізм впливу способу контролю форми дерева пошуку на процес виконання пошуку в дереві методом Монте-Карло (MCTS). Виконано порівняння способу реалізації MCTS з контролем форми дерева зі стандартним способом реалізації цього методу. Показано, що за правильного підбору коефіцієнтів використання способу реалізації MCTS з контролем форми дерева приводить до підвищення результативності пошуку і, в результаті, до прийняття кращих рішень.
Посилання
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 .
##submission.downloads##
-
PDF
Завантажень: 210
Переглядів анотації: 148
Опубліковано
2017-08-31
Як цитувати
[1]
О. О. Марченко, О. І. Марченко, і Б. О. Щербина, «ПОБУДОВА ДЕРЕВА ПОШУКУ СПОСОБОМ З ВИКОРИСТАННЯМ МЕТОДУ МОНТЕ-КАРЛО І КОНТРОЛЕМ ФОРМИ ДЕРЕВА», Вісник ВПІ, вип. 4, с. 65–69, Серп. 2017.
Номер
Розділ
Інформаційні технології та комп'ютерна техніка
Ліцензія
Автори, які публікуються у цьому журналі, згодні з такими умовами:
- Автори зберігають авторське право і надають журналу право першої публікації.
- Автори можуть укладати окремі, додаткові договірні угоди з неексклюзивного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опублікувати її в книзі), з визнанням її первісної публікації в цьому журналі.
- Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, оскільки це сприяє продуктивним обмінам, а також швидшому і ширшому цитуванню опублікованих робіт (див. вплив відкритого доступу).
