Title: WATCH THE UNOBSERVED: A SIMPLE APPROACH TO PARALLELIZING MONTE CARLO TREE SEARCH

Abstract: Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature: each rollout heavily relies on the statistics (e.g., node visitation counts) estimated from previous simulations to achieve an effective exploration-exploitation tradeoff. In spite of these difficulties, we develop an algorithm, WU-UCT 1 , to effectively parallelize MCTS, which achieves linear speedup and exhibits only limited performance loss with an increasing number of workers. The key idea in WU-UCT is a set of statistics that we introduce to track the number of on-going yet incomplete simulation queries (named as unobserved samples). These statistics are used to modify the UCT tree policy in the selection steps in a principled manner to retain effective exploration-exploitation tradeoff when we parallelize the most time-consuming expansion and simulation steps. Experiments on a proprietary benchmark and the Atari Game benchmark demonstrate the linear speedup and the superior performance of WU-UCT comparing to existing techniques.

1. INTRODUCTION:

Recently, Monte Carlo Tree Search (MCTS) algorithms such as UCT (Kocsis et al., 2006) have achieved great success in solving many challenging artificial intelligence (AI) benchmarks, including video games (Guo et al., 2016) and Go (Silver et al., 2016) . However, they rely on a large number (e.g. millions) of interactions with the environment emulator to construct search trees for decision-making, which leads to high time complexity (Browne et al., 2012) . For this reason, there has been an increasing demand for parallelizing MCTS over multiple workers. However, parallelizing MCTS without degrading its performance is difficult (Segal, 2010; Mirsoleimani et al., 2018a; Chaslot et al., 2008) , mainly due to the fact that each MCTS iteration requires information from all previous iterations to provide effective exploration-exploitation tradeoff. Specifically, parallelizing MCTS would inevitably obscure these crucial information, and we will show in Section 2.2 that this loss of information potentially results in a significant performance drop. The key question is therefore how to acquire and utilize more available information to mitigate the information loss caused by parallelization and help the algorithm to achieve better exploration-exploitation tradeoff.

To this end, we propose WU-UCT (Watch the Unovserved in UCT), a novel parallel MCTS algorithm that attains linear speedup with only limited performance loss. This is achieved by a conceptual innovation (Section 3.1) as well as an efficient real system implementation (Section 3.2). Specifically, the key idea in WU-UCT to overcome the aforementioned challenge is a set of statistics that tracks the number of on-going yet incomplete simulation queries (named as unobserved samples). We combine these newly devised statistics with the original statistics of observed samples to modify UCT's policy in the selection steps in a principled manner, which, as we shall show in Section 4, effectively retains exploration-exploitation tradeoff during parallelization. Our proposed approach has been successfully deployed in a production system for efficiently and accurately estimating the rate at which users pass levels (termed user pass-rate) in a mobile game "Joy City", with the purpose of reducing their design cycles. On this benchmark, we show that WU-UCT achieves near-optimal linear speedup and superior performance in predicting user pass-rate (Section 5.1). We further evaluate WU-UCT on the Atari Game benchmark and compare it to state-of-the-art parallel MCTS algorithms (Section 5.2), which also demonstrate our superior speedup and performance.

2. ON THE DIFFICULTIES OF PARALLELIZING MCTS:

We first introduce the MCTS and the UCT algorithms, along with their difficulties in parallelization.

2.1. MONTE CARLO TREE SEARCH AND UPPER CONFIDENCE BOUND FOR TREES (UCT):

We consider the Markov Decision Process (MDP) S, A, R, P, γ , where an agent interacts with the environment in order to maximize a long-term cumulative reward. Specifically, an agent at state s t ∈ S takes an action a t ∈ A according to a policy π, so that the MDP transits to the next state s t+1 ∼ P (s t+1 |s t , a t ) and emits a reward R(s t , a t ). 2 The objective of the agent is to learn an optimal policy π * such that the long-term cumulative reward is maximized:

EQUATION

where s ∈ S denotes the initial state and γ ∈ (0, 1] is the discount factor. 3 Many reinforcement learning (RL) algorithms have been developed to solve the above problem (Sutton & Barto, 2018) , including model-free algorithms (Mnih et al., 2013; 2016; Williams, 1992; Konda & Tsitsiklis, 2000; Schulman et al., 2015; 2017) and model-based algorithms (Nagabandi et al., 2018; Weber et al., 2017; Bertsekas, 2005; Deisenroth & Rasmussen, 2011) . Monte Carlo Tree Search (MCTS) is a model-based RL algorithm that plans the best action at each time step (Browne et al., 2012) . Specifically, it uses the MDP model (or its sampler) to identify the best action at each time step by constructing a search tree (Figure 1 (a)), where each node s represents a visited state, each edge from s denotes an action a s that can be taken at that state, and the landing node s denotes the state it transits to after taking a s . As shown in Figure 1 (a), MCTS repeatedly performs four sequential steps: selection, expansion, simulation and backpropagation. The selection step traverses over the existing search tree until the leaf node (or other termination conditions are satisfied) by choosing actions (edges) a s at each node s according to a tree policy. One widely used node-selection policy is the one used in the Upper Confidence bound for Trees (UCT) (Kocsis et al., 2006) :

EQUATION

where C(s) denotes the set of all child nodes for s; the first term V s is an estimate for the long-term cumulative reward that can be received when starting from the state represented by node s , and the second term represents the uncertainty (size of the confidence interval) of that estimate. The confidence interval is calculated based on the Upper Confidence Bound (UCB) (Auer et al., 2002; Auer, 2002) using N s and N s , which denote the number of times that the nodes s and s have been visited, respectively. Therefore, the key idea of the UCT policy (2) is to select the best action according to an optimistic estimation (i.e., the upper confidence bound) of the expected return, which strikes a balance between the exploitation (first term) and the exploration (second term) with β controlling their tradeoff. Once the selection process reaches a leaf node of the search tree (or other termination conditions are met), we will expand the node according to a prior policy by adding a new child node. Then, in the simulation step, we estimate its value function (cumulative reward) Vs by running the environment simulator with a default (simulation) policy. Finally, during backpropagation, we update the statistics V s and N s from the leaf node s T to the root node s 0 of the selected path by recursively performing the following update (i.e., from t = T -1 to t = 0): 

EQUATION

Simulation Backpropagation:

Recursively select child node with (2). Select an action 𝑎 to expand and construct child node accordingly.

Simulate from current node's state 𝑠 % with policy 𝜋.

Recursively update visited nodes with simulation return.

Repeat:

(a) Each (non-parallel) MCTS rollout consists of four sequential steps: selection, expansion, simulation and backpropagation, where the expansion and the simulation steps are generally most time-consuming. 

𝑠 " 𝑠 # 𝑠 $ 𝑠 % 𝑠 & 𝑠 ' A B C 𝑉 ' 𝑁 ' 𝑉 # 𝑁 # 𝑉 $ 𝑁 $ 𝑉 & 𝑁 & 𝑉 % 𝑁 % 𝑠 + (b) Ideal parallelization 𝑠 " 𝑠 # 𝑠 $ 𝑠 % A B C 𝑉 % 𝑁 % 𝑉 " 𝑁 " 𝑉 # 𝑁 # 𝑉 ) 𝑁 ) 𝑉 $ 𝑁 $ 𝑛 + 𝑠 ) (c) Naive parallelization 𝑠 " 𝑠 # 𝑠 $ 𝑠 % 𝑠 & 𝑠 ' A B C 𝑉 ' 𝑁 ' 𝑂 ' 𝑉 $ 𝑁 $ 𝑉 " 𝑁 " 𝑂 " 𝑉 & 𝑁 & 𝑂 & 𝑉 % 𝑁 % 𝑂 %

Simulation in progress:

After Backpropagation where Vs T is the simulation return of s T ; a t denotes the action selected following (2) at state s t .

Selection in progress:



2.2. THE INTRINSIC DIFFICULTIES OF PARALLELIZING MCTS:

The above discussion implies that the MCTS algorithm is intrinsically sequential: each selection step in a new rollout requires the previous rollouts to complete in order to deliver the updated statistics, V s and N s , for the UCT tree policy (2). Although this requirement of up-to-date statistics is not mandatory for implementation, it is in practice intensively required to achieve effective explorationexploitation tradeoff (Auer et al., 2002) . Specifically, up-to-date statistics best help the UCT tree policy to identify and prune non-rewarding branches as well as extensively visiting rewarding paths for additional planning depth. Likewise, to achieve the best possible performance, when multiple workers are used, it is also important to ensure that each worker uses the most recent statistics (the colored V s and N s in Figure 1(b) ) in its own selection step. However, this is impossible in parallelizing MCTS based on the following observations. First, the expansion step and the simulation step are generally more time-consuming compared to the other two steps, because they involve a large number of interactions with the environment (or its simulator). Therefore, as exemplified by Figure 1 (c), when a worker C initiates a new selection step, the other workers A and B are most likely still in their simulation or expansion steps. This prevents them from updating the (global) statistics for other workers like C, which happens at their respective backpropagation steps. Using outdated statistics (the gray-colored V s and N s ) at different workers could lead to a significant performance loss given a fixed target speedup, due to behaviors like collapes of exploration or exploitation failure, which we shall discuss thoroughly in Section 4. To give an example, Figure 1 (c) illustrates the collapse of exploration, where worker C traverses over the same path as the worker A in its selection step due to the determinism of (2). Specifically, if the statistics are unchanged between the moments that worker A and C begin their own selection steps, they will choose the same node according to (2), which greatly reduces the diversity of exploration. Therefore, the key question that we want to address in parallelizing MCTS is how to track the correct statistics and modify the UCT policy in a principled manner, with the hope of retaining effective exploration-exploitation tradeoff at different workers.

3. WU-UCT:

In this section, we first develop the conceptual idea of our WU-UCT algorithm (Section 3.1), and then we present a real system implementation using a master-worker architecture (Section 3.2).

3.1. WATCH THE UNOBSERVED SAMPLES IN UCT TREE POLICY:

As we pointed out earlier, the key question we want to address in parallelizing MCTS is how to deliver the most up-to-date statistics {V s , N s } to each worker so that they can achieve effective exploration-exploitation tradeoff in its selection step. This is assumed to be the case in the ideal parallelization in Figure 1(b) . Algorithmically, it is equivalent to the sequential MCTS except that the rollouts are performed in parallel by different workers. Unfortunately, in practice, the statistics {V s , N s } available to each worker are generally outdated because of the slow and incomplete simulation and expansion steps at the other workers. Specifically, since the estimated value Vs is unobservable before simulations complete and workers should not wait for the updated statistics to proceed, the (partial) loss of statistics {V s , N s } is unavoidable. Now the question becomes: is there an alternative way to addressing the issue? The answer is in the affirmative and is explained below.

Aiming at bridging the gap between naive parallelization and the ideal case, we closely examine their difference in terms of the availability of statistics. As illustrated by the colors of the statistics, their only difference in {V s , N s } is caused by the on-going simulation process. As suggested by (3), although V s can only be updated after a simulation step is completed, the newest N s information can actually be available as early as a worker initiates a new rollout. This is the key insight that we leverage to enable effective parallelization in our WU-UCT algorithm. Motivated by this, we introduce another quantity, O s , to count the number of rollouts that have been initiated but not yet completed, which we name as unobserved samples. That is, our new statistics, O s , watch the number of unobserved samples, and are then used to correct the UCT tree policy (2) into the following form:

EQUATION

)

The intuition of the above modified node-selection policy is that when there are O s workers simulating (querying) node s, the confidence interval at node s will eventually be shrunk after they complete. Therefore, adding O s and O s to the exploration term considers such a fact beforehand and let other workers be aware of it. Despite its simple form, (4) provides a principled way to retain effective exploration-exploitation tradeoff under parallel settings; it corrects the confidence bound towards better exploration-exploitation tradeoff. As the confidence level is instantly updated (i.e., at the beginning of simulation), more recent workers are guaranteed to observe additional statistics, which prevent them from extensively querying the same node as well as find better nodes for them to query. For example, when multiple children are in demand for exploration, (4) allows them to be explored evenly. In contrast, when a node has been sufficiently visited (i.e., large N s and N s ), adding O s and O s from the unobserved samples have little effect on (4) because the confidence interval is sufficiently shrunk around V s , allowing extensively exploitation of the best-valued child.

3.2. SYSTEM IMPLEMENTATION USING MASTER-WORKER ARCHITECTURES:

We now proceed to explain the system implementation of WU-UCT, where the overall architecture is shown in Figure 2 (a) (see Appendix A for the details). Specifically, we use a master-worker architecture to implement the WU-UCT algorithm with the following considerations. First, since the expansion and the simulation steps are much more time-consuming compared to the selection and the backpropagation steps, they should be intensively parallelized. In fact, they are relatively easy to parallelize (e.g., different simulations could be performed independently). Second, as we discussed earlier, different workers need to access the most up-to-date statistics {V s , N s , O s } in order to achieve successful exploration-exploitation tradeoff. To this end, a centralized architecture for the selection and backpropagation step is more preferable as it allows adding strict restrictions to the retrieval and update of the statistics, making them up-to-date. Specifically, we use a centralized master process to maintain a global set of statistics (in addition to other data such as game states), and let it be in charge of the backpropagation step (i.e., updating the global statistics) and the selection step (i.e., exploiting the global statistics). As shown in Figure 2 (a), the master process 

Expansion workers (worker):

Select an action to expand, then load the game-state, execute that action. Return reward, episode terminal signal, and the result game-state.

Simulation workers (worker):

Load game-state, then perform rollout until termination. Return the cumulative discounted reward.

Assign/gather task to/from workers.

Task buffer:

Assign/gather task to/from workers.

Game-state Game-state & copy of current node new game-state, reward, etc.

Cumulative reward (a) The system architecture that implements WU-UCT. 

EQUATION

where incomplete update is performed before the simulation task starts, allowing the updated statistics to be instantly available globally; complete update is done after the simulation return is available, resembling the backpropagation step in the sequential algorithm. In addition, V s is also updated in the complete update step using (3). Such a clear division of labor between the master and the workers provides sequential selection and backpropagation steps when we parallelize the costly expansion and simulation steps. It ensures up-to-date statistics for all workers by the centralized master process and achieves linear speedup without much performance degradation (see Section 5 for the experimental results).

To justify the above rationale of our system design, we perform a set of running time analysis for our developed WU-UCT system and report the results in Figure 2 (b)-(c). We show the timeconsumption for different parts at the master and at the workers. First, we focus exclusively on the workers. With a close-to-100% occupancy rate for the simulation workers, the simulation step is fully parallelized. Although the expansion workers are not fully utilized, the expansion step is maximumly parallelized since the number of required simulation and expansion tasks is identical. This suggests the existence of an optimal (task-dependent) ratio between the number of expansion workers and the number of simulation workers that fully parallelize both steps with the least resources (e.g. memory). Returning to the master process, on both benchmarks, we see a clear dominance of the time spent on the simulation and the expansion steps even they are both parallelized by 16 workers. This supports our design to parallelize only the simulation and expansion steps. We finally focus on the communication overhead caused by parallelization. Although more time-consuming compared to simulation and backpropagation, the communication overhead is negligible compared to the time used by the expansion and the simulation steps. Other details in our system, such as the centralized game-state storage, are further discussed in Appendix A.

4. THE BENEFITS OF WATCHING UNOBSERVED SAMPLES:

In this section, we discuss the benefits of watching unobserved samples in WU-UCT, and compare it with several popular parallel MCTS algorithms (Figure 3 ), including Leaf Parallelization (LeafP), (c) Root parallelization (RootP)

Figure 3 : Three popular parallel MCTS algorithms. LeafP parallelizes the simulation steps, TreeP uses virtual loss to encourage exploration, and RootP parallelizes the subtrees of the root node.

Tree Parallelization (TreeP) with virtual loss, and Root Parallelization (RootP). 4 LeafP parallelizes the leaf simulation, which leads to an effective hex game solver (Wang et al., 2018) . TreeP with virtual loss has recently achieved great success in challenging real-world tasks such as Go (Silver et al., 2016) . And RootP parallelizes the subtrees of the root node at different workers and aggregates the statistics of the subtrees after all the workers complete their simulations (Soejima et al., 2010) .

We argue that, by introducing the additional statistics O s , WU-UCT achieves a better explorationexploitation tradeoff than the above methods. First, LeafP and TreeP represent two extremes in such a tradeoff. LeafP lacks diversity in exploration as all its workers are assigned to simulating the same node, leading to performance drop caused by collapse of exploration in much the same way as the naive parallelization (see Figure 1(c) ). In contrast, although the virtual loss used in TreeP could encourage exploration diversity, this hard additive penalty could cause exploitatin failure: workers will be less likely to co-simulating the same node even when they are certain that it is optimal (Mirsoleimani et al., 2017) . RootP tries to avoid these issues by letting workers perform an independent tree search. However, this reduces the equivalent number of rollouts at each worker, decreasing the accuracy of the UCT policy (2). Different from the above three approaches, WU-UCT achieves a much better exploration-exploitation tradeoff in the following manner. It encourages exploration by using O s to "penalize" the nodes that have many in-progress simulations. Meanwhile, it allows multiple workers to exploit the most rewarding node since this "penalty" vanishes when N s becomes large (see (4)).

5. EXPERIMENTS:

This section evaluates the proposed WU-UCT algorithm on a production system to predict the user pass-rate of a mobile game (Section 5.1) as well as on the public Atari Game benchmark (Section 5.2), aiming at demonstrating the superior performance and near-linear speedup of WU-UCT.

5.1. EXPERIMENTS ON THE "JOY CITY" GAME:

Joy City is a level-oriented game with diverse and challenging gameplay. Players tap to eliminate connected items on the game board. To pass a level, players have to complete certain goals within a given number of steps. 5 The number of steps used to pass a level (termed game step) is the main performance metric, which differentiates masters from beginners. It is a challenging reinforcement learning task due to its large number of game-state (over 12 9×9 ) and high randomness in the transition. The goal of the production system is to accurately predict the user pass-rate of different game-levels, providing useful and fast feedback for game design. Powered by WU-UCT, the system runs 16× faster while accurately predicting user pass-rate (8.6% MAE). In this subsection, we concentrate our analysis on the speedup and performance of WU-UCT using two typical game-levels (Level-35 and Level-58) 6 , and refer the readers interested in the user pass-rate prediction system to Appendix C.

We evaluate WU-UCT with different numbers of expansion and simulation workers (from 1 to 16) and report the speedup results in Figures 4(a )-(b). For all experiments, we fix the total number of simulations to 500. First, note that when we have the same number of expansion workers and simulation workers, WU-UCT achieves linear speedup. Furthermore, Figures 4 also suggest that both the expansion workers and the simulation workers are crucial, since lowering the number of workers from either sets decreases the speedup. Besides the near-linear speedup property, WU-UCT suffers negligible performance loss with the increasing number of workers, as shown in Figures 4(c)-(d) .

The standard deviations of the performance (measured in the average game steps) over different numbers of expansion and simulation workers are only 0.67 and 1.22 for Level-35 and Level-58, respectively, which are much smaller than their average game steps (12 and 30).

5.2. EXPERIMENTS ON THE ATARI GAME BENCHMARK:

We further evaluate WU-UCT on Atari Games (Bellemare et al., 2013), a classical benchmark for reinforcement learning (RL) and planning algorithms (Guo et al., 2014) . The Atari Games are an ideal testbed for MCTS algorithms for its long planning horizon (several thousand), sparse reward, and complex game strategy. We compare WU-UCT to three parallel MCTS algorithms discussed in Section 4: TreeP, LeafP, and RootP (additional experiment results comparing WU-UCT with a variant of TreeP is provided in Appendix E). We also report the results of sequential UCT (≈ 16× slower than WU-UCT) and PPO (Schulman et al., 2017) as reference. Generally, the performance of sequential UCT sets an upper bound for parallel UCT algorithms. PPO is included since we used a distilled PPO policy network (Hinton et al., 2015; Rusu et al., 2015) as the roll-out policy for all other algorithms. It is considered as a performance lower bound for both parallel and sequential UCT algorithms. All experiments are performed with a total of 128 simulation steps, and all parallel algorithms use 16 workers (see Appendix D for the details).

We first compare the performance, measured by average episode reward, between WU-UCT and the baselines on 15 Atari games, which is done with 16 simulation workers and 1 expansion worker (for a fair comparison, since baselines do not parallel the expansion step). Each task is repeated 10 times with the mean and standard deviation reported in Table 1 . Due to the better exploration-exploitation tradeoff during selection, WU-UCT out-performs all other parallel algorithms in 12 out of 15 tasks. Pairwise student t-test further show that WU-UCT performs significantly better (adjusted by the Bonferroni method, p-value < 0.0011) than TreeP, LeafP, and RootP in 7, 9, and 7 tasks, respectively. Next, we examine the influence of the number of simulation workers on the speed and the For WU-UCT, the number of expansion workers is fixed to be one.

performance. In Figure 5 , we compare the average episode return as well as time consumption (per step) for 4, 8, and 16 simulation workers. The bar plots indicate that WU-UCT experiences little performance loss with an increasing number of workers, while the baselines exhibit significant performance degradation when heavily parallelized. WU-UCT also achieves the fastest speed compared to the baselines, thanks to the efficient master-worker architecture (Section 3.2). In conclusion, our proposed WU-UCT not only out-performs baseline approaches significantly under the same number of workers but also achieves negligible performance loss with the increasing level of parallelization.

6. RELATED WORK:



MCTS:

Monte Carlo Tree Search is a planning method for optimal decision making in problems with either deterministic (Silver et al., 2016) or stochastic (Schäfer et al., 2008) environments. It has made a profound influence on Artificial Intelligence applications (Browne et al., 2012) , and has even been applied to predict and mimic human behavior (van Opheusden et al., 2016) . Recently, there has been a wide range of work combining MCTS and other learning methods, providing mutual improvements to both methods. For example, Guo et al. (2014) harnesses the power of MCTS to boost the performance of model-free RL approaches; Shen et al. (2018) bridges the gap between MCTS and graph-based search, outperforming RL and knowledge base completion baselines.

Parallel MCTS:

Many approaches have been developed to parallelize MCTS methods, with the objective being two-fold: achieve near-linear speedup under a large number of workers while maintaining the algorithm performance. Popular parallelization approaches of MCTS include leaf parallelization, root parallelization, and tree parallelization (Chaslot et al., 2008) . Leaf parallelization aims at collecting better statistics by assigning multiple workers to query the same node (Cazenave & Jouandeau, 2007) . However, this comes at the cost of wasting diversity of the tree search. Therefore, its performance degrades significantly despite the near-ideal speedup with the help of a client-server network architecture (Kato & Takeuchi, 2010) . In root parallelization, multiple search trees are built and assigned to different workers. Additional work incorporates periodical synchronization of statistics from different trees, which results in better performance in real-world tasks (Bourki et al., 2010) . However, a case study on Go reveals its inferiority with even a small number of workers (Soejima et al., 2010) . On the other hand, tree parallelization uses multiple workers to traverse, perform queries, and update on a shared search tree. It benefits significantly from two techniques. First, a virtual loss is added to avoid querying the same node by different workers (Chaslot et al., 2008) . This has been adopted in various successful applications of MCTS such as Go (Silver et al., 2016) and Dou-di-zhu (Whitehouse et al., 2011) . Additionally, architecture side improvements such as using pipeline (Mirsoleimani et al., 2018b) or lock-free structure (Mirsoleimani et al., 2018a) speedup the algorithm significantly. However, though being able to increase diversity, virtual loss degrades the performance under even four workers (Mirsoleimani et al., 2017; Bourki et al., 2010) . Finally, the idea of counting the unobserved samples to adjust the confidence interval in arm selection also appeared in Zhong et al. (2017) . However, it mainly focuses on parallelizing the multi-armed thresholding bandit problem (Chen et al., 2014) instead of the tree search problem as we do.

7. CONCLUSION:

This paper proposes WU-UCT, a novel parallel MCTS algorithm that addresses the problem of outdated statistics during parallelization by watching the number of unobserved samples. Based on the newly devised statistics, it modifies the UCT node-selection policy in a principled manner, which achieves effective exploration-exploitation tradeoff. Together with our efficiency-oriented system implementation, WU-UCT achieves near-optimal linear speedup with only limited performance loss across a wide range of tasks, including a deployed production system and Atari games. 

SUPPLEMENTARY MATERIAL A ALGORITHM DETAILS FOR WU-UCT:

The pseudo-code of WU-UCT is provided in Algorithm 1. Specifically, it provides the workflow of the master process. When the number of completed updates (t complete ) has not exceeded the maximum simulation step T max (a pre-defined hyperparameter), the main process repeatedly performs a modified rollout that consists of the following steps: selection, expansion, simulation, and backpropagation. The selection and backpropagation steps are performed in the main process, while the two others are assigned to the workers. The backpropagation step is divided into two sub-routines incomplete update (Algorithm 2) and complete update (Algorithm 3). The former is executed before simulation starts, while the latter is called after receiving simulation results. Task index τ is added to help the main process to track different tasks returned from the workers. To maximize efficiency, the master process keeps assigning expansion and simulation tasks until all workers are fully occupied.

Communication overhead of WU-UCT The choice for centralized game-state storage stems from the following observations: (i) size of the game-state is usually small, which allows efficient inter-process transformation, and (ii) each game-state is used at most |A| + 1 times,7 thus is inefficient to store in multiple processes. Although this design may not be ideal for all tasks, it is at least a reasonable choice. During rollouts, game-states generated by any expansion worker may be later used by any other expansion and simulation workers. Therefore, either a per-task transformation or decentralized storage is needed. For the latter case, however, since a game-state will be used at most |A| + 1 times, most workers will not need it, which results in inefficiency of the decentralized storage.

Another possible solution is to store the game-states in shared memory. However, to receive benefit from it, the following conditions should be satisfied: (i) each process can access (read/write) the memory relatively fast even if some collisions may happen, and (ii) the shared memory is big enough to hold all game-states that may be accessed. If the two conditions hold, we may be able to reduce the communication overhead. Since the communication overhead is negligible even with 16 simulation and expansion workers (as shown in Figures 2(b ) and 2(c)), we should consider using more workers to speedup the algorithm.

B ALGORITHM OVERVIEW OF BASELINE APPROACHES:

We give an overview of three baseline parallel UCT algorithms: Leaf Parallelization (LeafP), Tree Parallelization (TreeP) with virtual loss, and Root Parallelization (RootP), with the objective of providing a comprehensive view to the readers. We refer readers interested in the details of these algorithms to Chaslot et al. (2008) . As suggested by their names, LeafP, TreeP, and RootP parallelized different parts of the search tree. Specifically, LeafP (Algorithm 4) parallelizes only the simulation process: whenever a node (state) is selected to query, all workers perform simulations individually to evaluate it. The main process (master) then waits for all workers to complete simulation and return their respective cumulative rewards, which are used to update the traversed nodes' statistics.

TreeP (Algorithm 5) parallelizes the whole tree search algorithm by allowing different workers to access a shared search tree simultaneously. Each worker individually performs the selection, expansion, simulation, and back-propagation steps and update the nodes' statistics. To discourage querying the same node, individual workers subtract a virtual loss r V L (r V L is a hyper-parameter of the algorithm) to each of its traversed node during the selection process, and add it back (+r V L ) during back-propagation. This allows nodes currently being evaluated by some workers to have lower utility scores (4) and will be less likely to be chosen by other workers, which improves the diversity of the node visited by different workers simultaneously. As hinted by its name, RootP (Algorithm 6) parallelizes the root node. Specifically, in an initialization step, all children of the root node is expanded, and different workers are assigned to perform rollouts using the expanded child nodes as the root node of the search tree. The algorithm evenly distribute the workload such that the number of rollouts starting from all child nodes is T max /M , where M is the number of workers. After the job assignment, all workers construct search trees in their own local memories and perform sequential tree search until their assigned tasks are finished. Finally, the main process collects statistics from all workers and return the predicted best action of the state represented by the root node of the search tree.

C EXPERIMENT DETAILS AND SYSTEM DESCRIPTION OF THE JOY CITY TASK:

This section describes the basic rules of the Joy City game (Appendix C.1) as well as details about the deployed user pass-rate prediction system (Appendix C.2).

C.1 DESCRIPTION OF THE JOY CITY GAME:

This section serves as an introduction to the basic rules of the tap game. Figure 7 depicts several screenshots of the game. In the main frame, there is a 9 × 9 grid, where each cell contains an item. We can click cells with connected color regions to eliminate them (i.e., if the cell represented by the purple dot in the first screenshot of Figure 6 (a) is tapped, the region contains blue boxes will be "eliminated"). The remaining cells then collapse to fill in the gaps of exploded ones. To goal is to fulfill all level requirements (goals) within a fixed number of clicks. Figure 6 (a) provides consecutive snapshots for playing level 10 of the game. The goal of this level is depicted on the top, which is 3 "cats" and 24 "balloons". The top-left corner represents the number of remaining steps. Players have to accomplish all given goals before the step runs out. Figure 6 (a) demonstrates successful gameplay, where only 6 steps are used to complete the level. In each of the three left frames, the cell noted by the purple circle is clicked. Immediately, the same-color region marked with a red frame is eliminated. Different goal objects/obstacle objects react differently. For instance, when some cell is exploded beside a it will also explode. Frame two demonstrates the use of props. Tapping regions with connectivity above a certain threshold will provide prop as a bonus.

They have special effects that can help players pass the level faster. Finally, in the last screenshot, all goals are completed and we pass the level. all the levels before its release, which generally takes a long time and is inaccurate. Therefore, it would greatly reduce the game design cycle if we can develop a testing system that is able to provide quick and accurate feedback about the user pass-rates. Figure 7 gives an overview of our deployed user pass-rate prediction system, where WU-UCT is used to mimic average user performance and provide features for predicting the human pass-rate. As we have shown in the main paper, it can achieve significant speedup without significant performance loss,8 allowing the game designer to get the feedback in 20 minutes instead of 12 hours. Specifically, we use WU-UCT with different numbers of rollouts to mimic players with different skill levels, where WU-UCT with 10 rollouts is used to represent average players while the agent with 100 rollouts mimics skillful players. This is verified by the pair-wise sample t-test result provided in Table 2 . With 10 simulations, the WU-UCT agent performs statistically similar (p-value > 5%) to human players, while with 100simulation, the agent performs statistically better (p-value < 5%). Besides, Figure 8 shows that our pass-rate prediction system achieves 8.6% mean absolute error (MAE) on 130 released game-levels, with 93% of them having MAE less than 20%.

The system consists of two working phases, i.e., training and inference. Specifically, training and validation are done on 300 levels that have been released in a test version of the game. In the training phase, the system has access to both the level and players' pass-rate, while only levels are available in the inference phase, and the system needs to give quick and accurate feedback about the (predicted) user pass-rate. In both phases, the levels are first fed into an asynchronous advantage actor-critic (A3C) (Mnih et al., 2016) learner for a base policy π. It is then used by the WU-UCT agent as a prior to select expand action as well as the default policy for simulation. We then use WU-UCT to perform multiple gameplays. The maximum depth and width (maximum number of child nodes for each node) of the search tree is 10 and 5, respectively. The number of simulations is set to 10 and 100 to get AI bots with different skill levels. Six features (three for both the 10-simulation and 100-simulation agent) are extracted from the gameplay results. Specifically, the features are AI's pass-rate, average used step divided by the provided step (the number at the top-left corner in the screenshots in Figure 6 ), and median used step divided by the provided step. During training, the features, as well as the players' pass-rate, is used to learn a linear regressor, while in the inference phase, the regression model is used to predict user pass-rate.

C.3 ADDITIONAL EXPERIMENTAL RESULTS:

In this section, we list the additional experimental results. In Table 3 , we report the specific speedup number for different numbers of expansion worker and simulation workers. 

D EXPERIMENT DETAILS OF THE ATARI GAMES:

This section provides the implementation details of the experiments on Atari games. Specifically, we first describe the training pipeline of the default policy. We then illustrate how the default policy is connected with MCTS algorithm to perform simulation.

Training default policy for MCTS To allow better overall performance, we used the Proximal Policy Gradient (PPO) (Schulman et al., 2017) , one of the state-of-the-art on-policy model-free reinforcement learning (RL) algorithms. We adopted the highest-starred third-party code of PPO on GitHub. The implementation uses the same hyper-parameters with the original paper. The architecture of the policy network is shown in Figure 9 . The original PPO network is trained on 10 million frames for each task. To reduce computation count, we reduce the network size using network Table 5 : Comparison between WU-UCT and three TreeP variants on 12 Atari games. Average episode return (± standard deviation) over 10 runs are reported. The best average scores among listed algorithms are highlighted in boldface. Hyper-parameter r V L refers to the virtual loss added before each simulation starts, and n V L similarly denotes the number of virtual visit counts added before each simulation starts.

Environment WU-UCT TreeP (r V L = n V L = 1) inates other factors (e.g. different language) that may bias the result. Specifically, leaf parallelization is implemented with a master-worker structure: when the main process enters the simulation step, it assigns the task to all workers. When return from all workers is available, the master process performs backpropagation according to these statistics and begin a new rollout.

EQUATION

As suggested by Browne et al. (2012) , tree parallelization is implemented using a decentralized structure, i.e., each worker performs rollouts on a shared search tree. At the selection step, each traversed node is added a fixed virtual loss -r V L to guarantee diversity of the tree search. When performing backpropagation, r V L is added back to the traversed nodes. r V L is chosen from 1.0 and 5.0 for each particular task. In other words, we ran TreeP with r V L = 1.0 and r V L = 5.0 for each task, and report the better result.

Root parallelization is implemented according to Chaslot et al. (2008) . Similar to leaf parallelization, root parallelization consists of sub-processes that do not share information with each other. At the beginning of the tree search process, each sub-process is assigned several actions of the root node to query. They then perform sequential UCT rollouts until reaches a pre-defined maximum number of rollouts. When all sub-processes complete the jobs, statistics from them are gathered by the main process, and are used to choose the best action. 

:

Code is available at https://github.com/liuanji/WU-UCT.

In the context of MCTS, the action space A is assumed to be finite and the transition P is assumed to be deterministic, i.e., the next state st+1 is determined by the current state st and action at.

We assume certain regularity conditions hold so that the cumulative reward ∞ t=0 γ t R(st, at) is always bounded(Sutton & Barto, 2018).

We refer the readers to Chaslot et al. (2008) for more details. The pseudo-code of the three algorithms is given in Appendix B. LeafP: Algorithm 4, TreeP: Algorithm

5, RootP: Algorithm 6.5 We refer it as the tap game below. See Appendix C.1 for more details about the game rules.6 Level-35 is relatively simple, requiring 18 steps for an average player to pass, while Level-58 is relatively difficult and needs more than 50 steps to solve.

In our setup, the game state will only be used for 1 time to start simulation and |A| times to initialize expansion.

Due to the complexity the tap game, model-free RL algorithms such as A3C(Mnih et al., 2016) and PPO(Schulman et al., 2017) fail to achieve satisfactory performance and thus cannot perform an accurate prediction. On the other hand, MCTS could achieve good performance but takes a long time in testing.

The task "Tennis" is not included in the calculation of the average percentile improvement due to the average episode return 0 in RootP.

Figures and Tables:

Figure 1: MCTS and its parallelization. (a) An overview of MCTS. (b)The ideal parallelization: the most up-to-date statistics {V s , N s } (in chromatic color) are assumed to be available to all workers as soon as a simulation begins (unrealistic in practice). (c) The key challenge in parallelizing MCTS: the workers can only access outdated {V s , N s } (in gray-color), leading problems like collapse of exploration. (d) WU-UCT tracks the number of incomplete simulation queries, which is denoted as O s , and modifies the UCT policy in a principled manner to retain effective exploration-exploitation tradeoff. It achieves comparable speedup and performance as the ideal parallelization.

Time consumption in the Atari games.

Figure 2: Diagram of WU-UCT's system architecture and its time consumption. (a) the Green blocks and the task buffers are operated at the master, while the blue blocks are executed by the workers. (b-c) the breakdown of the time consumption on two game benchmarks (Section 5).

Figure 4: WU-UCT speedup and performance. Results are averaged over 10 runs. WU-UCT achieves linear speedup with negligible performance loss (measured in game steps).

Figure 5: Speed and performance test of our WU-UCT along with three baselines on four Atari games. All experiments are repeated three times and the mean and standard deviation (for episode reward only) are reported. For WU-UCT, the number of expansion workers is fixed to be one.

(a) A demonstrated game play in level 10 of the tap game. Purple dots refers to the tapped cell, and red regions indicate directly eliminated cells. A "boss level" Small initial connectivity Various kinds of hard-to-remove obstacles and spiral layout (b) Examples of levels with different rule, difficulty, and layout.

Figure 6: Snapshots of the Tap-elimination game.

Figure6(b) further demonstrates the variety of levels. Specifically, the left-most frame depicts a special "boss level", where the goal is the "defeat" the evil cat. The cat will randomly throw objects to the cells, adding additional randomness. Three other frames illustrate relatively hard levels, which is revealed from their low-connectivity, abundance and complexity of the obstacles, and special layout.

Figure 10: Relative performance between WU-UCT and three baseline approaches on 15 Atari benchmarks. Relative performance is calculated according to the mean episode reward in 3 trials. The average percentile improvement of WU-UCT on TreeP, LeafP, and RootP is 49%, 104%, and 82%, respectively. 10

node s, environment emulator E, prior policy π a ← random action drawn from π(• | s) while s has expanded a do a ← random action drawn from π(• | s) end while s , r, d ← performing a in s according to E (d: terminal signal) s ← a new node constructed according to s Store reward signal r and termination indicator d in s Link s as the child of s by the node corresponding to a Algorithm 8 back propagation input: node s, cumulative reward r while s = null do Ns ← Ns + 1 Retrieve the reward r in the current node s (which is collected during its expansion) r ← r + γ r Vs ← Ns-1 Ns Vs + 1 Ns r s ← PR(s) // PR(s) denotes the parent node of s end while

The performance on 15 Atari games. Average episode return (± standard deviation) over 10 trials are reported. The best average scores among parallel algorithms are highlighted in boldface. The mark * indicates that WU-UCT achieves statistically better performance (p-value < 0.0011 in paired t-test) than TreeP (no mark if both methods perform statistically similar). Similarly, the marks † and ‡ mean that WU-UCT performs statistically better than LeafP and RootP, respectively.

Table content: <table><tr><td>Environment</td><td>WU-UCT</td><td>TreeP</td><td>LeafP</td><td>RootP</td><td>PPO</td><td>UCT</td></tr><tr><td>Alien</td><td>5938±1839</td><td>4200±1086</td><td>4280±1016</td><td>5206±282</td><td>1850</td><td>6820</td></tr><tr><td>Boxing</td><td>100±0* † ‡</td><td>99±0</td><td>95±4</td><td>98±1</td><td>94</td><td>100</td></tr><tr><td>Breakout</td><td>408±21 † ‡</td><td>390±33</td><td>331±45</td><td>281±27</td><td>274</td><td>462</td></tr><tr><td>Centipede</td><td colspan="4">1163034±403910* † ‡ 439433±207601 162333±69575 184265±104405</td><td colspan="2">4386 652810</td></tr><tr><td>Freeway</td><td>32±0</td><td>32±0</td><td>31±1</td><td>32±0</td><td>32</td><td>32</td></tr><tr><td>Gravitar</td><td>5060±568 †</td><td>4880±1162</td><td>3385±155</td><td>4160±1811</td><td>737</td><td>4900</td></tr><tr><td>MsPacman</td><td>19804±2232* † ‡</td><td>14000±2807</td><td>5378±685</td><td>7156±583</td><td>2096</td><td>23021</td></tr><tr><td>NameThisGame</td><td>29991±1608*</td><td>23326±2585</td><td>25390±3659</td><td>27440±9533</td><td>6254</td><td>38455</td></tr><tr><td>RoadRunner</td><td>46720±1359* † ‡</td><td>24680±3316</td><td>25452±2977</td><td>38300±1191</td><td colspan="2">25076 52300</td></tr><tr><td>Robotank</td><td>101±19</td><td>86±13</td><td>80±11</td><td>78±13</td><td>5</td><td>82</td></tr><tr><td>Qbert</td><td>13992±5596</td><td>14620±5738</td><td>11655±5373</td><td>9465±3196</td><td colspan="2">14293 17250</td></tr><tr><td>SpaceInvaders</td><td>3393±292</td><td>2651±828</td><td>2435±1159</td><td>2543±809</td><td>942</td><td>3535</td></tr><tr><td>Tennis</td><td>4±1* † ‡</td><td>-1±0</td><td>-1±0</td><td>0±1</td><td>-14</td><td>5</td></tr><tr><td>TimePilot</td><td>55130±12474* †</td><td>32600±2165</td><td>38075±2307</td><td>45100±7421</td><td>4342</td><td>52600</td></tr><tr><td>Zaxxon</td><td>39085±6838 † ‡</td><td>39579±3942 † ‡</td><td>12300±821</td><td>13380±769</td><td>5008</td><td>46800</td></tr></table>

Daniel Whitehouse, Edward J Powley, and Peter I Cowling. Determinization and information set monte carlo tree search for the card game dou di zhu. In 2011 IEEE Conference on Computational Intelligence and Games (CIG'11), pp. 87-94. IEEE, 2011.

Table content: <table><tr><td>Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement</td></tr><tr><td>learning. Machine learning, 8(3-4):229-256, 1992.</td></tr><tr><td>Jie Zhong, Yijun Huang, and Ji Liu. Asynchronous parallel empirical variance guided algorithms</td></tr><tr><td>for the thresholding bandit problem. arXiv preprint arXiv:1704.04567, 2017.</td></tr></table>

: environment emulator E, root tree node sroot, maximum simulation step Tmax, maximum simulation depth dmax, number of expansion workers Nexp, and number of simulation workers Nsim Initialize: expansion worker pool Wexp, simulation worker pool Wsim, game-state buffer B, t ← 0, and t complete ← 0 while t complete < Tmax doTraverse the tree top down from root node sroot following (4) until (i) its depth greater than dmax, (ii) it is a leaf node, or (iii) it is a node that has not been fully expanded and random()<0.5 if expansion is required then s ← shallow copy of the current node Assign expansion task (t, s) to pool Wexp // t is the task index else assign simulation task (t, s) to pool Wsim if episode not terminated Call incomplete update(s); if episode terminated, call complete update(t, s, 0.0) end if if Wexp fully occupied then Wait for a expansion task with return: (task index τ , game state s, reward r, terminal signal d, task index τ ); expand the tree according to s, τ , r, and d; assign simulation task (τ, s) to pool Wsim Call incomplete update(t, s) else continue if Wsim fully occupied then Wait for a simulation task with return: (task index τ , node s, cumulative reward r) Call complete update(τ, s, r); t complete ← t complete + 1

Table content: <table><tr><td>Algorithm 1 WU-UCT</td><td/><td/></tr><tr><td>else continue</td><td/><td/></tr><tr><td>t ← t + 1</td><td/><td/></tr><tr><td>end while</td><td/><td/></tr><tr><td>Algorithm 2 incomplete update</td><td>Algorithm 3 complete update</td><td/></tr><tr><td>input: node s</td><td>input: task index t, node s, reward</td><td>r</td></tr><tr><td>while n = null do</td><td>while n = null do</td><td/></tr><tr><td>Os ← Os + 1</td><td>Ns ← Ns + 1; Os ← Os -1</td><td/></tr><tr><td>s ← PR(s) // PR(s) denotes the parent</td><td colspan="2">Retrieve reward r according to task index t</td></tr><tr><td>node of s end while</td><td colspan="2">r ← r + γ r; Vs ← Ns-1 Ns Vs + 1 Ns s ← PR(s) // PR(s) denotes the parent r</td></tr><tr><td/><td>node of s</td><td/></tr><tr><td/><td>end while</td><td/></tr></table>

Pair-wise sample t-test of pass-rate across 130 levels between two AI bots (different number of MCTS rollouts) and the players. "Avg. diff" means the average difference between the pass-rate of the bot and that of the human players. p-value measures the likelihood that two sets of paired samples are statistically similar (i.e. larger means similar). Effect size the strength of the difference (larger means greater difference).

Table content: <table><tr><td/><td/><td/><td/><td/><td>MAE: 8.6%</td><td>93%</td></tr><tr><td/><td/><td/><td/><td/><td/><td>84%</td></tr><tr><td/><td/><td/><td/><td/><td/><td>67%</td></tr><tr><td>AI bot</td><td colspan="4"># rollouts Avg. diff. Effect size p-value</td><td/></tr><tr><td>WU-UCT</td><td>10</td><td>-1.54</td><td>0.07</td><td>0.4120</td><td/></tr><tr><td>WU-UCT</td><td>100</td><td>22.18</td><td>0.88</td><td>0.0000</td><td colspan="2">Figure 8: Distribution of the pass-rate</td></tr><tr><td/><td/><td/><td/><td/><td colspan="2">prediction error on 130 game-levels.</td></tr></table>

Speedup on two levels of the tap game. M e is the number of expansion workers and M s is the number of simulation workers.

Table content: <table><tr><td>Lv.</td><td colspan="2">Level 35</td><td colspan="2">Level 58</td></tr><tr><td colspan="2">Me Ms 1 2 4</td><td>8</td><td>16 1 2 4</td><td>8</td><td>16</td></tr><tr><td>1</td><td colspan="5">1.0 2.0 2.8 3.6 4.5 1.0 1.8 4.1 4.8 5.1</td></tr><tr><td>2</td><td colspan="5">1.4 2.2 4.1 5.7 6.3 1.1 3.1 5.3 6.7 8.4</td></tr><tr><td>4</td><td colspan="5">1.7 2.5 4.5 8.4 8.8 1.1 3.4 6.1 10.1 12.8</td></tr><tr><td>8</td><td colspan="5">2.3 3.0 5.1 10.1 12.8 1.2 3.6 6.7 13.2 16.1</td></tr><tr><td colspan="6">16 2.9 3.7 5.7 11.2 15.5 1.2 3.8 7.6 16.1 20.9</td></tr></table>

Performance of the original PPO policy and our distilled policy on 15 Atari games.

Table content: <table><tr><td>Environment</td><td colspan="2">Origin PPO policy Distilled policy</td></tr><tr><td>Alien</td><td>1850</td><td>850</td></tr><tr><td>Boxing</td><td>94</td><td>7</td></tr><tr><td>Breakout</td><td>274</td><td>191</td></tr><tr><td>Centipede</td><td>4386</td><td>1701</td></tr><tr><td>Freeway</td><td>32</td><td>32</td></tr><tr><td>Gravitar</td><td>737</td><td>600</td></tr><tr><td>MsPacman</td><td>2096</td><td>1860</td></tr><tr><td>NameThisGame</td><td>6254</td><td>6354</td></tr><tr><td>RoadRunner</td><td>25076</td><td>26600</td></tr><tr><td>Robotank</td><td>5</td><td>13</td></tr><tr><td>Qbert</td><td>14293</td><td>12725</td></tr><tr><td>SpaceInvaders</td><td>942</td><td>1015</td></tr><tr><td>Tennis</td><td>-14</td><td>-10</td></tr><tr><td>TimePilot</td><td>4342</td><td>4400</td></tr><tr><td>Zaxxon</td><td>5008</td><td>3504</td></tr></table>

Peer review (iclr2020):
This paper introduces a novel approach to parallelizing Monte Carlo Tree Search which achieves speedups roughly linear in the number of parallel workers while avoiding significant loss in performance. The key idea to the approach is to keep additional statistics about the number of on-going simulations from each of the nodes in the tree. The approach is evaluated in terms of speed and performance on the Atari benchmark and in a user pass-rate prediction task in a mobile game. I recommend that this paper be accepted. The approach is well motivated and clearly explained, and is supported by the experimental results. The experiments are reasonably thorough and demonstrate the claims made in the paper. The paper itself is very well-written, and all-around felt very polished. Overall I am enthusiastic about the paper and have only a few concerns, detailed below. - I suggest doing more runs of the Atari experiment. Three runs of the experiment does not seem large enough to make valid claims about statistical significance. This is especially concerning because claims of statistical significance are made via t-testing, which assumes that the data is normally distributed. Three runs is simply too few to be making conclusions about statistical significance using t-testing. I think that this is a fair request to make and could reasonably be done before the camera-ready deadline, if the paper is accepted. - The experiments in Atari compare against a model-free Reinforcement Learning baseline, PPO. Was there a set clock time that all methods had to adhere to? Or alternatively, was it verified that PPO and the MCTS methods are afforded approximately equal computation time? If not, it seems like the MCTS methods could have an unfair advantage against PPO, especially if they are allowed to take as long as necessary to complete their rollouts. This computational bias could potentially be remedied by allowing PPO to use sufficiently complex function approximators, or by setting the number of simulations used by the MCTS methods such that their computation time is roughly equal to that of PPO. - I would be careful about stating that PPO is a state-of-the-art baseline. State-of-the-art is a big claim, and I*m not quite sure that it*s true for PPO. PPO*s performance is typically only compared to other policy-based RL methods; it*s hard to say that it*s a state-of-the-art method when there*s a lack of published work comparing it against the well-known value-based approaches, like Rainbow. I suggest softening the language there unless you*re confident that PPO truly is considered a state-of-the-art baseline.