Artificial intelligence

Scientific journal

ISSN 2710-1673

ONLINE: ISSN 2710-1681

Search by:

Year of publication
Author name
Paper title

Classification of Monte-Carlo tree search enhancement techniques oriented to specifics of the method

Marchenko O.1, Marchenko O.1, Orlova M.1
1 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

Full text (PDF)

UDC: 004.023
Publication Language: Ukrainian
Stuc. intelekt. 2016; 21(2):59-69

Abstract: In the article basing on information taken from various sources about Monte-Carlo tree search (MCTS) method, the updated structure of classification and the first version of just the classification of improvement techniques of the basic MCTS method implementation are proposed. For the moment, this version of the classification discusses only pure theoretical techniques for improving of steps of the general MCTS schema, which are oriented to specifics of the method. It is supposed that the proposed classification can be used for systematization of knowledge about MCTS method and discovering of new possibilities for its improvement.

Keywords: artificial intelligence tasks, game trees, tree search, Monte-Carlo method, MCTS

References:

  1. Marchenko O. I. Struktura ta kryteriyi klasyfikatsiyi sposobiv realizatsiyi ta pokrashchennya poshuku po derevu metodom Monte-Karlo / O. I. Marchenko, O. O. Marchenko, M. M. Orlova. – Komp"yuternointehrovani tekhnolohiyi: osvita, nauka, vyrobnytstvo, 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.

View full text (PDF)