Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design
Authors: Xiufeng Yang
Tanuj Aasawat
Kazuki Yoshizoe
Venue: ICLR 2021 Poster (2021)
Keywords: parallel Monte Carlo Tree Search (MCTS)
Upper Confidence bound applied to Trees (UCT)
molecular design

Abstract: It is common practice to use large computational resources to train neural networks, known from many examples, such as reinforcement learning applications. However, while massively parallel computing is often used for training models, it is rarely used to search solutions for combinatorial optimization problems. This paper proposes a novel massively parallel Monte-Carlo Tree Search (MP-MCTS) algorithm that works efficiently for a 1,000 worker scale on a distributed memory environment using multiple compute nodes and applies it to molecular design. This paper is the first work that applies distributed MCTS to a real-world and non-game problem. Existing works on large-scale parallel MCTS show efficient scalability in terms of the number of rollouts up to 100 workers. Still, they suffer from the degradation in the quality of the solutions. MP-MCTS maintains the search quality at a larger scale. By running MP-MCTS on 256 CPU cores for only 10 minutes, we obtained candidate molecules with similar scores to non-parallel MCTS running for 42 hours. Moreover, our results based on parallel MCTS (combined with a simple RNN model) significantly outperform existing state-of-the-art work. Our method is generic and is expected to speed up other applications of MCTS.

Published as a conference paper at ICLR 2021
PRACTICAL MASSIVELY PARALLEL MONTE-CARLO TREE SEARCH APPLIED TO MOLECULAR DESIGN
Xiufeng Yang
Chugai Pharmaceutical Co., Ltd yangxiufenngs @@g i com
Tanuj Kr Aasawat
Parallel Computing Lab India, Intel Labs tanuj. wwwawatt@nnteee..............a.e com
Kazuki Yoshizoe*
RIKEN Center for Advanced Intelligence Project yoshizoe@acm. org
ABSTRACT
It is common practice to use large computational resources to train neural net- works, known from many cxamples, such as reinforcement learning applications. However, while massively parallel computing is often used for training models, it is rarely used to search solutions for combinatorial optimization problems. This paper proposes a novel massively parallel Monte-Carlo Tree Search (MP-MCTS) algorithm that works efficiently for 1,000 worker scale on distributed memory environment using multiple compute nodes and applies it to molecular design. This paper is the first work that applies distributed MCTS real-world and non-game problem. Existing works on large-scale parallel MCTS show efficient scalability terms of the number of rollouts up to 100 workers. Still, they suffer from the degradation in the quality of the solutions. MP-MCTS maintains the search quality at a larger scale. By running MP-MCTS on 256 CPU cores for only minutes, we obtained candidate molecules with similar scores to non-parallel MCTS running for 42 hours. Moreover, our results based on parallel MCTS (combined with a simple RNN model) significantly outperform existing state-of-the ffite-of-the---a the-art work. Our method generic and is expected to speed up other applications of MCTs[]
INTRODUCTION
survey paper MCTS, published in 2012, has cited 240 papers, including many game and non-game applications (Browne et al. 2012). Since the invention of Upper Confidence bound applied to Trees (UCT) (Kocsis & Szepesvári] 2006) (the most representative MCTS algorithm) in 2006, MCTS has shown remarkable performance various problems. Recently, the successful combination with Deep Neural Networks (DNN) in computer Go by AlphaGo (Silver al.) (016) has brought MCTS into the spotlight. Combining MCTS and DNN is becoming one of the standard tools for solving decision making combinatorial optimization problems. Therefore, there a significant demand for parallel MCTS. However, in contrast to the enormous computing resources invested in training DNN models in many recent studies, MCTS is rarely parallelized large scale.
Parallelizing MCTS/UCT is notoriously challenging. For example, in UCT, the algorithm follows Non-parallel vanilla UCT updates (back- propagates) the values in the tree nodes after each rollout. The behavior of the subsequent selection steps depends on the results of the previous rollouts- bacputtsbcckkooaaatiio... Therefore, there is no apparent parallelism in the algorithm.
four steps, selection-expee papaaniioonoolloutbaakaeee
"This work was done while all the authors were at RIKEN. Code available at attttps: : thub wwwp.hhw....chhhhhcctettc wttp://///.......oo//ee//eeeee

---

Published as a conference paper at ICLR 2021
Using virtual-loss technique (explained in section 2.3 MCTS has been efficiently parallelized on -eeoryy single machine environment, where the number of CPU cores are limited (Chaslot et al. 2008 Enzenberger & Müller 2010: Segal 2010). However, there is limited research on large-scale parallel MCTS using distributed memory environments. Only two approaches scale efficiently distributed memory environment, but these were only validated in terms of the number of rollouts and the actual improvement is not validated (Yoshizoe et al. 2011 Graf et al.) [011I).
Recently, the combination of (non-parallel) MCTS and DNN has been applied to molecular design problems, which aims to find new chemical compounds with desired properties (Yang et al. 2017 Sumita et al. 2018), utilizing the ability of MCTS solve single-agent problems. In general. designing novel molecules can be formulated as combinatorial optimization or planning problemppobmmmmmm to find the optimal solutions in vast chemical space (of 1023 to 10 PPllischuk et al. (2013)) and can be tackled with the combinations of deep generative models and search (Kusner et al. 2017 Gómez Bombarelli et al, 2018 Jin et al. 2018 [Popova al., 2018 2019 Yang et al. 2017). However, there no previous studies about massively parallel MCTS for molecular design.
In this paper, we propose a novel distributed parallel MCTS and apply to the molecule design problem. This is the first work explore viability of distributed parallel MCTS in molecular design. Our experimental results show that a simple RNN model combined with massively parallel MCTS outperforms existing work using more complex models combined with Bayesian Optimization or Reinforcement Learning (other than UCT).
2 BACKGROUND
2.1 (NON-PARALLEL) MCTS
In 2006, Kocsis and Szepesvári proposed UCT based on Multi-Armed Bandit algorithm UCB1 (Auer ett al. 2002). which is the first MCTS algorithm having a proof of convergence to the optimal solution. has shown good performance for many problems, including the game of Go (Gelly al. 2006).
One round of UCT consists of four steps, as shown in Fig. It repeats the rounds for given number of times or until specified time has elapsed.
Selection: The algorithm starts from the root node and selects the child with the highest UCBI value (Fig. left until it reaches a leaf node. For each child i, v; the number of visits, wi the cumulative reward, and V is the number of visits at the parent node. Exploration constant C' controls the behavior of UCT: the smaller, the more selective; the greater, the more explorative.
Expansion: If the number of visits exceeds given threshold, expand the leaf node (add the children of the leaf to the tree) and select one the new children for simulation. Do nothing otherwise. UCT then evaluates the node by simulation. This step is often called playout rollout. simple example of rollout is to go down the tree by selecting a random child at each node until reaches terminal node and returns the value at the terminal node as the reward (win loss for games). Replacing rollout with a DNN based evaluation is becoming more popular following the success of AlphaGo.
Simulation:
Repeat
Selection
Expunsion
Simulation
Bacigrropagation
A
Partial SMILES "O=C"
Score
RNN rollout
Complete SMILES
(reward)
Chemistry
simulator
Figure 1: Four steps of (non (non-parallel) MCTS, with simulation for molecular design.
2

---

Published as a conference paper at ICLR 2021
(a)
(b)
Green worker goes first, increments 4; on the path and reaches leaf.
Red goes second, inerements f, and avoids the leaf because of the penalty.
Blue further avoids the same path because of the greater penalty.
logV
log(V 7)
UCB1
C
UCRvl
12+0
v;
Figure 2: (a) parallel UCT using UCBI (failed) (b) parallel UCT with viriual loss, and the search paths of three parallel workers shown in solid circles, (green, red, and blue, from left to right).
Backpropagation: UCT finally traverses the path all the way back to the root, and updates the values of the nodes in the path (w; = wi r, Us = 1/S + 1).
2.2 SOLVING MOLECULAR DESIGN USING MCTS
The Simplified Molecular-Input Line-Entry System (SMILES) (Weininger 1988) is a standard notation in chemistry for describing molecules using ASCII strings, defined by grammar. SMILES uses ASCII symbols to denote atoms, bonds, or structural information such as rings. For example, SMILES for Carbon dioxide is "O=C=O" where "=" means double bond, and for Benzene, "CI=CC=CC=C1" or "cl " which forms a ring by connecting the two "C1"s. The search space for molecular design can be defined as a tree based on the SMILES, where the root node the starting symbol (denoted as "&", usually not shown) and each path from the root to depth d node represents a left-to-right enumeration of the first d symbols in the (partial) SMILES string (see Fig. I The subscripts shows the depth.).
Yang et al. (2017) were the first to apply non non-parallel MCTS to this problem using the AlphaGo- approach, which combines MCTS with DNN and computational chemistry simulator. They trained an RNN model with a chemical compound database, and the RNN predicts the next symbol of a partial SMILES string which is given the input. The model is used for expansion and rollout.
Expansion for Molecular Design: The node (=2) in Fig. [ denotes SMILES strings starting with "O=". The RNN receives "O=" input and outputs the probability of the next SMILES symbols. Instead of simply adding all symbols as child nodes, the low probability branches are pruned based on the output of the model.
Simulation for Molecular Design: Fig. Tillustrates the simulation step for molecular design. Node (Cz) denotes SMILES strings starting with "O=C". Firstly, a rollout generates a complete SMILES string, a new candidate molecule, by repeatedly sampling the next symbol using the model, until the model outputs the terminal symbol. Then, a computational chemistry simulator receives the SMILES string and caleulates the target chemical property for the molecule, to determine the reward.
2.3 PARALLEL MCTS
Non-parallel MCTS finds the most promising leaf one time in the selection step. In parallel MCTS, multiple workers must find the promising leaves (to launch simulations from) in parallel, hence, should find leaves speculatively without knowing the latest results.
Fig. 2 shows the example of a three workers case (a worker means a thread or process, which runs on either CPU GPU). If the workers (shown green, red, blue) follow the UCB1 formula, all end up at the same leaf node (Fig. (a)), and the parallelization fails.
The Virtual loss (Chaslot et al. 2008) let the workers find the promising but different leaves. The original UCB1 is modified to UCBul shown in Fig. (-(b), where i, is the number of workers currently searching in the subtree of the child node i, and is the sum of t, of the children. It is called virtual loss because it assumes that the current ongoing simulations will obtain 0 reward. With this modification, UCBul value is penalized based on the number of workers, which makes the subsequent workers avoid the subtrees already being explored (see Fig. (b)).
3

---

Published as a conference paper at ICLR 2021
0111101110100
Hash tables for workers
1101 100110101
0011011110111
1001010110110
Figure 3: Hash-driven parallel search distributes the nodes to workers based on hash function. The home worker of the nodes are defined by the trailing 2 bits.
Parallel UCT with virtual loss was proved to improve the strength of shared-memory (using up to 16 cores) Go programs (Chaslot al. 2008 Enzenberger & Müller 2010). Segal's is experiment on an emulated multithreaded machine that assumes no communication overhead shows speedup on up to 512 threads. However, his experiments on real distributed machines did not provide significant speedup beyond 32 cores (Segal 2010).
2.4 HASHIDRIVVN PARALLEL SEARCH AND UNIFORM LOAD BALANCING
When many workers perform search in parallel, it is essential to distribute the search space as evenly as possible. If there is an imbalance in the workload, overall performance will be less efficient because only some workers will continue the computation while the rest remain idle. If all the search space is explicitly given in advance, this is a trivial matter. However, in case of problems such games and combinatorial optimization, where the search space is generated while the search is performed, is difficult to distribute the search space evenly.
Hash-driven (HD) parallel search is of the methods for resolving this difficulty; Evett al. (1995) (PRA*) and Romein et al. (1999) (TDS: Transposition-table Driven Scheduling) developed this method independently and applied parallel Iterative Deepening A search. Kishimoto al. (2013) later applied it to parallel A search. HD parallel search requires a hash function that defines the hash key of each node. Each time the algorithm creates a node during the search, assigns the node to a specific worker, the home worker (or the home processor), based on the hash function, and achieves near-equal load balancing if the hash function sufficiently random (such as Zobrist. Hashing (Zobrist 1970p).
Figure illustrates this method. The hash function randomly divides the tree into four partitions (shown in four colors), and each worker holds the nodes in the assigned partition in its hash table. A distinct drawback of this method is that requires communication between workers almost every time the algorithm traverses branch (unless the two nodes on the same worker). The key to efficient parallel speedup is the trade-off between uniform load balancing and frequent communication. The experimental results for IDA* and A (Evett al. 1995 Romein et al. 1999) Kishimoto al. 2013) prove its efficiency for these search algorithms. However, a straightforward application of HD parallel search UCT is not efficient enough as described below.
DISTRIBUTED PARALLEL MCTS AND MOLECULAR DESIGN
3.1 TDS-UCT: TASH-DRIVEN PARALLEL MCTS
Here we describe the application of Hash-da driven parallel search to UCT, TDS-UCT. Figure 4 illustrates the behavior of the four steps in TDS-UCT.
Selection: The worker which holds the root node selects the best child (O2 in Fig. based on UCBvl formula (Fig. (b)). It then sends selection message, which holds information of O₁. to the home worker O (the green worker in Fig 4 a worker receives a selection message, selects the best child of the node and pass the message to another worker until the message reaches leaf node. The worker-count f; of each node is incremented during the step.
Expansion: If a worker receives a selection message and the node is leaf, the expansion step is done in the same way as in non non-parallel MCTS.
Simulation:
Simulation is done by the home worker of the leaf (the green worker in Fig. in the
4

---

Published as a conference paper at ICLR 2021
same way in non-parallel MCTS.
Backpropagation: After a simulation (at Cs), a backpropagation message, which holds the reward r, is sent to the parent (=2). The workers pass the backpropagation message to the parent until it reaches the root node. At each node, the values are updated by the corresponding worker (w; = Wi + r.
0 14 + 1, 14
To reduce the the number of idle workers, the sum of the number of selection messages, backprop- agation messages and ongoing simulations must be more than the number of workers. Yoshizoe et al. (2011) and Graf et al. (201T) independently proposed to control the number to N x #workers where N the overload factor.. We used N following the experimental results in the two papers.
3.2 TDS-DF-UCT. DEPTH-FIRST REFORMULATION OF TDS-UCT
Scalability of TDS-UCT is limited because of the communication contention around the root node. In TDS-UCT, all backpropagation messages are sent up until to the root node. As the number of messages increase, the workers that hold shallow nodes (especially the root node) spend more time for communication. Because of this problem, the scalability of TDS-UCT quickly diminishes beyond 100 workers (Yoshizoe et al. 2011).
For solving the communication contention, TDS-df-UCT was proposed based on the observation that the promising part of the tree does not change often after each simulation (Yoshizoe et al. 2011)) The next selection step will likely reach a node that is close to the previously selected lcaf node, as shown in Fig. (a). The leaf is C3 for the 1st selection step and N₂ for the 2nd selection step. Each job message in IDS-df-UCT carries a history table which contains the history of the siblings of the nodes in the current path. After each simulation, TDS-df-UCT updates the values in the node and the history table, and re-calculate the UCBvl of the siblings. Unlike TDS-UCT, TDS-df-UCT will backpropagate only if the UCBv/ value of the nodes in the current path is exceeded by one of the other siblings in the history table.
Fig. (b) shows a trajectory of a message in TDS-dF-UCT. After the first selection-expansion simulation, it does not send the backpropagation message to the parent of =2. Instead, it directly sends a selection message to N3, as =2 is still the most promising node. This technique dramatically reduces the number of messages sent to the root node by staying at the more promising part, thus solving the communication contention problem.
3.3 MP-MCTS: ADDRESSING SHORTCOMINGS OF TDS-DF-UCT
TDS-df-UCT carries the history only in the messages, hence, requires more time to propagate new results to other jobs. As a result, TDS-df-UCT skips backpropagations too often because overlooks that other workers may have found more promising part of the tree, therefore making the tree wider and shallower. our MP-MCTS, along with its own statistical information (w, v, t), cach node maintains the history table shown in Fig, (c). It accelerates the propagation of the latest information at the cost of extra (minor) memory usage (see Appendix [A.2 for the memory usage analysis). This modification TDS-df-UCT crucial for improving the behavior of the parallel MCTS to generate a deeper tree. We illustrate in the experimental results that the quality of the
(b) TDS-AFUCT
&
Selectio
Rockpropagation 2r Selection
(Ng
(c) MP-MCTS
N
rollout (simulation)
rollout (simulation)
(N
TDS-UCT
Figure 4: The trajectory of a message in (a) TDS-UCT (b) TDS-df-UCT and (c) MP-MCTS. TDS-df- UCT has the history table only in the messages and MP-MCTS stores it in the nodes also
5

---

Published as a conference paper at ICLR 2021
solution and the average depth of the tree generated by N-parallel MP-MCTS are both similar to the ideal case obtained by running the non-parallel MCTS for N W-times more wall-clock time.
4 EXPERIMENT METHODOLOGY
To evaluate the quality of the solutions and to compare against state-of-the-art methods, we use the octanol-water partition coefficient (logP) penalized by the synthetic accessibility (SA) and large Ring Penalty score, popular benchmarking physicochemical property (Kusner et al. 2017] Jin et al. 2018
You et al. 20118 Sa Popova et al.) 2019; Maziarka et al., 2020) used in molecular design.
Model and Dataset: We the GRU-based model and pre- pre-trained weights publicly available on the repository of ChemTS YYnng et al. 2017), which mainly consists of two stacked GRU units. Input data represents SMILES symbols using 64-dim one-hot vectors. The first GRU layer has 64-dim input/256-dim output. The second GRU layer has 256-dim input/256-dim output, connected to the last dense layer, which outputs 64 values with softmax. The model was pre-trained using a molecule dataset that contains 250K drug molecules extracted from the ZINC database, following (Kusner
al. 2017
Yang et al. 2017 Jin al. 2018).
MCTS implementation: The GRU model explained above takes partial SMILES string as the input and outputs the probability of the next symbol. We use this model for both Expansion and Simulation. In the expansion step, we add branches (e.g., SMILES symbols) with high probability until the cumulative probability reaches 0.95. For a rollout in the simulation step, we repeatedly sample over the model to generate complete SMILES string. Then the string is passed to a computational chemistry tool, RDKit (Landrum et al.] 2006) for calculating the penalized logP score, which is commonly used in existing work. We use the reward definition described in Yang et al. (Yang et al. 2017) which is normalized to [-1, 1] and consider the same value for exploration constant, C = I.
Other experimental settings: Algorithms are implemented using Keras with TensorFlow and MPI library for Python (mpi4py). ). All experiments, unless otherwise specified, were run for 10 minutes on up to 1024 cores of CPU cluster (each node equipped with two Intel Xeon Gold 6148 CPU (2.4GHz, 20 cores) and 384GB of memory), and one MPI process (called worker in this paper) is assigned one core.
5 EXPERIMENT RESULTS
To evaluate the distributed MCTS approaches, we study the quality of the solutions obtained, analyze the performance of different parallel MCTS algorithms, and compare the performance of MP-MCTS with state-of-the-ar work in molecular design.
Maximizing penalized logP score. Table presents the penalized logP score of distributed MCTS approaches for varying number of CPU cores. With increasing number of cores available, more number of simulations can be performed in parallel, which improves the quality of the score. We performed 10 runs for each settings, and show the average and standard deviation of the best scores. TDS-UCT suffers from communication contention, with increasing number of cores the load imbalance becomes more significant, hence yields lower score. TDS-df-UCT achieves more uniform load balancing but only slightly improves the score (discussed later in this section). Our MP-MCTS, which mitigates the issues of other approaches, shows strict improvement in score with increase in number of cores leveraged.
Quality of parallel solution over non-parallel solution. As mentioned earlier, any parallel MCTS must speculatively start to search before knowing the latest search results, and it may return different outcomes from those of the non-parallel version. In addition, the exploration and exploitation trade-off of distributed MCTS is controlled via the virtual-loss based UCBv/ instead of theoretically guaranteed UCB1 1 (rrwnn et al. 2012). Hence, it is significant to compare the quality of distributed MCTS solution with non-paralle lel MCTS (cf. strength speedup (Appendix I...).
The bottom of Table D presentss the penalized logP score for non non-parallel MCTS. Note that nan-parallel MCTS was run for equivalent core-hours (for example, 256 cores for non non- -orralllll MCTS indicates it run for 256 10 minutes single core; while distributed MCTS is on 256 cores

---

Published as a conference paper at ICLR 2021
Table 1: Penalized logP score (higher the better) of TDS-UCT, TDS-dI-UCT and MP-MCTS, with 10 minutes time limit, averaged over 10 runs.
* 4, 16, 64 and 256 cores for non-pan parallel-MCTI indicates the algorithm was performed for (4x 10), 160 (16x 10), 640 x64x 10), and 2560 (256x 10) minutes. For x024x 10 minutes, non-parallel-MCTS was not performed due to the huge execution time (~170 hours).
cores
4
16
64
256
1024
Methods
TDS-UCT
5.8310.31
6.24
7.47=00722
7.39:10.92
6.22:10.27
TDS-df-UCT
7.26:t0.49
8. 0.34
8.59:10.49
8.22++0.41
8.34:10.6
MP-MCTS
6.82+t0.76
8.01+00.1
9.03++0.85
11.46=1..22
11.94-22.03
-non-parallel-MCTS
6.97 + 0.49
8.54 + 0.34
9.23 + 0.53
11.17 0.88
(licores x 10 minutes)
Depth of the nodes in the tree
x16+
#BP messages per worker
Received #BP messages
1.2
TDS-UCT
TDS-dF-UCT
70
1.0
60
Depth
50
40
0.4
0.2
50
100
150
200
250
TDS-UCT TDS-dFUCT MP-MCTS
2660 min. 10 min.
Worker ID
ParallelMCTS using 256 workers for 10min.
Non-parallei MCTS
Figure 5: (a) Number of back- tokk-ropagation (BP) messages received by each of 256 workers. (b)
Box-whisker plot showing the depth of the search tree for different parallel MCTS variants.
for 10 minutes). While taking much less time, the distributed-MCTS on-par and yields higher score than non-parallel when large computing resources (i.e. with 256 and 1024 cores) are leveraged.
Message traffic reduction at root. Fig. (a) presents back back-propagation messages received by each worker. MP-MCTS and TDS-df-UP TDS-UCT, root's and few other hot nodes' home worker get overwhelmed by the messages, and suffers from extremely high load-imbalance. Note that TDS-df-UCT generates shallower tree, resulting in fewer BP messages,
lead better load balance across all workers, while for
Depth of the search tree. Fig. 5 (b) compares the depth of the nodes the search tree generated by parallel and non-parallel MCTS. TDS-UCT creates shallower tree than the others because of the load imbalance. TDS-df-UCT generates deeper tree than TDS-UCT but still much shallower than ideal case. It is presumed that TDS-df-UB does too few backpropagations (see 3.2). MP-MCTS generates significantly deeper tree by using 256 cores for 10 minutes, which is close to the ideal case of non-parallel MCTS using 2,560 minutes (approx. 42h).
Comparison against related work in molecular design. Table presents the top penalized logP scores obtained by the existing state-of-the-an work (description in section 6). The scores of MP-MCTS are the best among 10 runs (10 minutes each), which outperforms the existing work significantly in maximizing the penalized logP score. It is also notable that MP-MCTS significantly improved the score of the GRU-based model Yangg et al. 2017). The bottom two lines compare the results obtained from 10 minutes random sampling from the GRU-based model with score obtained by MP-MCTS which uses the same model (as mentioned in Section 4). This result suggests the possibility of improving existing work by combining their models with parallel MCTS.
7

---

Published as a conference paper at ICLR 2021
Table 2: Comparison of the best three penalized logP scores
Methods
1st
2rd
3rd
JT-VAE (Jin et al.
2018
5.30
4.93
4.49
reported results
GCPN You et al.
2018a)
7.98
7.85
7.80
reported results
MolecularRNN Popoya et al. 2019
10.34
10.19
10.14
reported results
MolDQN (Zhou et al.
2019)
9.01
9.01
8.99
reported results
Mol-CycleGAN (Maziarka et al.
2020
9.76
7.29
7.27
reported results
GRU-based Yang et al. 2017)
6.47
5.65
5.01
hours x 10 runs
MP-MCTS using GRU
15.13
14.77
14.48
10 min. x 10 runs
"These scores are hased on the updated values in authors' correction of the paper.
RELATED WORK
6.1 MOLECULAR DESIGN
In molecular design, it is a common approach use deep generative models (to generate candidate molecules), followed by optimization algorithms to focus on the promising candidates having desired molecular property (mainly Bayesian Optimization (BO) or Reinforcement learning (RL)). Gomez- Bombarelli et al. (Gómez-Bombarelli et al. 2018) were the first to employ variational autoencoders (VAE). Kusner et al. (Kusner et al. 2017) enhanced it grammar variational autoencoder (GVAB) by combining context free grammars. Both of the above used BO for optimization. Segler et al. Segllr 1997).
al. 2018a) focused on generating molecules using LSTM (Hochreiter & Schmidhuber Olivecrona et al. (Olivecrona et al. 2017) used simple RNN and Popova et al. (Popova et al. 2018
used GRU for generation, both combined with RI.. These work use SMILES representations. Graph- based molecule generation, such as JT-VAE (Jin et al.] (2018) and GCPN (You et al.) 200 generate molecules by directly operating on molecular graphs, optimized with BO and RL respectively, Popova et al. (Popova et al., 2019) proposed MolecularRNN, an improved RNN model by extending the GraphRNN You et al. 2018b) with RL. MolDQN (Zhou et al.) 2019) is based on DQN with three types of actions, Atom addition, Bond addition, and Bond removal.
The above mentioned work do not use MCTS. Jin et al. (2020) applied MCTS for molecule design with multi-objective constraints, where MCTS is first used for extracting important substructures, then a graph-based molecule generation is trained on a data set having these substructures, and outperforms RL based methods. Yang al. (017) combined non-parallel MCTS with simple GRU and outperformed BO based methods in penalized logP. Sumiia et al. (2018) later applied the same approach a wavelength problem using a quantum mechanical simulation method (DFT).
6.2 PARALLEL MCTS
Among the work combining DNN and MCTS beyond single-machine Distributed AlphaGo (using 1202 GPUs) the only massively parallel work (applied to Go program). However, it has limited scalability because only one machine holds the search tree, and the GPUs in other machines are used only for neural network computation.
Hash driven parallel search was first applied to distributed MCTS by IDS-df-UCT (Yoshizoe et al. 201T) (for an artificial game) and UCT-tree-split (Graf et al. 2011) (for the game of Go) independently. and solves communication contention problem. UCT-tree-split preserves replicated subtree for each worker which contains the nodes with large number of visits. periodically synchronizes the subtrees, hence, suffers from higher communication overhead than TDS-df-UCT.
Other distributed parallel MCTS techniques include Root parallelization and Leaf parallelization Root parallelization performs multiple runs of MCTS with different random seeds (Chaslot et al.) 2008) and synchronizes the shallow part of the tree. The strength improvement is limited because the size of the tree remains similar to that of non poralaallll MCTS (Soejima al.) 2010). Another known parallel method is Leaf parallelization (Cazenave & Jouandeau (007), ) but its performance was lower than that of root parallelization.
8

---

Published as a conference paper at ICLR 2021
Among shared-memory environment (having only few tens of workers), the first reported parallel UCT (Gelly et al.] 2006), did not rely on virtual loss and it was less efficient. Many other work on shared memory environment
virtual loss (Chaslot et al. 2008 Enzenberger & Müller 2010 Segal 2010: Liu et al. 2020). However, they are limited to a maximum of 32 workers.
7 CONCLUSION
Applying MCTS molecular design relatively less explored. Ours the first work explore distributed parallel MCTS for molecular design. The extensive experiments have shown that an efficient distributed MCTS significantly outperforms other approaches that use more complex DNN models combined with optimizations such as Bayesian Optimization or Reinforcement Learning (other than UCT). Further, it does not trade off search ability (w.r.t non-parallel MCTS) for a real world problem.
would be an interesting future work further enhance the performance of molecular design by using more complex and improved models with parallel MCTS. Also, MP-MCTS could be applied to other MCTS applications, including retrosynthetic analysis to which an AlphaGo-like approach applied (Segler et al. 2018b). Furthermore, although we analyzed the performance for molecular design, the parallelization technique is independent the chemistry specific components and could be applied to other game and non-game applications. Our experiments strongly suggest that MCTS can be a better alternative for real-world optimization problems.
ACKNOWLEDGMENTS
This work is partially supported by JSPS Kakenhi (20H04251). Experiments were conducted on the RAIDEN computer system at RIKEN AIP.
REFERENCES
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multi-armed bandit problem. Machine Learning, 47:235-256, 2002.
N. Brown, M. Fiscato, M.H.S. Segler, and A. Vaucher. GuacaMol: Benchmarking Models for de Novo Molecular Design. Journal of Chemical Information and Modeling, 59(3):099-1108, 2019.
C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1): 2012.
T. Cazenave and N. Jouandeau. On the parallelization of UCT. In Proceedings of the Computer Games Workshop 2007, pp. 93-101. 2007.
G. M. J-B. Chaslot, M. H. M. Winands, and H. J. van den Herik. Parallel Monte-Carle tree search. In Proceedings of the 6th International Conference on Computers and Games (CG), volume 5131 of Lecture Notes in Computer Science, pp. 60-71. 2008
R. Coulom. Efficient selectivity and backup operators in Monte-Carlo tree search. In Proceedings of the 5th International Conference on Computers and Games (CG), pp. 72-83. 2006.
M. Enzenberger and M. Müller. A lock-free multithreaded Monte-Carlo tree search algorithm. In Proceedings of the 12th Advances in Computer Games (ACG), volume 6048 of Lecture Notes in Computer Science, pp. 14-20. 2010.
M. Enzenberger, M. Müller, B. Areson, and R. Segal. FUEGO an open-source framework for board games and Go engine based on Monte-Cath Carlo tree search. IEEE Transaction on Computational Intelligence and Al in Games, 2(4):259-22) 270, 2010.
M. Evett, J. Hendler, A. Mahanti, and D. Nau. PRA*: Massively Parallel Heuristic Search. Journal of Parallel and Distributed Computing, 133-)3333-144, March 1995.

---

Published as a conference paper at ICLR 2021
M. Frisch, G. W. Trucks, H. B. Schlegel, G. E. Scuseria, M. A. Robb, J. Cheeseman, G. Scalmani,
V. Barone, G. A. Petersson, H. Nakatsuji, X. Li, M. Caricato, A. Marenich, J. Bloino, B. G. Janesko, R. Gomperts, B. Mennucci, H. P. Hratchian, J. V. Ortiz, A. F. Izmaylov, J. L. Sonnenberg, Ding, F. Lipparini, F. Egidi, J. Goings, B. Peng, A. Petrone, '. Henderson, D. Ranasinghe, V. G. Zakrzewski, J. Gao, N. Rega, G. Zheng, W. Liang, M. Hada, M. Ehara, K. Toyota, R. Fukuda, J. Hasegawa, M. Ishida, T. Nakajima, Y. Honda, O. Kitao, H. Nakai, T. Vreven, K. Throssell, J. A. Montgomery, Jr., J. E. Peralta, Ogliaro, M. Bearpark, J. Heyd, E. N. Brothers, K. N. Kudin, V. N. Staroverov, T. A. Keith, R. Kobayashi, J. Normand, K. Raghavachari, A. Rendell, C. Burant, S. S. Iyengar, Tomasi, M. Cossi. M. Millam, M. Klene, C. Adamo, R. Cammi, J. W. Ochterski, R. L. Martin, K. Morokuma, O. Farkas, J. B. Foresman, and D. J. Fox. Gaussian-16 Revision C.01, 2016. Gaussian Inc. Wallingford CT.
D. Williams- Yoriaas--Young,.
Gelly, Y. Wang, R. Munos, and O. Teytaud. Modification of UCT with patterns in Monte-Carlo Go. Technical Report 6062, INRIA, 2006.
R.
J. N. Wei, D. Duvenaud, J. M. Hemnández-Lbbtto B. Sánchez-Lengeling Aguilera-parraguurre
D. Sheberla, J. Aguilera- Iparraguirre, T. D. Hirzel, R. Adams, and A. Aspuru-Guzin Automatic chemical design using data-driven continuous representation of molecules. ACS central science, 4(2):268-22 276, 2018.
T. Graf, U. Lorenz, M. Platzner, and I.. Schaefers. Parallel monte-carlo tree search for hpe systems. In European Conference on Parallel Processing, pp. 365-376. Springer, 2011.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 933: 1997.
W. Jin, R. Barzilay, and T. Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pp. 1323-2332, 2018.
W. Jin, R. Barzilay, and T. Jaakkola. Composing molecules with multiple property constraints. arXiv preprint arXiv:2002.032-4, 2020.
A. Kishimoto, A.Fukuna,a and A. Botea. Evaluation simple, scalable, parallel best-first search strategy. Artificial Intelligence,, 195:222-248, 2013.
L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In Proceedings the 17th European Conference on Machine Learning (ECML), pp. 282-293. Springer, 2006.
M. J. Kusner, B. Paige, and J. M. Hernández-Lobato Grammar variational autoencoder. In Pro- ceedings of the 34th International Conference Machine Learning (ICML), pp. 1954. 2017.
G. Landrum et al. RDKit: Open-source cheminformatics. 2006.
A. Liu, J. Chen, M. Yu, Y. Zhai, X. Zhou, and Liu. Watch the unobserved: A simple approach to parallelizing monte carlo tree search. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
L. Maziarka, A. Pocha, J. Kaczmarczyk, K. Rataj. T. Danel, and M. Warchol. Mol-cyclegan: generative model for molecular optimization. Journal of Cheminformatics, 2020.
M. Nakata and T. Shimazaki. Pubchemqe project: a large-scale frst-prrnciples electronic structure database for data-driven chemistry. Journal of chemical information and modeling, 57(6):1300 1308, 2017.
M. Olivecrona, Blaschke, O. Engkvist, and H. Chen. Molecular de-novo design through deep reinforcement learning. Journal of cheminformatics, 9(1):48, 2017.
P. Polishchuk, T. Madzhidov, and A. Varnck. Estimation of the size of drug-like chemical space based on gdb-17 17 data. Journal of computer-aided molecular design, 27, 2013.
M. Popova, O. Isayev, and A. Tropsha. Deep reinforcement learning for de novo drug design. Science advances, 4(7)eaap7885, 2018.
10

---

Published as a conference paper at ICLR 2021
M. Popova, M. Shvets, J. Oliva, and O. Isayev. Molecularmn: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:1905.13372. 2019.
J. W. Romein, A. Plaat, H. E. Bal, and J. Schaeffer. Transposition table driven work scheduling in distributed search. In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI), pp. 725-731. 1999.
C. D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61:203-230, 2010.
R. Segal. On the scalability of parallel UCT. In Proceedings of the 7th International Conference on Computers and Games (CG). 2010.
M. H. S. Segler, T. Kogej, C. Tyrchan, and M. P Waller. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS central science, 4(1):120-131, 201 1a.
M. H. S. Segler, M. Preuss, and M. Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7699))004-610, 2018b.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanetot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587)4484 489, 2016.
Y. Soejima, A. Kishimoto, and O. Watanabe. Evaluating root parallelization in Go. IEEE Transactions on Computational Intelligence and Al in Games, 2(4):278-287, 2010.
M. Sumita, X. Yang. S. Ishihara, R. Tamura, and K. Tsuda. Hunting for organic molecules with artificial intelligence: molecules optimized for desired excitation energies. ACS central science, (9):1126-1133 2018.
Y. Tian, J. Ma, Q. Gong, S. Sengupta, Z. Chen, J. Pinkerton, and L.. Zitnick. ELF OpenGo: an analysis and open reimplementation AlphaZero. Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pp. 2244-6253 2019.
D. Weininger. Smiles, chemical language and information system. 1. introduction methodology and encoding rules. Journal of chemical information and computer sciences, 28(1):31 1988.
X. Yang. J. Zhang, K. Yoshizoe, K. Terayama, and K. Tsuda. Chemts: an efficient python library for de novo molecular generation. Science and technology of advanced materials, 18(1)9972-976 2017.
K. Yoshizoe, A. Kishimoto, T. Kaneko, H. Yoshimoto, and Y. Ishikawa. Scalable distributed monte- carlo tree search. In Proceedings of the Fourth Annual Symposium on Combinatorial Search, 2011.
You, B. Liu, Z. Ying, V. Pande, and Leskovec. Graph convolutional policy network for goal- directed molecular graph generation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), pp. 6412-6422, 2018 8a.
You, R. Ying. X. Ren, W. L. Hamilton, and J. Leskovec, Graphrnn: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80, pp. 57.55708-77 5717, 2018b.
Z. Zhou, S. Kearnes, L. Li, R. N. Zare, and P. Riley. Optimization of Molecules via Deep Reinforce- ment Learning. Scientific Reports, 9():1210-1239, 2019.
A. L. Zobrist. A new hashing method with applications for game playing. Technical report, Department of Computer Science, University of Wisconsin, 1970.
11

---

Published as a conference paper at ICLR 2021
A OTHER DETAILS OF PARALLEL MCTS
A. STRENGTHI SPEEDUP
is quite misleading to compare only the number of rollout for evaluating the parallel MCTS algorithms. For example, it easy achieve a linear speedup in terms of the number of rollouts using the simplistic root parallel MCTS, However, it is not meaningful because it does not contribute to the actual strength.
For example, the only massively parallel Go program based on DNN and MCTS, distributed AlphaGo, wins 77% of the games against single- machine AlphaGo using approximately 150-fold more resources (1202 GPUs vs. 8 GPUs) (Silver et al.] 2016). Distributed AlphaGoo is presumed to have limited scalability because only one machine holds the search tree, and the GPUs in other machines are used only for neural network computation. But how efficient is this in reality? How should we estimate the effective speedup of the distributed version?
In the game-Al domain, strength speedup is used to evaluate the scalability. First, measure the strength improvement the non-parallel program, by using N-times more thinking time than the default settings. Then, if the parallel version reaches the same strength within the same default thinking time, using N-times more computing resources, the speedup is ideal.
Strength speedup never measured for distributed AlphaGo, but of other similarly strong Go programs. Based on the self-play experiments of ELF OpenGo (Fig. 7. Tian et al. (2019), it is enough to use four times more thinking time achieve 77% win rate against itself. Therefore, at least for ELF OpenGo, 77% win rate means less than or equals to 4-fold strength speedup. Based on this estimation,
guess from the results
presume that distributed AlphaGo also guessed that distributed A AlphaGo was designed to be robust against hardware failures and the scalability was not the first priority.)
efficient. (It
It is difficult to directly compare Go and molecular design, but our "strength speedup" shows almost ideal speedup, obtaining better results (within error range) than non-parallel MCTS (using 256x more time) by using 256 cores in parallel.
A.2 EXTRA MEMORY USAGE OF MP-MCTS
In MP-MCTS, the additional memory consumption per worker of storing w, v, of siblings at depth d is: C' x d x 6 x n x t, where C = 24 is a constant representing the memory usage of storing w, u, & (each costs 8 bytes) in a node, is the depth of the tree, is the average branching factor, the number of stored nodes per worker per second, and f is the execution time(s). In our molecular design case, 2.7, n Rs 1.8 (one evaluation on a node costs 0.5s, on average). Assuming d 20, the additional memory usage is 2.3KB per worker per second. For other problems (e.g., AlphaGO), presuming R
20, and n Rv 200 (approximated by one evaluation 5ms), then the additional memory usage is 843KB per worker per second, which is acceptable for recent servers having 10+GB memory per core (or worker) (allows more than 10,000 seconds of thinking time). In case the memory usage increases because of the larger b, save memory by recording only the top-K K branches and ignore less promising branches.
node using DNN costs
B VIRTUAL LOss DETAILS
B. THE ORIGIN OF VIRTUAL LOss
One of the first detailed paper about parallel MCTS (Chaslot et al. 2008 (Chaslot et al. 2008 already describes the use of virtual loss (page 5, section 3.3 bottom paragraph titled "Virtual loss"). The explained behavior about avoiding multiple threads visiting the same leaf is the same described in Section 2.3 of the main text. Yoshizoe et al. 2011 (Yoshizoe et al. (01T)) explains virtual loss in more detail.
12

---

Published as a conference paper at ICLR 2021
Chaslot et al. mentions that Coulom suggested, in personal communication, to assign one virtual loss per one thread during phase (c.g. the selection step). However, when we personally contacted Coulom to confirm the inventor of virtual loss, it turned out that Coulom was not the inventor. We could not track further and the original inventor of virtual loss is still unknown.
Recently, in early 2020, Liu et al. proposed method very similar the vanilla virtual loss (eq. D named Watched the Unobserved in UCT (WU-UCT) (Liu et al. 2020). (eq. 2 We presume Liu et al. misunderstood or overlooked the explanation of virtual loss formula in existing work for some reasons (although they refer to Chaslot et al. (Chaslot et al. 2008). mentioned above). The explanation about virtual loss in the related work section in (Liu et al. (Liu al. OpenReview website are wrong. In Response to reviewer #4 (part of 2) they say,
2020) and also their comment the
"To our best knowledge, NONE of the existing TreeP algorithmss (or any existing parallel MCTS algorithm) updates the visit counts BEFORE the simulation step finishes. TreeP only updates the values ahead of time using virtual loss. This is also the case for the work [1] and [2]."
However, this is not true. To our best knowledge, most of the existing work on multithreaded parallel MCTS published after 2008 updates the values BEFORE the simulation step completes. (Actually, we can not find the benefit of adding virtual loss AFTER the simulation step.)
Liu et al. say AlphaGoo (referred as [1] and [2] in their comment) do not update virtual loss BEFORE the simulation step completes. However this is presumed to a misunderstanding caused by the explanation in the first AlphaGo paper (Silver al.) 2016). The paper explains that virtual loss value is added during the Backup phase, so it sounds like the value is added after the simulation (explained in Methods, Search Algorithms Section, in the paper (Silver et al. 2016)). However, if you read carefully, the paper says that the virtual loss is added before the end of the simulation, and removed (subtracted) after the end of the simulation. Therefore, AlphaGo does update the visit count before the simulation step finishes. The main difference between WU-UCT and existing Virtual-loss-base parallel MCTS is the difference of the formulas (eq. and 2
We +0 UCB
log( V + T)
+ CV
(1)
U/ + 44
0 + li
Wi UCBwa + C
log(V + T) 02 + li
(2)
Ui
UCBel
Wi + LCB
C
log(V +T) Ui + 4
LCB min 0, 0,4
w;
log(V V + +T) W/ + li
U; + 4i
0i
B.2 COMPARISON OF VIRTUAL LOSS FORMULAS
We compared the results of our MP-MCTS using three different virtual loss formulas, the vanilla virtual loss, WU (Liu et al., 2020), and a new formula shown in eq. UCBelzcs (LCB stands for Lower Confidence Bound). Vanilla virtual loss assumes zero reward from the ongoing simulations and WU assumes the reward remains unchanged. UCBulLCB assumes something between these two, assumes a decreased reward estimated by Lower Confidence Bound.
Table 3 shows the logP score results of our MP-MCTS using three virtual loss formulas, averaged for 10 runs. The results suggests that, for molecular design, WU and UCBel do not improve the results over vanilla virtual loss.
Remi Coulom, invented the first MCTS algorithm (Coulom 2006) and applicd to his Go program CrazyStone (before UCT).
https:://ppenrerieew.n
d- H 10t.SKKDH
13

---

Published as a conference paper at ICLR 2021
Table Penalized logP score obtained by MP-MCTS using different virtual loss formulas for 256 and 1024 workers.
Methods
256
1024
UCBur (Liu et al. 2020)
10.19 0.82
10.37 = 1.01
UCBulI.R
10.75 + 1.32
10.78 0.27 11.94 + 2.03
UCBvl (vanilla)
11.46
1.52
B.3 EXAMPLES OF VIRTUAL LOSS IN CODES
It is common to use virtual loss for parallel game programs. We show real examples of virtual loss implementations in existing open source Go other game programs, both before and after AlphaGo. We can see the examples of the usage of virtual loss, and in all of these, the values are updated BEFORE the simulation step completes. is also interesting to note that the majority these work modify virtual loss equation for their implementations because they rely different variations of UCT, such as P-UCT (Rosin 2010).
Fuego (Enzenberger et al., 2010), one of the best open source Go programs until 2015, is generic game library. It started to use virtual loss in 2008 (from r677, committed on Nov. 27, 2008). In the P Play PlayGame function starting from line 673 (in the following URL), it calls AddVirtue urrtualLoss Loss at line 685, clearly before the playout (simulation), playouts start right below at line 693 after StartPlayouts.
Fuego:
3/
smarttganee/Sgpuctt.eaaaa cpp
ELF OpenGo: is a Go program and generic game library developed by FaceBook researchers Tian al. 2019). Source code of the search part in the following URL. In the single_ra sallerrollou
function starting from line 258, it calls addVirtualosss at line 282. (Please note that here "rollout" means the one whole cycle of the UCT, start selection from the root, reach a leaf, do (random) rollout, and backpropagate.)
https://githuf: wtw.uu.bcccc..a http:///w......aaaaaaaaaaaaaaaaa Src_cpp /ttp:////////////teeeeeaaaaaa///
www.seeeaereeeeeeeeeeeeeeeeeeeee search.h
LeelaZero: An open source Go program. In pllayssmulation: function starting from line 59, pirtual_loss updates the values Please note that this is part of the selection step.
play_simulatti_ is recursively called at line 88 or 94.
http://tttti..o......e..e....art Stc/DCTSearch.cop
AQ: An open source Go program. Virtual loss is added before simulations at line 142, and subtracted line 199 or around line 247 after simulations. Also is interesting to note that AQ uses virtual loss in two different ways, one for random rollouts and one for Neural Network based evaluation.
htt.:ggttuu...ooggggggggoooommoe Src bra/search.co
https://githut
C TOP MOLECULES
C.I LOGP OPTIMIZATION
Figure (a) shows the top 3 molecules by MP-MCTS for penalized logP optimization. MP-MCTS can design molecules with extremely high penalized logP scores, which demonstrates that our MP-MCTS algorithm has the ability identifying the promising branches. However, these molecules are not desirable because they are likely have inaccurate predicted properties, which shows limitation of maximizing penalized logP using an empirical tool (e.g. RDKit).
Therefore it would be interesting to apply MCTS based approach for different optimization problem with more accurate simulations. Figure (b) shows the best three molecules designed by MP-MCTS for another problem, wavelength property optimization (explained below).
14

---

Published as a conference paper at ICLR 2021
Table Wavelength (nm) score (higher the better) with hours time limit, averaged over 3 runs. indicates that experiments under the settings were not performed.
and 16 cores for non-parne pat---aaaaaaCCCI indicates the algorithm was performed for 4 6 and 16x6 hours. For 64 x6, 256x6 and 1024 x 10 hours, non-parallel-MCTS was not performed due to the huge execution time.
Methods MP-MCTS
cores
64
256
1024
1038.71: 1213.5 169.4 1850.1 + 281.9
1896.91: 275.8
1960.9:132.7
2308.5
104.4
2412.9 31.6
=non-paralle-MMCS
Table Zaleplon MPO score (higher the better) with minutes time limit, averaged over runs.
cores
16
64
256
1024
Method MP-MCTS
0.43 +0.03
0.46:10.02
0.47 0.01
0.51=0.07
0.47#0.01
C.2 WAVELENGTH OPTIMIZATION
It is possible to predict the wavelength of a given molecule using quantum mechanical simulation methods based on Density-Functional Theory (DFT). Following Sumita al. (Sumita et al. 2018). we apply our MP-MCTS for finding molecules with greater absorption wavelength but limited to 2500 nm.
Model and dataset. Our model is based GRU, which mainly consists of one GRU layer. Input data represents 27 SMILES symbols in one-hot vectors, which represents the symbols appeared the training dataset. The GRU layer has 27-dim input/256-dim output and the last dense layer has outputs 27 values with softmax. The model was pre-trained using a molecule dataset that contains 13K molecules (only H, O. N, and C elements included) extracted from the PubChemQC database (Nakata & Shimazaki 2017).
Calculating wavelength property and reward function. Following (Sumita al. 2018). the wavelength property was evaluated by DFT calculations with B3LYP/3-21G" level setting using Gaussian 16 (Frisch et al., (2016). We used one core (for simplicity) for the DFT calculation. The reward function is defined as equation 4 If the generated molecules are valid, then we assign positive reward within (-1, 1] as shown in equation 4 Negative reward -1 is assigned in case the generated molecule is invalid, DFT fails, or the wavelength is greater than the limit.
0.01 x wovelength
(4)
+ 0.01 X |wavelength)
Optimization of wavelength property. Table 2 summarizes the optimized wavelength (nm) of MP-MCTS approach for varying number of CPU cores. 3 independent runs and 6 hours time limit were applied to each setting, and the average and standard deviation of the best scores were shown.
C.3 SIMILARITY SEARCH
To test our MP-MCTS for another type of problem, we ran our algorithm using Zaleplon MPO, one of the Guacamol benchmarks (Brown et al. 2019). Unlike the property based scores (c.g., penalized logP or the wavelength score), Zaleplon MPO aims to find similar but not exactly the same molecules as the given target molecule. Table shows the results for 10 minutes x runs. The best score was 0.659, which observed in of the runs for 256 cores. The score is lower than the best score of 0.754 achieved by Graph GA, according to the Guacamol website. Further validation is needed to assess the effectiveness of our method for this type of problem.
shows
15

---

Figure 6: Top molecules designed by MP-MCTS (a) Top molecules with highest penalized logP Published as a conference paper at ICLR 2021
(a)
14.48
ott.://c........................ jel
14.77
15.13
(b)
O-NeTrecmcTGG-OIIICC
Ci-O0no
2447.2
2455.4
score. (b) Top 3 molecules with highest wavelength/nm property.
D PSEUDO CODE
The Pscudocode for TDS-UCT, TDS-dF-UCT, and MP-MCTS are shown in Algorithm 1 and All of the workers call the function TDS JCS_, TDS_d df UCTO, or MP_MCP PPMMCSSO respectively, and continue until timeup.
16

---

Published as a conference paper at ICLR 2021
Algorithm Pseudocode for TDS-UCT
1: function TDS_ (DS_UCT)
2: Initialize Hash Table, Initialize job_queue j_
3: initial job_ = |SELECT, root noo_]
4: if' this worker is the www.wwowowwwwwweeeeeeeee then
5: for N_jobs do
6:
job qee.quuueuusunnnn job)
7: end for
8:
end if
9:
while TimelsRemaining do
Receive all incoming messages and push to job queue if job queue.NotEmpty() then
11:
_jo__tyee, node) job wtw.uuueeeeu.... Pop()
13:
if job_type == SELECT then
14:
node is in HashTable then
15:
node = Look Loohh
16:
if node not yet expanded then Expansion(node) end if
17:
Expand node.children on the second visit
18:
best ccilld=SSeecctionnndde) wtr.irtualllossnoodoe httr:raiill..ooooccceecceeeeetta
19:
20:
TriteeToo
SendMessage((ELLECC best_ child], dest=home_ else
dest-homee_workerbbsss.do worker(best_chill)
22:
Reward-Siimlationnnndd)
24:
n (Reward)) Taaie
25:
26:
SendMessage(BP, node], dest=hone__ookertndde.preee
end if
28:
else if job_type- == BP then
29:
parent = Tocce
b parent should be in hashtable on BP
30:
31:
parent. pareent.jpaateecnodeeeeweaa WriiteTTFFashhTabbbeepeeen) if parent t= root_node then
32:
33:
SendMessage(BBP, parent], dest=home d worker(parent.pareen)) else
35:
best_ childd-Selecciio(pparn)))
37:
child)) SendMessage((EELECC. best best_chhidd] dest=home, worker(best_child)
AddVirrullloss(pprent.cci
38:
39:
end if end end if
40:
41:
42:
end while
43:
end function
17

---

Published as a conference paper at ICLR 2021
Algorithm 2 Pseudocode for TDS-dFUCCT
1: function TDS DF SUCT())
2: Initialize Hash Table, Initialize job_queee, N N_jobs=3x4worken
3: initial job [SELECT, root_nooe None]
4: if this worker is the home_ waaeeewooeeerrot_noee then
5:
for N_jobs do too__queue.Pushiniittal
6:
7:
end for
8:
end
9:
while TimeIsRemaining do
10:
Receive all incoming messages and push to job qub_queue if ceob_queee.Noteee queue.NotEmptyO then
11:
12:
(job_type, node, ucb_ ser__hitorr) = job_ leabb_quee.Poopl if job_type SELECT then
14:
if node is in HashTable then
node Look Haaakaaaaedll if node not yet expanded then Expansion(node) end if
16:
Expand node.children on the second visit
18:
best_ _ccildd-Seeeccionnnndee)) AddVirtualLosssnode. haapalooossssoocciiiceeeeeeeeeid
19:
20:
WriteTToHHashTTabeeenddde)
21:
ucb heapory.Apppennmndeeeehilllloe
D ucb history only in messages SendMessage((ELECCT best child, ucb historyl.
22:
23:
dest=home_wortd werter(beeeeeeeeeeeooo... (eieeeeeessschhdd))
24:
else
25:
Reward-SSimlltionnndde))
node. Sedee.ppdteeRewaaaa
27:
WriteToHash Table ucb
ucb history only in messages SendMessage node, node.uch historyl,
29:
30:
dest=home_ wareee__ooree(odeeprrreeee
31:
end if
32:
else if job_type then
33:
parent = Losh parent) parent should be in hashtable on BP
34:
Virtuallosss (crrretttccilreenoooe]]
35:
parent. CareentUppdaee(modeeeeeee
36:
WriteTTofaass//abeeeeeeen)
37:
current_best_nne
wub_historyy Qurrenetnee)))))))
38:
ucb_ Boo__listoyy.emovBBooooteee
b nnc__iitoo is only in messages if parent == current best _ode OR parent root_ node then
40:
best ccchlld-SSelcccio(pprrntttt caddVirualloosspppnnn.ccddeeeree child))
42:
TriieeTo ucb hww.thitttttteeeooe hisstoy.Appeenmppannttciltlee
uub__uhn cob_history only in messages
44:
SendMessage((EELECTT best child, ueb history].
45:
dest=home_workere haarhhomm___orrkrbbbs_hhhhhlll
46:
else
47:
SendMessage(BBP, parent, parent.ueb dest=home_ hattooome__ookkeerrrenttppperree
parentt,parent.ubb parent.ueb_historyl,,
48:
49:
end if end if
50:
51:
end if
end while
53:
end function
18

---

Published as a conference paper at ICLR 2021
Algorithm 3 Pscudocode for MP-MCTS
1: function MP MCTS()
2: Initialize Hash Table, Initialize nob_queue, N N_jobs=3x4workers
3: initial job [SELECT, root_ root_node, None]
4: if this worker is the home_homeeeee setee_wooeeerroo_ooeee node) then
5:
for N_jobs do lib__queue.Pushinittall
6:
7:
end for
8:
end
9:
while TimeIsRemaining do
10:
Receive all incoming messages and push to job qub_queue if Lob__qeee..Notiee queue.NotEmptyO then
11:
12:
(job_type, node, ucb_ ree__istory) = job_jjoueeeee leabb_queeePoopl if job_type SELECT then
14:
if node is in HashTable then
node Look Haahaaaaeello if node not yet expanded then Expansion(node) end if
16:
Expand node.children on the second visit
18:
best best_child= c_ccild=SSelcccionnnddee) addViirualllssfooddechlddddrr
19:
20:
node. Aale.uuudeeUCBHisttorryune (uithh_otttrr) (riieTofaashTaallennddde))
21:
22:
ucb hiistory-pppem//nddeecchlddd
23:
SendMessag((SELECT, best child, ueb history].
24:
sestshomme_workerrbss__chhe
25:
else
Reward-SSimulationnndd))
27:
node.Updater Update WriieTooHasshhaaeenndddd
29:
SendMessage node, node.ucb historyl,
30:
dest=home wwwpe//oooeeeeeeeeeeereee parent))
31:
end if
32:
else if job_type == then
33:
parent = (abiossshnTalcnnoodeeearann
parent) parent should be in hashtable on BP
34:
Vor wtw.tossaaaattt.cacceeeeeeeeeeee children(node))
35:
pareent.jpdateenodeeeeeee reward)
36:
37:
WriieTToFHash/Taabbeepeen))
38:
current_best_node. = parent.ucb. wwwstory.eeeuureenttttt
if parent current best node OR parent root_ node then
40:
best w.cchlll-SSelcccioppaaennt
AdddiirtullLoosspppnntthillhree child]
42:
Write/ToHHass//labepppeeen
ucb hwwtohot hissory-Appenn(pprenn.chhiaa
44:
SendMessage((EELECTT boest_chile ueb history].
45:
dest=home (iieehomm___orkkrbbbs_cchhh))
46:
else SendMessage(BB,, parent, parent.ueb dest=home_ htttroomm_wwookeerrrentttppeeree
47:
parentt,parentuubb parent.uebbhistorryy,
48:
49:
end if end if
50:
51:
end if
end while
53:
end function
19


Reviews:
[{"review_id": "eXU3zLpANq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work the authors apply a distributed parallel Monte-Carlo Tree Search (MCTS) algorithm to the Molecular Design problem. The goal of this paper is to speed-up the computation needed by an MCTS algorithm using parallelization over multiple machines. The authors show how to modify a previously successful parallel MCTS algorithm (namely, TDS-DF-UCT) to address its shortcoming that leads to shallow and wide trees. The modification that is performed changes the way that the history on the nodes are stored and propagated, which leads the algorithm to construct trees with more similar characteristics with those constructed by a sequential algorithm that is allowed to use time equal to the number of processors times the time required by the parallel implementation.\n\nThe authors then apply their algorithm to the molecular design problem using a pre-trained GRU-based model for rollout and expansion, and compared the quality of the method with non-parallel implementations (that are allowed to use time equal to the time of the parallel algorithm times the number of CPUs used; the goal is to obtain solutions with quality close to the performance of such algorithms), and to existing parallel implementations of MCTS algorithms (that lead to non-ideal MCTS tree structures). The experiments show that, in terms of quality, the proposed parallel MCTS algorithm outperforms the rest of the parallel MCTS algorithms, given the same amount of time, and performs closer to the non-parallel implementation which takes much more time. \n\nFinally, the authors compare their method, in terms of quality, to state-of-the-art algorithms for the problem and show that their method outperforms the rest of the methods significantly.\n\nPROS:\n+ The experimental results show that the proposed algorithms coupled with the necessary model achieve very good parallelization\n+ The proposed algorithm outperforms the state-of-the-art approaches on an application to the Molecular Design problem\n+ This is the first work that applied the distributed parallel MCTS algorithms for the Molecular Design problem\n\nCONS:\n- The technical contribution of the paper seems rather incremental to previous work on parallel MCTS algorithms\n\nThe proposed method shows a significant speedup for the molecular design problem, and for nearly-linear speedup similar solution quality is achieved. Although I'm not an expert in Molecular Design, it seems to me that this work should also be of interest to people in Computational Chemistry. On the other hand, the new methodology is not tight to the specific application and might find applications to other problems where MCTS algorithms were found to be successful. \nMy main complaint is the incremental technical contribution of the paper, which is limited to adapting the history message passing and storing in the parallel MCTS method proposed by (Yoshizoe et al 2011). On the other hand, it is evident that this small change to the algorithm is able to achieve a much more desirable MCTS tree structure and performance. \n\nOverall, I tend to be positive about the paper, given it's claimed significant contribution in the application to the Molecular Design problem.  \n\nSmall things:\n* In Table 2, how long did you let the competitor algorithms run? Was it again 10 minutes?\n* Is the massively parallel terminology widely used for distributed parallel algorithms? This conflicts with the terminology for the Massively Parallel Computation model, which is an abstraction of MapReduce, Hadoop, and other systems. I suggest using \"Distributed Parallel\".\n* \"the the\" in page 3.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WGXhaZnVtd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to provide a scalable and competitive molecular design technique based on MCTS. Machine learning guided molecular design is a popular field and many solutions have been developed in the recent years. There is appeal, due to the high dimensionality of search space, to resort to MCTS based approaches that leverage stochastic pruning of the search space as an effective way of making the problem tractable. \n\nPositives: \n- The innovations herein are focused on engineering a parallelizable MTCS algorithm that can explore the space much faster (though it requires much higher compute at once).  This can be a useful tool for faster computation and proposal of drug-like molecules\n\nNegatives: \n- In principle the methods introduced here have little specialized domain relevance to chemical design. I.e. it's unclear why the paper is focused on chemical design and benchmarks itself there. It seems more appropriate to show that the scalability can be general to any MCTS application. As such, it might be better to apply it in spaces where MCTS is already better developed. \n\n- The paper is light on results and their discussion. Instead of spending as much space talking about how MTCS works, which is well known, the authors are better off showing more metrics related to drug-likeness (e.g. QED) or validity checks.  It is unclear if the solutions proposed are actually sensible which could overstate the performance of the method. Adding long chains of carbon to improve the score is a notorious problem for these design methods, and it does seem to be an issue for the designed molecules presented in the appendix. I'm not a chemist so I cannot validate this molecules by eye, but I am quite concerned about the lack of validity checks. \n- Comparison and discussion of more performant methods like Zhou et al 2019 Scientific Reports (optimization of molecules via RL). \n- It is also unclear if the scoring method for logP used in this study is the same as the one used by the other methods mentioned. At least it doesn't seem to match the method used in Zhou et al 2019 or others reported there. \n\nMinor comments\nTable 1 boldface is confusing, it makes more sense to boldface the best performing models. \n\n\n------\n\nI think the paper makes some interesting engineering contributions, but the focus on chemical design is somewhat arbitrary, and the authors don't investigate the domain application with enough depth. Especially, I'm quite concerned about validity of the designed molecules, and lack of clarity that all methods reported herein are actually run with the same scoring method (e.g. the numbers aren't simply picked up from elsewhere when the oracle was different).  If the authors are able to provide more reassurance about the validity of the design, and the soundness of the oracle they have chosen to use, I'm happy to improve my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "KdCxzJHMald", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes a new algorithm to scale up parallel MCTS. The proposed method, MP-MCTS is a modified version of previous efforts to parallelize MCTS (TDS-UCT, TDS-df-UCT), all using virtual loss and modern MCTS enhancements (NN-guided selection learned offline). In exchange for small additional memory requirement, MP-MCTS is able to grow significantly deeper trees at much higher levels of parallelism. Overall, the approach is shown to be quite effective at constructing deeper trees efficiently on large MPI clusters and aligns nicely with results in the single-worker MCTS literature (shallow vs deep trees). The experimental section is nicely detailed and shows strong performance gains over the state of the art in molecular design. Overall, this seems to be a very successful scale-up of MCTS, resulting in a new state-of-the-art result in molecular design. The algorithmic description is a bit thin right now. Please consider including a detailed discussion of the pseudo-code.\n\nStrengths:\n  + Intuitively clear, reasonably well-written. The illustrative example is very helpful.\n  + Proposed algorithm significantly advances the state-of-the-art in distributed, parallel MCTS.\n  + Nicely detailed set of experiments showing intuitively clear results.\n  + The paper does a good job of making its contributions clear relative to the broader body of work in MCTS and molecular design.\n\nAreas of improvement:\n  - The main algorithmic descriptions (Section 3) feel a bit \"thin\". Details of the algorithmic contributions are difficult to spot on the first read. I had to refer to Algorithms 1 and 2 in the Appendix to understand what was really happening and the pseudo-code seems incomplete. Please consider bringing those 2 algorithms in to the main paper (although space could be tight). Also, pseudo-code for TDS-df-UCT seems to be missing.\n  - I'm not sure I fully understood the reasons behind TDS-df-UCT's shallower trees. It seems to have something to do with the search tree being biased towards making local changes (rather than propagating info at every leaf up to the root) but the paper hand-waves a bit about this aspect (\"It is presumed that TDS-df-UCT does too few backpropagations\"). Figure 5a and 5b illustrate the issues empirically which is nice, but I think a more careful explanation and / or analysis of the root cause would better motivate MP-MCTS.\n  - The terminology about workers and home processors feels like it could be simplified a bit. If I understand correctly, each node in the tree is mapped to exactly one worker (MPI process = core). Any message sent to that node will be processed by the assigned worker. Is there more to it than this?\n\nQuestions\n  * Why does TDS-df-UCT generate shallow trees?\n  * What does `node = LookUpHashTable(node)` do? \n  * Is the if-else expression in Algorithms 1 and 2 correct? Shouldn't an unsuccessful hash table lookup result in expansion rather than selection? Also, what happens to `new_node`?\n  * What exactly is the difference between worker and home processor? Doesn't the same worker handle every message sent to the tree nodes it's been assigned to?\n  * Will you be releasing source code? I didn't see any links and the pseudo-code is incomplete.\n\n\nUPDATE: I thank the authors for their detailed feedback and updated paper. I'm a bit more in favor of acceptance of the paper now. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "IczQVN3F62s", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a novel parallelized implementation of Monte\nCarlo Tree Search (MCTS) that is evaluated in a molecule design domain. The MCTS\nloop uses the outcomes from prior iterations to guide future expansion of the\nsearch tree --- this complicates attempts to parallelize the algorithm, since\nsuch approaches will need to perform some degree of speculative expansion.\nHash-driven parallelization methods --- where each node in the search tree is\n\"owned\" by a worker --- have been used in the past, together with a \"virtual loss\"\naccounting system and message passing, to successfully parallelize MCTS. By\nincluding a statistics history table in the messages, the TDS-DF-UCT algorithm\nhas been shown to scale successfully with up to 100 workers by reducing\ncommunication congestion. The authors propose a simple modification to\nTDS-DF-UCT called MP-MCTS --- namely, storing the history table in each node,\ninstead of including it in the messages --- which significantly boosts the\nscalability of the algorithm.\n\nIn the remainder of the paper, the authors evaluate MP-MCTS in a molecule\nsynthesis domain, one which has recently drawn significant attention from the ML\ncommunity. The goal in this problem is to design novel molecules that maximize a\nparticular physicochemical property (in this case, a logP measure with\npenalties), which is a standard in this area. An RNN pre-trained on a database\nof drug molecules is used to generate candidate children at each node in the\nsearch tree, as well as to perform the rollouts. The authors demonstrate that\nMP-MCTS displays much better scaling behavior compared to prior parallel MCTS\nimplementations (TDS-UCT and TDS-DF-UCT) with up to 1024 workers. They also\nshow striking improvements over prior state-of-the-art methods for molecule\nsynthesis.\n\nStrengths of the paper:\n  + MCTS methods are of broad interest to the AI/ML community and this paper\n    offers an interesting application of the algorithm to a new, non-traditional\n    domain that has already drawn prior interest from ML researchers (including\n    publications at NeurIPS, ICML etc.).\n  + The parallel implementation of MCTS described is general and could be\n    applied to other problems.\n  + The proposed enhancement, while relatively straightforward, nevertheless\n    appears to offer significant gains, thus making it easy to adopt.\n  + The paper is well-written, organized and easy to follow.\n\nAreas for improvement/questions for the authors:\n  - While the results in Table 1 are convincing, I found the results in Table 2\n    less so, since computational resources have not been controlled for. While\n    there is merit to simply comparing the best molecules found by each method,\n    one does have to wonder how well something MolecularRNN might do with the\n    equivalent of 1024*10 core minutes.\n  - I found that the paper's reasons for MP-MCTS's gains over TDS-DF-UCT\n    somewhat unclear. Is it the fact that the messages that need to be passed\n    between workers are smaller in size? I also didn't understand what caused\n    TDS-DF-UCT to build wider/shallower trees. A slightly more detailed\n    discussion of this would be welcome and strengthen the paper.\n\nOn balance, I find it noteworthy that such a subtle tweak to an established\nalgorithm produces such significant improvement in performance on this domain.\nWhile there are some methodological questions and some claims that may need\ntempering, I think the results are sufficiently interesting for me to recommend\nACCEPTANCE.\n\nMinor comment:\n  - On page 3, the authors write: \"and a level d node denotes the d-th symbol\n    in a SMILES string\". I found this a little confusing at first. I might\n    consider rephrasing this along the lines of: \"each path through the tree\n    represents a left-to-right enumeration of the characters in the SMILES\n    string\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-6c5YD53M-s", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present an approach to parallelize MCTS on a large number of processors. Out of potentially many different applications, they chose to use the domain of molecular design, and show improved performance over several baselines, including some baselines using non-parallel MCTS. Impressively, this is achieved in very little wall time.\n \n \nStrengths:\n-  Very simple idea (this is good), straightforward execution, no faff\n- The approach is non domain specific, and could be applied in many different areas\n- Good empirical results\n\n \nWeaknesses:\n- Not very fancy from the ML side\n- The validation is weak, and to some extent outdated. I understand that drug design application is only an example, however, nevertheless I would strongly suggest that the authors run the more challenging guacamol benchmark, since the benchmarks the authors use are know to be very easy (see https://github.com/BenevolentAI/guacamol / https://pubs.acs.org/doi/abs/10.1021/acs.jcim.8b00839 )\n \nQuestion:\n- How much tuning of the size of the virtual loss is required to optimally use the provided CPUs?\n- By using the virtual loss, do we lose some of the theoretical guarantees of UCT?\n \nAll in all, I think this paper could in my opinion be accepted at ICLR if the authors commit to running the harder guacamol benchmarks for the camera ready version.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I think this is a very solid and good work in the topic of "Practical Massive Parallel MCTS."   I think it will be good to open up perspectives among ICLR's audience going beyond just Deep Learning and Machine Learning. I also noted a lot of positive comments during the evaluation and discussion period.

Still, it was a borderline case and not an easy decision (primarily because of the concerns raised by R3 towards the end of the discussion period). In the end the program committee decided that the paper does meet the bar.  We think that the work is interesting and original, though not without weaknesses.

Decision: Accept (Poster)