On Monte Carlo Tree Search and Reinforcement Learning

Fuelled by successes in Computer Go, Monte Carlo tree search (MCTS) has achieved widespread adoption within the games community. Its links to traditional reinforcement learning (RL) methods have been outlined in the past; however, the use of RL techniques within tree search has not been thoroughly s...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2017-01, Vol.60, p.881-936
Main Authors: Vodopivec, Tom, Samothrakis, Spyridon, Ster, Branko
Format: Article
Language:English
Subjects:
Artificial intelligence
Computer & video games
Machine learning
Monte Carlo simulation
Search algorithms
Searching
Semantics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Fuelled by successes in Computer Go, Monte Carlo tree search (MCTS) has achieved widespread adoption within the games community. Its links to traditional reinforcement learning (RL) methods have been outlined in the past; however, the use of RL techniques within tree search has not been thoroughly studied yet. In this paper we re-examine in depth this close relation between the two fields; our goal is to improve the cross-awareness between the two communities. We show that a straightforward adaptation of RL semantics within tree search can lead to a wealth of new algorithms, for which the traditional MCTS is only one of the variants. We confirm that planning methods inspired by RL in conjunction with online search demonstrate encouraging results on several classic board games and in arcade video game competitions, where our algorithm recently ranked first. Our study promotes a unified view of learning, planning, and search.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.5507