×

Scalability and parallelization of Monte-Carlo tree search. (English) Zbl 1316.68134

van den Herik, H. Jaap (ed.) et al., Computers and games. 7th international conference, CG 2010, Kanazawa, Japan, September 24–26, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-17927-3/pbk). Lecture Notes in Computer Science 6515, 48-58 (2011).
Summary: Monte-Carlo Tree Search is now a well established algorithm, in games and beyond. We analyze its scalability, and in particular its limitations and the implications in terms of parallelization. We focus on our Go program MoGo and our Havannah program Shakti. We use multicore machines and message-passing machines. For both games and on both type of machines we achieve adequate efficiency for the parallel version. However, in spite of promising results in self-play there are situations for which increasing the time per move does not solve anything. Therefore parallelization is not a solution to all our problems. Nonetheless, for problems where the Monte-Carlo part is less biased than in the game of Go, parallelization should be quite efficient, even without shared memory.
For the entire collection see [Zbl 1206.68025].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W10 Parallel algorithms in computer science
91A46 Combinatorial games
91A90 Experimental studies

Keywords:

computer Go
PDFBibTeX XMLCite
Full Text: DOI Link