Штучний інтелект

Науковий журнал

ISSN 2710-1673

ONLINE: ISSN 2710-1681

Шукати за:

Роком видання
Автором
Назвою статті

Класифікація способів покращення пошуку по дереву методом Монте-Карло, орієнтованих на особливості цього методу

Марченко О.І.1, Марченко О.О.1, Орлова М.М.1
1 Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Повний текст (PDF)

УДК: 004.023
Мова публікації: Українська
Stuc. intelekt. 2016; 21; (2):59-69

Анотація: У статті, на основі інформації з різних джерел про пошук по дереву методом Монте-Карло (MCTS), пропонується уточнена структура класифікації та перша версія класифікації способів покращення базової реалізації методу MCTS. У цій версії, на даний момент, розглянуті тільки суто теоретичні способи покращення етапів загальної схеми MCTS, які орієнтовані на особливості роботи цього методу. Передбачається, що запропонована класифікація може бути в подальшому розширена і використана для систематизації знань про метод MCTS та виявлення нових можливостей його покращення.

Ключові слова: задачі штучного інтелекту, дерева ігор, пошук в дереві, метод Монте-Карло, MCTS

Посилання:

  1. Марченко О. І. Структура та критерії класифікації способів реалізації та покращення пошуку по дереву методом Монте-Карло / О. І. Марченко, О. О. Марченко, М. М. Орлова. – Комп’ютерно-інтегровані технології: освіта, наука, виробництво, 2015. – № 21. – С. 51–57.
  2. Cameron Browne and others. A Survey of Monte Carlo Tree Search Methods // IEEE Trans. on Computational Intelligence and AI in Games. - Vol. 4. - No. 1. - March 2012.
  3. Garivier, A., Cappe, A. The KL-UCB algorithm for bounded stochastic bandits and beyond // Proc. 24th Ann. Conf. on Learning Theory (COLT’11), 2011, pp.359-376.
  4. Yun-Ching Liu, Yoshimasa Tsuruoka. Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search // Proc. 14th Int. Conf., ACG 2015, Leiden, The Netherlands, July 1-3 2015, pp. 53-64.
  5. Mark H. M. Winands, Yngvi Björnsson, and Jahn-Takeshi Saito. Monte Carlo Tree Search in Lines of Action // IEEE Trans. Comp. Intell. AI Games. - Vol. 2. - No. 4. - December 2010, pp.239-250.
  6. Cowling, P., Powley, E., Whitehouse, D.: Information set Monte Carlo tree search // IEEE Trans. Comp. Intell. AI Games. - Vol. 4. - No. 2. - June 2012, pp.120–143.
  7. Yun-Ching Liu, Yoshimasa Tsuruoka. Asymmetric Move Selection Strategies in Monte-Carlo Tree Search: Minimizing the Simple Regret at Max Nodes // Submitted on 8 May 2016 to the 2016 IEEE Comp. Intell. and Games Conference, pp.193-199.
  8. D. P. Helmbold and A. Parker-Wood. All-Moves-As-First Heuristics in Monte-Carlo Go // Proc. Int. Conf. Artif. Intell., Las Vegas, Nevada, 2009, pp. 605–610.
  9. Sylvain Gelly, Levente Kocsis, Marc Schoenauer, Michèle Sebag, David Silver, Csaba Szepesvári, and Olivier Teytaud. The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions. // Communications of the ACM, - Vol. 55, - No. 3, - March 2012, pp.106-113.
  10. Tristan Cazenave. Generalized Rapid Action Value Estimation // Proc. 24th Int. Conf. on Art. Intell., IJCAI 2015, Buenos Aires, Argentina, July 26-27, 2015, pp 754-760.
  11. T. Pepels, T. Cazenave, and M.H.M. Winands. Sequential Halving for Partially Observable Games // Proc. 24th Int. Conf. on Art. Intell., IJCAI 2015, Buenos Aires, Argentina, July 26-27, 2015, pp.16-29.
  12. Hendrik Baier and Mark H. M. Winands. MCTS-Minimax Hybrids // IEEE Trans. Comp. Intell. AI Games. - Vol. 7. - No. 2. - June 2015, pp. 167-179.
  13. S. Ontanon. The combinatorial multi-armed bandit problem and its application to real-time strategy games // Proc. 9th AAAI Conf. Artif. Intell. Interact. Dig. Entertainment 2013, pp.58-64.
  14. J.-T. Saito, G. Chaslot, Jos W.H.M. Uiterwijk, and H. J. van den Herik. Monte-Carlo Proof-Number Search for Computer Go // Proc. 5th Int. Conf. Comput. and Games, Turin, Italy, 2006, pp. 50–61.
  15. H. Baier and P. D. Drake.The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte Carlo Go Trees// IEEE Trans. Comp. Intell. AI Games. - Vol. 2. - No. 4. - December 2010, pp. 303-309.
  16. Fern and P. Lewis. Ensemble Monte-Carlo Planning: An Empirical Study // Proc. 21st Int. Conf. Automat. Plan. Sched., Freiburg, Germany, 2011, pp. 58–65.
  17. R. Ramanujan and B. Selman. Trade-offs in sampling-based adversarial planning // Proc. 21st Int. Conf. Automat. Plan. Sched., Freiburg, Germany, 2011, pp.202-209.
  18. Thomas Keller, Malte Helmert. Trial-based Heuristic Tree Search for Finite Horizon MDPs // [Електр. Ресурс]. Режим доступу: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS13/paper/view/6026.
  19. Zohar Feldman, Carmel Domshlak. On MABs and Separation of Concerns in Monte-Carlo Planning for MDPs // Proc. 24th Int. Conf. Automat. Plan. Sched., pp.120-127.
  20. G. M. J.-B. Chaslot, M. H. M. Winands, and H. J. van den Herik. Parallel Monte-Carlo Tree Search // Proc. Comput. And Games, LNCS 5131, Beijing, China, 2008, pp. 60–71.

Переглянути повний текст статті (PDF)