DocumentCode :
3147253
Title :
Large-Scale Parallel Monte Carlo Tree Search on GPU
Author :
Rocki, Kamil ; Suda, Reiji
Author_Institution :
Dept. of Comput. Sci., Univ. of Tokyo, Tokyo, Japan
fYear :
2011
fDate :
16-20 May 2011
Firstpage :
2034
Lastpage :
2037
Abstract :
Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search. The motivation behind this work is caused by the emerging GPU-based systems and their high computational potential combined with relatively low power usage compared to CPUs. As a problem to be solved I chose to develop an AI GPU(Graphics Processing Unit)-based agent in the game of Reversi (Othello) which provides a sufficiently complex problem for tree searching with non-uniform structure and an average branching factor of over 8. I present an efficient parallel GPU MCTS implementation based on the introduced ´block-parallelism´ scheme which combines GPU SIMD thread groups and performs independent searches without any need of intra-GPU or inter-GPU communication. I compare it with a simple leaf parallel scheme which implies certain performance limitations. The obtained results show that using my GPU MCTS implementation on the TSUBAME 2.0 system one GPU can be compared to 100-200 CPU threads depending on factors such as the search time and other MCTS parameters in terms of obtained results. I propose and analyze simultaneous CPU/GPU execution which improves the overall result.
Keywords :
Monte Carlo methods; artificial intelligence; computer games; computer graphic equipment; coprocessors; decision making; parallel processing; tree searching; AI GPU based agent; GPU SIMD thread groups; Othello; Reversi game; TSUBAME 2.0 system; artificial intelligence; block parallelism scheme; branching factor; combinatorial games; graphic processing to unit; inter-GPU communication; intra-GPU communication; large-scale parallel Monte Carlo tree search; nonuniform structure; optimal decision making; parallel GPU MCTS; random simulation; simultaneous CPU-GPU execution; Games; Graphics processing unit; Instruction sets; Kernel; Monte Carlo methods; Parallel processing; Search problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
ISSN :
1530-2075
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
Type :
conf
DOI :
10.1109/IPDPS.2011.370
Filename :
6009083
Link To Document :
بازگشت