DocumentCode :
188721
Title :
Knowledge Complement for Monte Carlo Tree Search: An Application to Combinatorial Games
Author :
Fabbri, Andre ; Armetta, Frederic ; Duchene, Eric ; Hassas, Salima
Author_Institution :
LIRIS, Univ. de Lyon, Lyon, France
fYear :
2014
fDate :
10-12 Nov. 2014
Firstpage :
997
Lastpage :
1003
Abstract :
MCTS (Monte Carlo Tree Search) is a well-known and efficient process to cover and evaluate a large range of states for combinatorial problems. We choose to study MCTS for the Computer Go problem, which is one of the most challenging problem in the field in Artificial Intelligence. For this game, a single combinatorial approach does not always lead to a reliable evaluation of the game states. In order to enhance MCTS ability to tackle such problems, one can benefit from game specific knowledge in order to increase the accuracy of the game state evaluation. Such a knowledge is not easy to acquire. It is the result of a constructivist learning mechanism based on the experience of the player. That is why we explore the idea to endow the MCTS with a process inspired by constructivist learning, to self-acquire knowledge from playing experience. In this paper, we propose a complementary process for MCTS called BHRF (Background History Reply Forest), which allows to memorize efficient patterns in order to promote their use through the MCTS process. Our experimental results lead to promising results and underline how self-acquired data can be useful for MCTS based algorithms.
Keywords :
Monte Carlo methods; computer games; game theory; learning (artificial intelligence); tree searching; BHRF; Computer Go problem; MCTS; Monte Carlo tree search; artificial intelligence; background history reply forest; combinatorial games; combinatorial problems; constructivist learning mechanism; game state evaluation; knowledge complement; Computational modeling; Context; Data structures; Games; History; Monte Carlo methods; Vegetation; Computer-Game; Knowledge Engineering; Monte Carlo Tree Search; Reinforcement Learning;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International Conference on
Conference_Location :
Limassol
ISSN :
1082-3409
Type :
conf
DOI :
10.1109/ICTAI.2014.151
Filename :
6984587
Link To Document :
بازگشت