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

fYear

2014

fDate

6-11 July 2014

Firstpage

2290

Lastpage

2297

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2014 IEEE Congress on

Conference_Location

Beijing

Print_ISBN

978-1-4799-6626-4

Type

conf

DOI

10.1109/CEC.2014.6900583

Filename

6900583