Title :
Parallelization of Information Set Monte Carlo Tree Search
Author :
Sephton, Nick ; Cowling, Peter I. ; Powley, Edward ; Whitehouse, Daniel ; Slaven, Nicholas H.
Author_Institution :
Dept. of Comput. Sci., Univ. of York, York, UK
Abstract :
Process parallelization is more important than ever, as most modern hardware contains multiple processors and advanced multi-threading capability. This paper presents an analysis of the parallel behaviour of Information Set Monte Carlo Tree Search and the Upper Confidence Bounds for Trees (UCT) variant of MCTS, and certain parallelization techniques (specifically Tree Parallelization) have different effects upon ISM-CTS and Plain UCT. The paper presents a study of the relative effectiveness of different types of parallelization, including Root, Tree, Tree with Virtual Loss, and Leaf.
Keywords :
Monte Carlo methods; multi-threading; multiprocessing systems; tree searching; ISM-CTS; MCTS; advanced multithreading capability; information set Monte Carlo tree search parallelization; leaf parallelization; parallel behaviour; plain UCT; process parallelization; root parallelization; tree parallelization techniques; tree with virtual loss parallelization; upper confidence bound for trees; Artificial intelligence; Electronic mail; Games; Instruction sets; Mathematical model; Monte Carlo methods;
Conference_Titel :
Evolutionary Computation (CEC), 2014 IEEE Congress on
Conference_Location :
Beijing
Print_ISBN :
978-1-4799-6626-4
DOI :
10.1109/CEC.2014.6900583
