Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design
This work addresses the problem of inefficient parallel search in combinatorial optimization for researchers and practitioners in fields like molecular design, offering a novel method that is not incremental but first-of-its-kind for real-world non-game applications.
The authors tackled the challenge of scaling Monte-Carlo Tree Search (MCTS) for combinatorial optimization by proposing a massively parallel MP-MCTS algorithm that maintains solution quality at 1,000 workers, achieving candidate molecules with similar scores in 10 minutes on 256 cores compared to 42 hours for non-parallel MCTS.
It is common practice to use large computational resources to train neural networks, as is known from many examples, such as reinforcement learning applications. However, while massively parallel computing is often used for training models, it is rarely used for searching solutions for combinatorial optimization problems. In this paper, we propose a novel massively parallel Monte-Carlo Tree Search (MP-MCTS) algorithm that works efficiently for 1,000 worker scale, and apply it to molecular design. This is the first work that applies distributed MCTS to a real-world and non-game problem. Existing work on large-scale parallel MCTS show efficient scalability in terms of the number of rollouts up to 100 workers, but suffer from the degradation in the quality of the solutions. MP-MCTS maintains the search quality at larger scale, and by running MP-MCTS on 256 CPU cores for only 10 minutes, we obtained candidate molecules having similar score to non-parallel MCTS running for 42 hours. Moreover, our results based on parallel MCTS (combined with a simple RNN model) significantly outperforms existing state-of-the-art work. Our method is generic and is expected to speed up other applications of MCTS.