Parallel Monte-Carlo Tree Search with Simulation Servers
Hideki Kato, IKUO K. TAKEUCHI · 2010
Monte-Carlo tree search is a new best-first tree search algorithm that triggered a revolution in the computer Go world. Developing good parallel Monte-Carlo tree search algorithms is importan because single processor's performance cannot be expected to increase as used to. A novel parallel Monte-Carlo tree search algorithm is proposed. A tree searcher runs on a client computer and multiple Monte-Carlo simulators run on other computers (simulation servers) on a network. The tree searcher broadcasts a position being simulated to every simulator, which then simulates the game from the position to the end and sends the result back to the searcher, if not busy. The statistical information in the search tree is updated by the searcher according to the result. This algorithm can run on a loosely coupled heterogeneous computer cluster, consists of inexpensive personal computers and game consoles, on a moderate speed network and allows users to connect or disconnect the servers on-the-fly, in contrast to ones run on an expensive HPC cluster. Experiments using four quad-core Linux personal computers on a private Gigabit Ethernet LAN show its performance scales well.