Speculative Monte-Carlo Tree Search
Authors: Scott Cheng
Mahmut Kandemir
Ding-Yong Hong
Venue: NeurIPS 2024 poster (2024)
Keywords: Monte-Carlo Tree Search
MCTS
Primary area: reinforcement_learning

Abstract: Monte-Carlo tree search (MCTS) is an influential sequential decision-making algorithm notably employed in AlphaZero. Despite its success, the primary challenge in AlphaZero training lies in its prolonged time-to-solution due to the high latency imposed by the sequential MCTS process. To address this challenge, this paper proposes and evaluates an inter-decision parallelization strategy called speculative MCTS, a new type of parallelism in AlphaZero which implements speculative execution. This approach allows for the parallel execution of future moves before the current MCTS computations are completed, thus reducing the latency. Additionally, we analyze factors contributing to the overall speedup by studying the synergistic effects of speculation and neural network caching in MCTS. We also provide an analytical model that can be used to evaluate the potential of different speculation strategies before they are implemented and deployed. Our empirical findings indicate that the proposed speculative MCTS can reduce training latency by 5.81$\times$ in 9x9 Go games. Moreover, our study shows that speculative execution can enhance the NN cache hit rate by 26\% during midgame. Overall, our end-to-end evaluation indicates 1.91$\times$ speedup in 19x19 Go training time, compared to the state-of-the-art KataGo program.

Speculative Monte-Carlo Tree Search
Scott Cheng
Mahmut Taylan Kandemir
Ding- Yong Hong
The Pennsylvania State University, USA
Institute of Information Science, Academia Sinica, Taiwan
(ppp5394,,tk2220ppl edu dyhong@iis dybong@lis.simica..eu. sinica.edi.......aa..a.....m.
Abstract
Monte-Carlo tree search (MCTS) is influential sequential decision-making algo- rithm notably employed in AlphaZero. Despite its success, the primary challenge in AlphaZero training lies in its prolonged time-to-solution due the high latency imposed by the sequential MCTS process. To address this challenge, this paper proposes and evaluates inter-decision parallelization strategy called speculative MCTS, a new type of parallelism in AlphaZero which implements speculative execution. This approach allows for the parallel execution of future moves before the current MCTS computations are completed, thus reducing the latency. Addi- tionally, we analyze factors contributing the overall speedup by studying the synergistic effects of speculation and neural network caching in MCTS. We also provide an analytical model that can used to evaluate the potential of different speculation strategies before they are implemented and deployed. Our empirical findings indicate that the proposed speculative MCTS can reduce training latency by 5.81 x in 9x9 Go games. Moreover, our study shows that speculative execution can enhance the NN cache hit rate by 26% during midgame. Overall, our end-to- end evaluation indicates 1.91 x speedup in 19x19 Go training time, compared to the state-of-the-art KataGo program.
Introduction
Monte-Carke tree search (MCTS) [1, 2] is sequential decision-making algorithm that has achieved breakthroughs in various fields, such as chemistry [3, 4], medicine [5, 6], and many others. Most notably, AlphaZero [7] leverages MCTS to reach superhuman-level performance "board games" such as Go, Chess, and Shogi. AlphaZero training consists of two phases: self-play and neural network (NN) training, as depicted in Figure 1. During the self-play stage, AlphaZero generates game records by playing against itself, with each move determined by MCTS simulations and NN inferences. After the self-play phase, the NN is trained on these self-play game records. By alternating between these two phases, AlphaZero continuously enhances its strategies through MCTS.
Despite AlphaZero's 's remarkable Decision-making capabilities, the training is considerably time- consuming, and several factors contribute to long training times. First, AlphaZero training requires lots of training data per parameter, which is even higher than the well-known resource-come conouue-consuming large language model (LLM) training.' Second, the MCTS algorithm involves sequential decision- making, where each game move depends on the outcome of the previous move. This sequential nature introduces significant latency. Third, the MCTS simulations evaluate the values of game positions with neural network (NN) inferences, which also contributes the prolonged training times. In this work, aim to reduce the training time by exploiting speculation-basee pipeline
'AlphaZero's training data per parameter can be estimated by (21M games 150 positions/game) / (24M parameters) 131 positions/parameter. comparison, LLM's 's training sample per parameter is about 20 according to Chinchilla scaling law [8].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Game N
Inter-game parallellism
Game
compute resource
0
Move 400
Latency = 320,000 NN inferences (800 simulations/move)
Self-play
Intra-decision parallelism
NN Training
.. wa.............................. w............................... Intra-game parallelism
latency
Inter-ne parallelism
Figure 1: AlphaZero training consists of self-play and NN training, where self-play is highly resource- consuming. We categorized the intrinsic "parallelism" in the self-play phase into three categories (a) inter-game, which is embarrassingly parallel, (b) intra-decision, such as parallel search algorithms, and (c) inter-decision, which enables parallel execution for moves within a single game. Our proposed work aims to address the problem of lack of decri-e parallelism.
parallelism in AlphaZero training. To this end, we categorize the self-play process into three dimensions (shown in Figure 1): (a) inter-game, (b) intra-decision, and (c) inter-decision. Most prior works [7, 9] have focused on parallelizing "inter-game" training, as it is embarrassinglyy-araad and easy implement. Additionally, several "parallel MCTS" strategies [10, 11] have been proposed in the literature to explore and exploit intra-decision parallelism. In contrast, to the best of our knowledge, the challenge of "inter-decision" parallelism, which involves parallelizing the sequence of decisions within individual games, has no! been addressed by prior art. As a result, even with sufficient inter- inter-game parallelism to collect multiple game records concurrently and efficient parallel MCTS algorithms in place, the training latency remains constrained by the sequential inter-decision MCTS self-play, thus limiting the potential benefits from the increasingly powerful segh-performanc computing (HPC) resources and systems.
Motivated by the observations above, in this work, we propose and experimentally evaluate specu- lative MCTS to enable "inter-decision" parallelism. Since MCTS an Anytime Algorithm" [12], it allows us obtain "partial" simulation results (i.e., values and policies) any point during its execution, and the simulation results keep refining as MCTS continues to execute. For example, we have observed that, more than 50% of the search results do not change after full MCTS and only 20% of the search results would change after performing half of the MCTS simulations. Leveraging these insights, we propose to utilize the partial simulation results from the current move to predict the subsequent moves to play. Doing so would allow us to start executing the "future moves" before the computation of the "current move" is completed and run the MCTS computation of consecutive moves in "pipelined fashion", thus reducing the overall training latency. Additionally, to address the NN inference latency in MCTS simulations, we integrate an "NN caching" mechanism accelerate the retrieval of inference results. Interestingly, even for the cases where our speculation mispredicts, the NN cached results from the discarded moves can still be utilized for the current MCTS move to reduce the latency.
In summary, this paper makes the following main contributions:
We design and implement "speculative parallclization" strategy based on our insights into MCTS's 's anytime algorithm characteristies. We also conduct detailed analysis of the NN cache to explore the synergy between caching and speculation. Furthermore, we conduct extensive performance evaluations by varying the number of speculative "look-ahead" steps in Go and NoGo games across different NN sizes.
We propose an "analytical model" that allows us estimate the performance gain and compute resource usage beforehand, which, in general, supports various designs in inter- decision parallelism. Our empirical evaluations suggest that the proposed analytical model
An algorithm capable of delivering "valid" result, if it is halted before completion.

---

can accurately estimate the actual latency, with an average RMSE (root mean square error) of 22.2, across four different settings.
Our evaluation results indicate that the proposed speculative MCTS can speed up training latency up to 5.8x in 9x9 Go games. Moreover, we can achieve around 26% higher NN cache hit ratio during mid-game Finally, our end-to-end evaluations demonstrate around 1.91 x speedup, compared to the state-of-the-art KataGo program.
2 Background
2.1 Monte-Carlo Tree Search
Monte Carlo Tree Search (MCTS) [1, 2] is a widely used best-first search algorithm and has demon- strated extraordinary performance when combined with neural networks in AlphaZero-like algo- rithms [7. 13J. Notably, KataGo [9] is the state-of-the-art, open-source computer Go program capable of defeating top-level human players, In board games, each node in the search tree represents board position. During each simulation, MCTS selects the most promising leaf node the search tree, and the selected node is then expanded and evaluated. During the evaluation, the NN takes the input features extracted from the current board position as image inputs and outputs a policy and a value. Based on the evaluated value, MCTS updates the winning probability estimation for each node on the selection path. Meanwhile, the evaluated policy is used in the next selection phase to guide the search process towards more promising moves. By conducting the simulation repeatedly, MCTS progressively refines its estimate of the optimal decision.
2.2 Motivation
As introduced earlier, the sequential decision- making process in MCTS leads to high training latencies, and the lack of parallelism bounds the training throughput even when more compute resources are available. In particular, inter-game parallelism, as shown in Figure 1, is mainly employed in scale-out training. On the other hand, intra-decision parallelism an example of which is parallel MCTS [10] - provides less parallelism opportunities since the parallelism would reduce the strength of MCTS results der the same compute resource bound [1 14]. These observations motivate us explore oppor- tunities for exploiting inter-decision parallelism to scale the whole training process beyond what can be achieved by state-of-the-ar methods.
100%
Prediction accuracy
80%
40%
20%
0%
0
400
800
1200
1600
Simulation count
Figure 2: Prediction accuracy when using fewer simulation counts to predict the (600-simulation's search results.
To show that partial MCTS searches can reasonably predict the full MCTS results, conduct an initial experiment using KataGo [9]. The experiment measures prediction accuracy by calculating the fraction of correct predictions made with fewer simulations relative to the complete MCTS with 1600 simulations.? 3 As depicted in Figure 2, a partial-search with 800 simulations can achieve an 83.8% prediction accuracy with respect to the full-search. which means that 83.8% of the search results remain unchanged after another 800 simulations. As expected, using fewer simulations leads lower prediction accuracy. These results provide insights indicating that, more simulations are executed, more confidence we have in the current best candidate. However, several critical board positions could still alter the search outcome in the last few simulations. Consequently, we cannor simply speed up MCTS by using fewer simulation counts, as those 16.2% % mispredicted search results (from 83.8% to 100%) are vital for improving strength from the 800 to 1600 simulations.
3 Related Works
In this section, we discuss the prior works that are most relevant to our paper.
Similar evaluations and observations can be done with different MCTS simulations (see also Appendix A.I).

---

Parallel MCTS and other parallel decision tree search algorithms, in broader sense, belong to the intra-decision parallelism. The parallelization can be implemented in root-level, tree-level, and leaf-level [10]. Several techniques have been proposed to enhance parallel MCTS performance, such as lock-free data structures [15] and virtual loss [10]. Prior study [16] proposed to combine multiple MCTS parallelism, while further study [11, 14] showed that leaf-level parallelism could reduce the performance even only with four workers. Furthermore, prior work [17] proposed to modify the UCT formula to make MCTS more suitable for parallelization. Overall, these previous approaches to "intra-decision" parallelism can potentially be integrated with our "inter-decision" parallelism.
Speculative parallelism has also been applied to the A algorithm [18] where nodes are speculatively expanded during the search process. Additionally, prior work [19] speculatively executes MCTS simulation by predicting the next move using smaller NN. In contrast, our work leverages the anytime algorithm characteristic of MCTS to predict future moves. We focus on addressing the inherent sequential nature of multiple MCTS gameplays that belong to the inter-decision parallelism. On the other hand, speculative parallelism has been explored in non-MCTS contexts and designed at various levels, such as hardware prefetching, thread-level speculation, and compiler loop speculation [20, 21].
4 Methodology
In this section, we first present the details of our proposed speculative MCTS approach. Then, we analyze the speculative execution using our analytical models in Section 4.2. Finally, we discuss the synergy effects when combining NN caching with speculative MCTS in Section 4.3.
4.1
Speculative MCTS
(a) Original (0-step look-ahead)
Move 1/2
1/2
Move
Move 3
1/2
1/2
(b) Speculation (1-step look-ahead)
Move prediction
Case 1
Move 1
1/2
1/2
Success speculation
Move 2
1/2
1/2
Failed speculation
Move
1/2
1/2
Move 1/2
1/2
Case
Move
1/2
Move 3
1/2
1/2
Time
Figure 3: (a) Original execution where each move proceeds sequentially, and (b) Speculation pipeline where the next move is speculatively executed in parallel based on the prediction. Each 1/2 block indicates half of the MCTS computation for move.
MCTS allows to obtain partial search results at any point during execution, as it continually updates the search results throughout the process. Hence, we can divide the tree search process into stages, with each stage handling I/n of the total computation. Figure 3 illustrates dividing the tree search process into two stages. this scenario, when the total number of MCTS simulations for a move is, say, 800, each stage will have 400 simulations. The state-of-the-art MCTS (Figure (a)), including parallel MCTS [10], proceeds to the next move only after the current tree search is completed.
example of
On the other hand, in our speculative MCTS, we leverage the partial search results from the current pipeline stage to predict the next move. In this example, we predict the final outcome of an 800- simulation MCTS using the results from the first 400 simulations. Based on this prediction, we then start the tree search of the next move. Therefore, the next move is speculatively executed in parallel with the ongoing tree search of the current move, as depicted in Figure 3(b). Case in Figure 3(b shows a "successful" speculation where the pipeline execution can continue to proceed, whereas Case illustrates "failed" speculation, which needs to flush the pipeline and restart the tree search for the next move (Move 2).

---

Move 1/n
1/n
1/n
Case
Move
1/n
1/n
1/n
prediction
Success speculation
Move
1/n
Failed speculation
Move
1/n
1/n
Case 2
Move
1/n
1/n
1/n
1/n
1/n
Move
1/n
Time
Figure 4: (n 1) st-t look-ahead speculation contains n pipeline stages. Case shows a successful prediction pipeline, whereas Case illustrates a failed speculation, leading pipeline flush.
In general, we can speculate (n step ahead from move by partitioning the tree search process into pipeline stages, shown in Figure 4. We define O-step look-ahead speculation to be the same as the original execution pipeline, namely, with no speculation occurring when n 1. In Case 1 of Figure 4, successful speculation reduces the latency ! of the original move while maintaining the same compute resources. contrast, in Case 2, a failed speculation results in the same latency as the original move, with increased compute resource demand to n+1 due to the pipeline flush. 4 Moreover, one could potentially design various speculation strategies to reduce the pipeline flush cost, and we will discuss this further in the following section and in Appendix A.2.
4.2 Speculation Analysis
In this section, we present an "analytical ap- proach" to estimate the speedup of end-to-end latency and compute resources. As discussed earlier, we have obtained the expected latency required for Case 1 and Case 2 in Figure 4. By knowing the fraction of time the pipeline spends in each case, we can estimate the end-to-end expected speedup as a "weighted average" over the expected latency for each case. Hence, first model the speculation pipeline (Figure 3(b)) into finite state machine (Figure 5), and then solve for the "steady-state" probability distribution of the pipeline. Since each pipeline case only depends the previous one, the finite state machine satisfies the Markov Property. In general, given a finite state machine with transition probabilities, we solve for the steady-state probability distribution of the finite Markov chain using the following linear equations:
1 1-p P
P
S
F DD1-
1011 1-P
Figure 5: The finite state machine corresponds to the speculation pipeline in Figure 3(b), containing two states: successful (S) and failed (F) specula- tion, and the prediction accuracy
qM ||||| =
where M is the given "transition matrix" and the vector q represents "steady-state probability distribution".. After solving the equation, we can calculate the expected end-to-end latency by the inner product of q and column vector L that contains the expected latency of each pipeline case. Then, the end-to-end latency is given by qL. Similarly, the compute resource required for each pipeline is defined R, and the total amount of required compute resources is qR.
Taking Figure as an example, as previously discussed, we can write down the latency vector as
L = - 1) and the resource vector as R (1, (-=") Based the finite state machine in Figure 5, we can determine the expected end-to-end latency and compute resources for the n-step
IIn this context, compute resource the of pipeline flush (orange stages in Case 2) and recomputa- tion cost
(x-11 (x++1)
5

---

look-ahead speculation and arrive at the following results:
Pn = Pr (make success (n 1)-ttep look-ahead speculation)
(2)
1 (1 pm)
Bllatency] = Pn 71
(3)
n +
B [[resource] = Pn + (1 - P..)
2
to be emphasized that our analysis general and applicable to different speculation- pipelining strategies (see also Appendix A.2), thus enabling us to provision the various pipeline designs beforehand, based on the insights from our analysis.
4.3 Synergizing Speculation and Neural Network Caching
Cache
Current Move:
Time
Next Move:
Figure 6: In speculative MCTS, parallel moves share cached NN inference results, which accelerate the execution mutually.
The NN inference results at each tree node can typically be cached in a hash table, with the NN input being the hash key. The costly NN inference can thus be alleviated during tree node evaluation upon a cache hit. This caching technique also applies to our speculative MCTS. In the original MCTS, different moves access the NN cache in sequence according to the gameplay order. As a result, the current move can only benefit from the inference results cached by previous moves and the current move itself. Unlike the original MCTS, speculative MCTS allows both the current and the next moves to simultaneously access the NN cache. Thus, regardless of which move performs the node inference first, the subsequent tree search can benefit from the cached NN results. For example, the dark green nodes in Figure 6 represent the shared positions between the current and next moves, which can potentially accelerate the execution mutually via the shared NN cache. In essence, both the current and speculated moves can take advantage of the NN inference results, and thus, the cache hit rate is expected to increase as the speculative look-ahead step increases. Furthermore, even if the speculated moves mispredicted and subsequently flushed, their NN inference results can still serve future moves and are likely to contribute to the hits in the main sequence of MCTS. Therefore, we expect the synergy between "speculation" and "caching" to provide more speedups than employing each technique individually.
Moreover, based on the introduced analysis, we can estimate the latency as follows:
E llatency w/S] = Ellatency w/o $] x (1 hr) + fo:
(5)
where hr denotes the NN cache hit rate, to is the time to access the hash table, which is significantly shorter than performing an NN inference, and E llatency w/o $] can be obtained from Equation 3.
5 Evaluations
In this section, we first provide our experimental setting in Section 5.1. Then, we evaluate the training latency in Section 5.2. and study the NN cache hit rate in Section 5.3, to provide insights into our
'To avoid the GHI problem, we only allow two identical board positions to share the same NN cache when they have the same history. particularly for the Go game [22, 23j.

---

observed speedups. Finally, we evaluate the performance of end-to-end training and compare our proposed method against state-of-the- -frt----ttttttttt----ee------ upproaches in Section 5.4.
5.1 Experimental Setting
evaluate our speculative MCTS approach on 9x9 NoGo [24], 9x9 Go, and Go games using different NN sizes. The NN models consist of ResNet blocks [25], denoted bXcY, where X represents the number blocks and is the number of channels per block. The input features for NoGo and Go games follow the configurations established in prior works [26, 27J. Additionally, all models are trained from randomly initialized weights, and the self self-play simulation is 800.
Our experiments are conducted on cluster that consists of 8 NVIDIA V100 GPUs per node. We train four NN models, (9x9 go, b5c64), (9x9 go, b10c128), (9x9 nogo, b5c64) and (19x19 go, b6c96), and each model is trained for 1400 V100-hours. For the latency evaluation in Sections 5.2 and 5.3, we run the experiments on one GPU and measure the latency by averaging moves. For end-to-end evaluation in Section 5.4, we use 5 GPU nodes for both two runs. Moreover, we perform strength evaluation against the state-of-the-art method, using an extra 280 V100-hours. In all our evaluations, the batch sizes for training and inference set to 1024 and 24, respectively.
results over 100,000 game
5.2
Evaluation of Training Latency
D[w/o S]
w/o
E[w/S]
w/S
E[w/o $]
w/o
B[w/S]
w/S
4
4
Speeduup
Speedup
3
3
2
2
3
$
2
5
Speculative look-ahead steps
Speculative look-ahead steps
(a) (9x9 go, b5c64)
(b) (9x9 go, b10c128)
E| [ww/ $]
w/o
F[w/S]
w/S
H[w/o S]
w/o
E[w/S]
w/S
4
3.0
3
Speedup
Speedup
2
0.0
2
4
Speculative look-ahead steps
Speculative look-ahead steps
(c) (9x9 nogo, h5c64)
(d) (19x19 go, b6c96)
Figure 7: Speedup for speculative MCTS across various speculative look-ahead steps, with each sub- figure representing different (game, NN size) setting. OOM denotes "out-of-memory" evaluation.
This section evaluates the per-iteration self-play latency with different configurations of speculation look-ahead steps and NN caching. Figure 7 shows the speedup of our speculative MCTS compared to the baseline (original) MCTS, which is executed withous speculation (i.e., 0 look-ahead step). Based on analysis described in Section 4.2, the light blue and orange bars indicate the expected speedup

---

without NN cache (denoted as E[w/o $1) and with NN cache (denoted as E[w/S]), respectively, whereas the dark blue and orange bars show evaluated speedups without and with NN cache, respectively.
For the performance without the NN cache (blue bars), the results indicate that all speculation cases faster than the baseline. Among the results, the speculation with four look-ahead steps achieves a speedup of 2.37 over the baseline in (9x9 go, b b10c128), We also observe that, in general, performance improves when the speculative look-ahead step increased, but the speedup does not improve significantly. The reason is that, as the speculative look-ahead step increases, we predict the next move with MCTS partial results of fewer simulations. As a result, the accuracy of the speculative prediction might be reduced, leading to less speedup improvement. For the comparison of the estimated speedup and the evaluated speedup. Equation gives a close estimation of 22.2 RMSE (root mean square error) across all four settings.
For the performance with NN cache (orange bars), the speedup increases as the speculative look-ahead step increases, and we achieve a speedup of up to 5.81 with five speculative look-ahead steps over the baseline MCTS in (9x9 go, b5c64). Furthermore, we observe that the values of evaluated speedups are greater than those of the estimated speedups among all four settings. This is because our analytical modeling (Equation 5) does not take the synergistic effects into account. Therefore, combining speculation and NN cache would, in general, lead to a better speedup. Overall, the speculation with the NN cache offers least 1.25 speedup over the baseline (0 loek-ahead step) with the NN cache, and achieves 2.1 times improvement, on average, compared to the speculation without the cache.
5.3
Evaluation of Cache Hit Rate
60.0%
100%
Cache hit rate
58.0%
56.3%
56.8%
57.1%
Cache hit rate
80%
56.0%
55.55%
60%
54.2%
54.0%
40%
52.0%
51.3%
20%
Specalative look-aleed Steps
50.0%
0%
3
4
0
16
24
32
40
48
56
64
Speculative look-ahead steps
Move
Figure 8: NN cache hit rate across different
Figure NN cache hit rate for each move across various speculative look-ahead steps.
speculative look-ahead steps.
In this section, we dissect the speculative MCTS speedup in (nogo, b5c64) by examining the contribution of the NN cache hit rate to the overall performance. Figure 8 indicates that, as the speculative look-ahead step is increased, the NN cache hit rate also increases, aligning with our discussion in Section 4.3. To further investigate the source of this improvement, we measure the cache hit rates of each move during self-play. The result in Figure reveals that the cache hit rates are high at the beginning and the end of the game, but drop in the middle of the game. In general, the NN cache hits come from two sources: (1) intra-game hits, which leverage temporal locality as moves within a game often overlap in multiple MCTS's tree nodes, and (2) inter-game hits, which are akin to caching an opening book for the game and the concept is similar to the "joseki" in Go. Hence, result matches our intuition that common opening board positions are shared across different games while many endgame moves recur in tree searches within the same game, thus leading to high cache board positions compared to the
hit rates. During the middle of the game, MCTS explores opening and endgame, and thus, move decisions are more divergent, leading to lower cache hit rates. In this case, our speculative MCTS can provide more intra- aatra-game hit opportunities, which improve the cache hit rates. This can be observed at move 7 in Figure 9, where the cache hit rate increased from 36% with speculation 62% with 5-step ahead speculation- an improvement of 26%.
5.4 Evaluation of End-to-End Training
In this section, we evaluate the performance of our speculative MCTS against the state-of-the-ar method. The KataGo [9] model and its training are based on settings in the public repository [28].
8

---

Ours (1-step)
Ours (0-step)
KataGo
7000
6000
rating
5000
4000
3000
2000
1000
0
0
50
100
150
200
250
300
350
Walltime (min)
Figure 10: End-to-end training evaluation against the state-of-the-an method, KataGo.
Since our training settings described in Section 5.1 are different from those of prior works, we extrapolated their training time. Furthermore, for each model iteration, play 400 games against KataGo's 's model to evaluate the Elo rating [29], establishing a 95% confidence interval for the win rate within +.5%.
Figure 10 shows the comparison result. The results show that the training performance of MCTS without speculation (0-step) aligns with the state-of-the-art Go program, KataGo. Morcover, speculative MCTS with 1-step look-ahead speculation achieves 1.91 speedup over KataGo when reaching 7,000 Elo rating. This performance also aligns with the per-iteration evaluation result in Figure 7d. Though we only evaluated our method with only 1 1-step look-ahead speculation since the training is resource-consumine
expect the end-to-end training will follow the same trend in Figure and continue to scale up further when more compute resources are available.
6 Discussion
6.1 Design Alternatives for Inter-Decision Parallelism
To achieve inter-decision parallelism in MCTS, we need break the "sequential" nature of the gameplay, and this typically comes with predicting the next move. Naively, we could store all transitions of the game states so that when new move is started, we can immediately execute the next move or even several future moves in parallel. However, in practice, this is not feasible due to the complexity of the game. On the other hand, in contrast to the prior work [19], which needs an extra NN for speculation prediction and incurs additional cost, our method leverages the anytime algorithm characteristics MCTS, and this naturally leads us to our proposed approach.
6.2 Design Choices Speculative MCTS
The design of speculative MCTS involves (1) improving prediction accuracy, and (2) reducing the speculation cost. For the first design dimension, investigated the number of steps to look ahead in the speculation. Our evaluation shows that, even with only one look-ahead step. we can speed up the training up to xx. Furthermore, the training can benefit from more speculative look-ahead steps when adding more computing resources. For the second design dimension, we integrate NN caching, and more importantly, our analytical method supports general design spaces, which can analyze potential speculation strategies beforehand.
6.3 Limitation of Speculative MCTS
Speculative MCTS introduces a new dimension of parallelism. This approach is more beneficial when computing resources are abundant. When game duration or the total MCTS simulation is short, the performance gain would be limited since the performance improvement comes from looking ahead into future moves. Fortunately, game applications typically utilize high simulation counts or require lengthy sequential decision process and, thus, can benefit from our approach.

---

7 Concluding Remarks
In this paper, we introduce and experimentally evaluate speculative MCTS as novel "inter-decision" parallelism maximization strategy, to reduce the time-to-solution in AlphaZero training. We provide insights into the anytime characteristic of MCTS, which allows us to predict future moves with partial search results and speculatively execute the future moves with the current move in parallel. We further introduce the NN cache and analyze the synergy between the caching mechanism and speculation. Additionally, we propose analytical model that can be used to analyze and evaluate different speculation strategeesimplleenttioon
Our empirical results indicate that the proposed speculative MCTS can accelerate training by up to 5.81 x in 9x9 Go. The end-to-end training results also show a 1.91 x speedup on 19x19 Go game training, compared to statc-of-the-al Go program, KataGo. Finally, our speculative MCTS can combine with other intra-decision parallelism approaches, such as parallel MCTS [10], to enable further performance improvement.
Acknowledgments and Disclosure of Funding
This research funded in part by National Science and Technology Council of Taiwan project number NSTC111--221--0000
We thank the Taiwan National Center for High-performance Computing (NCHC) for providing computational and storage resources. Lastly, would like thank Meng-Yo Yu Tsai for the intellectual discussions.
10

---

References
[1] R. Coulom, "Efficient selectivity and backup operators in monte-carlo tree search," in Computers and Games: 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers 5, pp. 72-83, Springer, 2007.
[2] L. Koesis and C. Szepesvári, "Bandit based monte-carlo planning." in Machine Learning: ECML 2006: 17th European Conference on Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17. pp. 282 293, Springer, 2006.
[3] M. H. Segler, M. Preuss, and M. P. Waller, "Planning chemical syntheses with deep neural networks and symbolic ai," Nature, vol. 555, no. 7698, pp. 604-610, 2018.
[4] S. S. SVS J. N. Law, C. E. Tripp, D. Duplyakin, E. Skordilis, D. Biagioni, R. S. Paton, and P. C.
St. John, "Multi-objective goal goal-directed optimization of de novo stable organic radicals for aqueous redox flow batteries," Nature Machine Intelligence, vol. 4, no. 8, pp. 720-730 2022.
[5] H. Qian, C. Lin, D. Zhao, S. Tu, and L. Xu, "Alphadrug: protein target specific de novo molecular generation," " PNAS Nexus, vol. 1, no. 4, p- pgac227, 2022.
[6] D. Erikawa, N. Yasuo, and M. Sekijima, "Mermaid: an open source automated hit-to-lead method based on deep reinforcement learning." Journal of Cheminformatics, vol. 13, pp. 1-10, 2021.
[7] D. Silver, T. Hubert, Schrittwieser, Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al., "A general reinforcement learning algorithm that masters chess, shogi, and go through self-play," Science, vol. 362, no. 6419, pp. 1140-1 144, 2018.
[8] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya. T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, Welbl, A. Clark, et al., "Training compute-optimal large language models," arXiv preprint
2022.
[9] D. J. Wu, "Accelerating self-play learning in go." arXiv preprint arXiv:1902. 10565, 2019.
[10] G. M. B. Chaslot, M. H. Winands, and H. J. van Den Herik, "Parallel monte-carlo tree search," in Computers and Games: 6th International Conference, CG 2008, Beijing, China, September 29-October 1, 2008. Proceedings 6, p. 60-71, Springer, 2008
[11] Y. Soejima, A. Kishimoto, and O. Watanabe, "Evaluating root parallelization in go," IEEE Transactions on Computational Intelligence and Al in Games, vol. 2, no. 4, pp. 278 278-287, 2010.
[12] M. Boddy and T. L. Dean, Solving time-dependent planning problems. Brown University. Department of Computer Science, 1989.
[13] A. Mandhane, A. Zhernov, M. Rauh, C. Gu, M. Wang, F. Xue, W. Shang, D. Pang, R. Claus, C.-H. Chiang, et al., "Muzero with self-competition for rate control vp9 video compression," arXiv preprint urXiv:2202.06626 2022.
[14] A. Bourki, G. Chaslot, M. Coulm, V. Danjean, H. Doghmen, J.-B. Hoock, T. Hérault, A. Rimmel, F. Teytaud, O. Teytaud, et al., "Scalability and parallelization of monte-carlo tree search," in Computers and Games: 7th International Conference, CG 2010, Kanazawa, Japan, September 24-26, 2010, Revised Selected Papers pp. 48-58, Springer, 2011.
[15] S. A. Mirsoleimani, H. J. van den Herik, A. Plaat, and J. Vermaseren, "A lock-free algorithm for parallel mets.." " in ICAART (2), pp. 589-598, 2018.
[16] Y. Meng, Q. Wang, T. Zu, and V. Prasanna, "Accelerating deep neural network guided mets using adaptive parallelism." in Proceedings of the SC'23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis, p. 766-769, 2023.
[17) A. Liu, J. Chen, M. Yu, Zhai, X. Zhou, and Liu, "Watch the unobserved: A simple approach to parallelizing monte carlo tree search," arXiv preprint arXiv:1810.1173 2018.
11

---

[18] M. Bakhshalipour, M. Qadri, D. Guri. S. B. Ehsani. M. Likhachev, and P. B. Gibbons, "Runahead
a Speculative parallelism for a* with slow expansions." in Proceedings of the International Conference Automated Planning and Scheduling, vol. 33, 31-31-11, 2023.
[19] J. Kim, B. Kang, and H. Cho, "Specmets: Accelerating monte carlo tree search using speculative tree traversal," IEEE Access, vol. 9, p.
2021.
[20] J. F. Martinez and J. Torrellas, "Speculative synchronization: Applying thread-level speculation to explicitly parallel applications," ACM SIGOPS Operating Systems Review, vol. 36, no. pp. 18-29, 2002.
[21] A. Estebanez, D. R. Llanos, and A. Gonzalez-Escribano, "A survey on thread-level speculation techniques," ACM Computing Surveys (CSUR), vol. 49, pp. 1-39, 2016.
[22] A. Kishimoto and M. Müller, "A general solution to the graph history interaction problem," in Proceedings of the 19th national conference on Artifical intelligence, pp. 644-649, 2004.
[23] A. J. Palay, Searching with probabilities. Pitman London, 1985.
[24] M. Müller, "Nogo history and competitions." "https://xebdoca" cs www.erta. ca/ momueleer/noo/hheeee
html", 2015.
[25] K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[26] T. Cazenave, Y.C. Chen, G.-W. Chen, S.-Y. Chen, X.-D. Chiu, J. Dehos, M. Elsa, Q. Gong, H. Hu, V. Khalidov, et al., "Polygames: Improved zero learning," ICGA Journal, vol. 42, no. pp. 246-256, 2020.
[27] D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, Antonoglou, V. Panncershelvam, M. Lanctot, et al., "Mastering the game of go with deep neural networks and tree search," nature, vol. 529, no. 7587, pp. 484-489, 2016.
[28] D. J. Wu, "Networks for katal." "https: "https://katagoee https/////aatttaaiinngg. ortph//wrrrr///ttwr///// 2020.
[29] R. Coulom, "Computing "elo ratings" of move patterns in the game of go," ICGA journal, vol. 30, no. 4, pp. 198-208 20--208,22 2007.
[30] A. Meurer, C. Smith, M. Paprocki, O. Čertík, B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K. Moore, S. Singh, et al., "Sympy: symbolic computing in python," Peer] Computer Science, vol. 3, p. e103, 2017.
12

---

A Appendix Supplemental Material
A.1 Scaling of the Prediction Accuracy
In addition to Figure 2, Figure 11 further evaluates the prediction accuracy for simulations ranging from 50 3200. In general, the prediction accuracy follows consistent trend across all evaluations. These results highlight that prediction accuracy scales effectively among different simulations and further suggest that our speculative MCTS approach scalable across various numbers of simulations.
10395
Prodiction scomncy
Predicsoe accumsyy
Production
0%
2001
Simulation count
Simulation count
Simmlction count
(a) 50 simulations.
(b) 100 simulations.
(c) 200 simulations.
100%
Prediction (ecuna))
Prediction sccumncy
8076
076
400
Simulation count
Simulation count
Simulation count
(d) 400 simulations.
(c) 800 simulations.
1 1600 simulations.
Predectoon accuraoy
800
1600
2400
5200
Simulation count
(g) 3200 simulations.
Figure 11: Prediction accuracy using 50 to 3200 simulations as the full MCTS simulations.
A.2 Alternative Speculation Strategy
Alternative Speculation
(1-step look-ahead)
prodiction
Move
1/2
1/2
Success speculation
Case
Move
1/2
1/2
Failed speculation
Move
Move
1/2
1/2
Case 2
Move 2
1/2
3/2
1/2
Move
1/2
1/2
Time
Figure 12: Alternative speculation pipeline with 1 look-ahead step. Specifically, in Case 2, the speculation starts immediately after pipeline flush.
As discussed earlier in Section 4.1. when the speculation fails, the pipeline is flushed and pipeline "bubbles" are introduced. This section explores an alternative design: instead inserting pipeline bubbles, the speculation is immediately started based on the prediction from the prior tree search result. For instance, Figure 12, Case shows that, when the speculation for Move 2 fails, the pipeline can still speculate Move using the prediction from the previous move (Move 1).
13

---

0.675
0.625
0.600
Pgu
Pg. gg
0.575
1 - Pyi
0.550
0.500
gl
g2
0.5
0.6
Poi + P92
Pg2
(1 Pot )1
Poz)
0.5
0,7
0.6
0.8
0.7
Pe:
1.0
Figure 13: The finite state machine corre- sponds to Figure 12, containing two states: gl (guess 1-step ahead) and g2 (guess 2-step ahead), and the prediction accuracy Py. Poz
Figure 14: Visualization for the expected la-
tency of the speculation pipeline in Figure 12, which is function of prediction accuracy Pot and Poz-
Similar to Figure 5, we first formulate the finite state machine, shown in Figure 13, based on the speculation pipeline cases in Figure 12, where Pa. = Pi defined in Equation and Paz is the probability to make a successful prediction using the prior tree search result. Specifically, gl has Pa probability remain successful prediction, thus having (1 Pai probability to transit the g2 state. On the other hand, g2 remains a successful prediction when both pipeline stages make successful or failed prediction, corresponding to the probabilities Pg, P92 and (1 Po. Po.) Psz). respectively. As result, we can obtain the transition matrix:
M
Poi
1 Pm1
(6)
Ps.
+ Paz
2p., Po2
1 1-
Pvs 2p Paz
Following Equation 1, we can solve for the steady-state probability distribution q via symbolic solver like SymPy [30], which gives us:
Ppo Poz -Pr -Pa
Poi
2P Psg Pu2
2P
Psg
Puz
Further, we can obtain the expected latency for each state based on Figure 12 and Figure 13:
Pet
Blatency of gl] Po. 2 + (1 - Po.) .
(8)
2
3
E latency of g2] P91 + (1 (1-Pa1)6 Po1)
Poz) (Po1 + Pgg 2p Poz)
4"
and thus, L = (Eflatency of gl], LE Elatencyy of g2))". Finally, based on the inner product and L, arrive at the expected latency for the speculation pipeline:
2p Pgz p3, + 2p- p3g 8p2, Pgz + 222 3pp.P? + 11ppr + Ps. + P2 -3pg2
4 (2pp. Ps. - Pgz 1)
(10)
Figure 14 shows the visualization for E[latency] in Equation 10. which function of prediction accuracies Pau and Paz- In the visualization, we can clearly see that, when all predictions are successful, i.c., Py. = and Ellatency] our intuition. When we fix Pa. the higher the prediction accuracy Рgu, the lower the overall latency. Similarly, when we fix Pga, the higher the prediction accuracy Pg. the lower the expected latency. Moreover, suppose we obtain (Po, Pou) = (83.8%, 79.8%) from a profiling similar to Figure 2 in the Go game. In this case, we see the expected latency speedup to be 1.84, while the method Section 4. has lower speedup of 1.72. However, the speedup is improved at the cost of complexity in the implementation. Nevertheless. our analytical model in Section 4.2 can be successfully adapted/applied to various speculative MCTS designs.
0.5, we reach the ideal 2x speedup, and this matches
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We include main claims in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of the work are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
Theory proof' and analysis are provided in Section 4.2 and Appendix A.2.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed experimental settings are provided in Section 5.1, and all evaluations are results of multiple runs.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification:
The model checkpoints are provided in
zenodo. 13929490.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
oonloooiio iccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
wwwsssoliccciiii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Detailed experimental settings provided in Section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: Experiment statistical significance are provided Section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiment compute resource are provided in Section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::://eurrps.... http:://earrpp...cppbbl/
ines?
Answer: [Yes]
Justification:
All authors conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper focuses parallel performance scaling.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper focuses on parallel performance scaling.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets properly credited and cited in the paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
20


Reviews:
[{"review_id": "LtQYAduHqr", "reviewer": "Reviewer_Ty7h", "summary": "The paper introduces Speculative Monte-Carlo Tree Search, which speculates by reducing the number of simulations in MCTS. Experiments demonstrate a two-fold acceleration in training on the Go game.", "questions": "see weakness", "limitations": "na", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to understand, even for readers not familiar with the RL.\n\nThe proposed method experimentally demonstrates improved training efficiency.", "weaknesses": "Inter-game and intra-decision parallelism seem to offer better acceleration than inter-decision parallelism, and they do not require speculation. Can the authors provide experimental evidence to demonstrate the importance of inter-decision parallelism?\n\nFor non-speculative MCTS methods, can we use caching? Based on the paper, caching does not appear to be exclusively beneficial for speculative MCTS.\n\nThere is a lack of comparison with [19] in terms of efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: Inter-game and intra-decision parallelism seem to offer better acceleration than inter-decision parallelism, and they do not require speculation. Can the authors provide experimental evidence to demonstrate the importance of inter-decision parallelism?\n\n**A**: As discussed in general response #1, inter-decision parallelism reduces training latency and improves overall resource utilization. All our evaluations in the paper utilize inter-game parallelism as a baseline. Overall, we want to emphasize that the existing two kinds of parallelism are not able to leverage the increasingly powerful HPC compute resource.\n\n\n**Q**: For non-speculative MCTS methods, can we use caching? Based on the paper, caching does not appear to be exclusively beneficial for speculative MCTS.\n\n**A**: Caching is not exclusive to our proposed method, but our research highlights its synergies with our proposed speculative parallelism of MCTS. Even though caching has been utilized in practice, including AlphaZero, KataGo and ELF Open Go training, it lacks prior literature discussion, especially in the context of caching NN results.\n\n\n**Q**: There is a lack of comparison with [19] in terms of efficiency.\n\n**A**: The prior work [19] can only be applied to gameplay or inferences, and cannot be applied to AlphaZero training since the method requires an additional pre-trained small NN to guide the speculative prediction. Hence, we do not compare our work to theirs, instead we discussed their speculation ideas in our related works section.", "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": "", "extra_scores": {}}, {"review_id": "gkbqw09MO9", "reviewer": "Reviewer_wL1P", "summary": "The paper considers Monte-Carlo Tree Search (MCTS) and aims to increase parallelism.\nIt leverages the fact that MCTS is an Anytime Algorithm, meaning early termination can still yield a feasible solution.\nThis property is used for prediction - the MCTS for the next move is started before the previous move's MCTS has finished.\nThe paper proposes \"inter-decision\" parallelization and speculative MCTS, where future moves are speculatively executed to reduce overall training latency.\nIt also explores synergies between speculation and neural network caching, which seems reasonable.", "questions": "- Fundamentally, is the speedup from speculative MCTS achieved through higher degrees of parallelism?\n- Is the real-world Go model training already highly parallelized, e.g. with the common inter-game parallelism? \n- The paper states \"training latency remains constrained by the sequential inter-decision MCTS self-play, thus limiting the potential benefits from the increasingly powerful high-performance computing (HPC) resources and systems.\" Why is this the case? Where is the bottleneck? Can't enough inter-game parallelism saturate the compute resources? Where does idling occur?\n- Was inter-game parallelism used when measuring the 5.8x speedup? \n- Would n-way inter-game parallelism provide similar speedups as Figure 4 without the risk of failed speculation and potentially higher efficiency?\n- Can the difference between intra-decision and inter-decision parallelism be clarified further? The boundary seems blurry. Isn't considering different nodes of the same tree as root analogous to making different decisions, as leveraged in NN caching?\n- How is accuracy defined in Figure 2? Why is 1600 used as ground truth - would results change with more simulations, say 3200?\n- In Figure 4, is it possible for the prediction from move2 to move3 to fail? If so, shouldn't the dimensionality of q be higher than 2 to account for this?", "limitations": "Some important details are lacking in the paper (see Questions section).\n\nThe code provided in the appendix is insufficient to reproduce the speculative MCTS process.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Proposes ideas of \"inter-decision\" parallelization, speculative MCTS to speculatively execute future moves and reduce overall training latency.\n\nExplores synergizing speculation and neural network caching in a natural and reasonable way.\n\nProvides empirical evaluation demonstrating significant speedups.", "weaknesses": "Some aspects are not clearly explained (see Questions section).\n\nThe efficiency analysis in the Speculation Analysis section does not consider the possibility of failure at each step of a move, implying there are more than just two cases to analyze.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: Fundamentally, is the speedup from speculative MCTS achieved through higher degrees of parallelism?\n\n**A**: Yes, the speedup comes from both higher degrees of parallelism and the synergies of caching to utilize available compute resources.\n\n\n**Q**: Is the real-world Go model training already highly parallelized, e.g. with the common inter-game parallelism?\n\n**A**: Yes, current Go model training, such as KataGo, ELF OpenGo, and AlphaZero, is already highly parallelized in both inter-game and intra-decision.\n\n\n**Q**: The paper states \"training latency remains constrained by the sequential inter-decision MCTS self-play, thus limiting the potential benefits from the increasingly powerful high-performance computing (HPC) resources and systems.\" Why is this the case? Where is the bottleneck? Can't enough inter-game parallelism saturate the compute resources? Where does idling occur?\n\n**A**: As the example introduced in general response #1, the inter-game parallelism is limited due to a fixed number of games collected for a training iteration. Once inter-game parallelism saturates the throughput, the training latency can not be further reduced even with more compute resources. Hence, this motivated us to introduce inter-decision parallelism, which aims to shorten the latency of long sequential decision processes.\n\n\n**Q**: Was inter-game parallelism used when measuring the 5.8x speedup?\n\n**A**: Yes, inter-game parallelism served as our baseline in all our evaluations, including the comparison baseline, KataGo.\n\n\n**Q**: Would n-way inter-game parallelism provide similar speedups as Figure 4 without the risk of failed speculation and potentially higher efficiency?\n\n**A**: When n is moderate, inter-game parallelism has high efficiency since it's an embarrassingly parallelizable technique. However, n often reaches its upper limit in most AlphaZero training. Moreover, as general response #1 mentioned, inter-game parallelism can only improve throughput. Hence, this motivated us to further accelerate the training by reducing the latency, as shown in Figure 4.\n\n\n**Q**: Can the difference between intra-decision and inter-decision parallelism be clarified further? The boundary seems blurry. Isn't considering different nodes of the same tree as root analogous to making different decisions, as leveraged in NN caching?\n\n**A**: Intra-decision parallelism focuses on searching for the current move and making one decision, while inter-decision parallelism focuses on multiple consecutive moves and speculating the most promising sequence of decisions. Hence, in inter-decision parallelism, the NN cache can be shared among threads spread across multiple moves where each search tree is likely to overlap. In contrast, in intra-decision parallelism, where multiple threads evaluate different positions of the same tree, the benefit of NN caching is limited since the cache hits only occur when there are two identical positions in the tree.\n\n\n**Q**: How is accuracy defined in Figure 2? Why is 1600 used as ground truth - would results change with more simulations, say 3200?\n\n**A**: We clarified the definition in general response #2, and the simulation count is a hyperparameter to the training, which does not represent a golden or game-theoretic decision. We also include additional results ranging from 50 to 3200 in the attached file. \n\n\n**Q**: The code provided in the appendix is insufficient to reproduce the speculative MCTS process.\n\n**A**: We will provide the link to the code and the artifacts.\n\n\n**Q**: In Figure 4, is it possible for the prediction from move2 to move3 to fail? If so, shouldn't the dimensionality of q be higher than 2 to account for this?\n\n**A**: Figure 4 shows two cases of the prediction from move-m to move-(m+1), represented by move1 and move2. After predicting move2 from move1, the pipeline proceeds, and the state machine shown in Figure 5 transits to the corresponding state/case. Then, the pipeline continues to predict move3 based on move2, which follows the two cases in Figure 4. Hence, the dimension of q is 2 in our analysis.\n\n\n**Q**: The efficiency analysis in the Speculation Analysis section does not consider the possibility of failure at each step of a move, implying there are more than just two cases to analyze.\n\n**A**: As answered in the previous question, the two cases represent two states in the finite-state machine. Hence, the pipeline state transits to the next state/case after making a success or failure prediction.", "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": "", "extra_scores": {}}, {"review_id": "0usaaxhVQx", "reviewer": "Reviewer_BfQS", "summary": "This paper proposes Speculative Monte Carlo Tree Search (MCTS), which predicts the next move of MCTS before completing the search on the current node. This concept is similar to the branch prediction algorithm in CPU pipelining. Speculative MCTS proceeds to the next node by predicting the branching direction of the current node. If the prediction fails, it reverts to the current node and flushes all previous computations.\n\nAdditionally, the paper introduces a caching technique to store the inference results of MCTS during the search. By combining speculation and caching, the training speed of an AI Go program is accelerated by 2x.", "questions": "N/A", "limitations": "+ While the caching strategy is effective in board games (and perhaps card games), it does not apply to video games such as Atari.\n\n+ For end-to-end experiments, only 1-step lookahead speculation is evaluated. While the authors claim that more lookahead steps can potentially improve performance, this should be validated in real experiments.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "+ The writing is clear, with well-articulated motivations, extensive experimental details, and thorough discussions of related works.\n\n+ The idea presented in this paper is straightforward yet highly effective. The 2x training speedup with just one lookahead step is impressive. The authors have done excellent work in implementation and in conducting a fair comparison with existing methods.", "weaknesses": "+ It is unclear whether accelerating the training of a Go program is beneficial to the community, given the existence of many strong Go programs and the infrequent need to train a new one from scratch. Although the method itself is great, the lack of application scenarios could diminish the overall contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: It is unclear whether accelerating the training of a Go program is beneficial to the community, given the existence of many strong Go programs and the infrequent need to train a new one from scratch. Although the method itself is great, the lack of application scenarios could diminish the overall contribution.\n\n**A**: The Go game is known for its complexity and remains several open problems unsolved, such as adversarial attacks [1] and game-theoretical values, including life-and-death [2] and game-solving [3], even though many strong Go programs exist. Moreover, many active recent research studies have also investigated multiple variants of Go games, such as Go games with various board sizes or variations in the winning condition, such as the Killall Go game [4]. Specifically, our evaluations cover 9x9 NoGo, 9x9 Go, and 19x19 Go games. Hence, being able to train a new Go program from scratch faster can accelerate the research in the field. Also, we discussed possible application scenarios in general response #3.\n\n\n1. Wang, T. T., Gleave, A., Tseng, T., Pelrine, K., Belrose, N., Miller, J., ... & Russell, S. (2023, July). Adversarial policies beat superhuman go AIs. In International Conference on Machine Learning (pp. 35655-35739). PMLR.\n2. Kishimoto, A., & Müller, M. (2005, July). Search versus knowledge for solving life and death problems in Go. In AAAI (pp. 1374-1379).\n3. Randall, O., Müller, M., Wei, T.H. and Hayward, R., 2024. Expected Work Search: Combining Win Rate and Proof Size Estimation. arXiv preprint arXiv:2405.05594.\n4. Wu, T. R., Shih, C. C., Wei, T. H., Tsai, M. Y., Hsu, W. Y., & Wu, I. C. (2022). AlphaZero-based proof cost network to aid game solving. In International Conference on Learning Representations.\n\n\n**Q**: While the caching strategy is effective in board games (and perhaps card games), it does not apply to video games such as Atari.\n\n**A**: Our work applies to games that can utilize the AlphaZero algorithm; thus, video games such as Atari are outside our primary scope of applications. However, as discussed in general response #3, other variants of the AlphaZero algorithm may apply to these video game applications.\n\nOn the other hand, in Section 5.3, we identified two sources of cache hits: (1) intra-game and (2) inter-game hits. We believe that video games also exhibit similar characteristics. Consider the following search paths for two consecutive moves in each search tree:\n\nSearch path on the tree of move 1: (root) s1 => s2 => s3 => s4 => **s5**\n\nSearch path on the tree of move 2: (root) s2 => s3 => s4 => **s5** => s6\n\n, where s1, …, s6 represents game states. For instance, in the \"Pac-Man\" Atari game, the first search path can correspond to sequences of moves like \"right=>**right=>right=>up**\" show substantial overlap with the second search path, \"**right=>right=>up**=>up\", when the player navigates towards a goal. Hence, we can observe that when speculatively executing two tree searches in parallel, the inference result for s5 can be reused across consecutive moves within the same game, showing intra-game temporal locality. Similar observations also apply to inter-game caching.\n\n\n**Q**: For end-to-end experiments, only 1-step lookahead speculation is evaluated. While the authors claim that more lookahead steps can potentially improve performance, this should be validated in real experiments.\n\n**A**: End-to-end experiments can help us demonstrate the effectiveness of our proposed approach, but additional evaluations also require a lot more compute resources. Hence, we adopt a bottom-up approach to elaborate our work from an analytical analysis, caching evaluation, and latency evaluation to the final end-to-end evaluations.", "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": "", "extra_scores": {}}, {"review_id": "Zig18xdfip", "reviewer": "Reviewer_j3Ju", "summary": "The paper proposes a new variant of parallelization in Monte Carlo Tree Search (MCTS) algorithm in the context of AlphaZero and the game of Go. The modification builds on the anytime nature of MCTS and consists in forking the search for subsequent moves (actions) before the search of a given move (action) is completed. It is experimentally verified in the paper that the proposed parallelization leads to reduction of training latency.", "questions": "1. Is the method applicable in the contexts other than AlphaZero and the game of Go? Can it be applied beyond the domain of games?\n2. How have the base numbers of simulations, i.e., 1600/800 been selected? Why these particular values are considered?\n3. The method should work nicely with sufficiently high number of simulations per move, since lowering (division of) their count would still lead to meaningful move estimations. What would happen if the base number of simulations was significantly lowered, e.g., from 1600 to 400? \n4. The authors show that lowering the number of simulations per move from 1600 to 800 changes the selected move in almost 20% of the cases. However, what can be said about the strength of MCTS with 1600 simulations per move is not discussed in the paper. I would suggest making the following experiment: use sufficiently high number of simulations to achieve almost perfect move selection and then compare the accuracy of move selection with 1600 and 800 simulations, respectively (both of them versus a perfect selection case). Such a comparison should present the real difference in strength between these two cases (1600 vs. 800 simulations).", "limitations": "The limitations of the proposed method are briefly mentioned in the paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The experiments show that the proposed method leads to time savings, at least in a few setups considered in the paper.", "weaknesses": "1. The experimental evaluation is insufficient for a comprehensive evaluation of the proposed MCTS parallelization. It seems that the strength of the method highly depends on the base number of simulations. How to choose a proper number of them is not explained in the paper.\n2. The ablation section should be significantly extended – see particular questions in the section below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: The experimental evaluation is insufficient for a comprehensive evaluation of the proposed MCTS parallelization. It seems that the strength of the method highly depends on the base number of simulations. How to choose a proper number of them is not explained in the paper.\n\n**A**: As discussed in general response #2, our method does not highly depend on the base simulations, and we adopt the same number of simulations that are used in many closely related works.\n\n\n**Q**: The ablation section should be significantly extended – see particular questions in the section below.\nIs the method applicable in the contexts other than AlphaZero and the game of Go? Can it be applied beyond the domain of games?\n\n**A**: Yes, as discussed in general response #3, any applications that can utilize the AlphaZero algorithm can benefit from our work, including chemistry synthesis and material science.\n\n\n**Q**: How have the base numbers of simulations, i.e., 1600/800 been selected? Why these particular values are considered?\n\n**A**: As discussed in general response #2, the base numbers of simulations is a hyperparameter of the training where 800 and 1600 are commonly selected in prior works.\n\n\n**Q**: The method should work nicely with sufficiently high number of simulations per move, since lowering (division of) their count would still lead to meaningful move estimations. What would happen if the base number of simulations was significantly lowered, e.g., from 1600 to 400?\n\n**A**: As discussed in general response #2, common applications use simulation counts around 800 to 1600 since the strength will be reduced if trained with a lower simulation count. Nevertheless, we include evaluation and discussion with various simulation counts ranging from 50 to 3200 in the general response #2. Additionally, in Section 6.3, we have mentioned the potential limitation when the simulation count is low since, given a limited computation amount (i.e., to make a decision in a very short time or a small number of resources), we can only have a limited benefit from parallelization.\n\n\n**Q**: The authors show that lowering the number of simulations per move from 1600 to 800 changes the selected move in almost 20% of the cases. However, what can be said about the strength of MCTS with 1600 simulations per move is not discussed in the paper. I would suggest making the following experiment: use sufficiently high number of simulations to achieve almost perfect move selection and then compare the accuracy of move selection with 1600 and 800 simulations, respectively (both of them versus a perfect selection case). Such a comparison should present the real difference in strength between these two cases (1600 vs. 800 simulations).\n\n**A**: As discussed in general response #2, we do not treat 1600 simulations as a golden/perfect or game-theoretical value to the current decision. Instead, the simulation count is a hyperparameter to the training, which is commonly decided by the compute budget for the training.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable feedback. Below, we answer the questions/concerns common among multiple reviewers.

## #1. Why is inter-decision parallelism necessary beyond inter-game and intra-decision parallelism?

Inter-game parallelism can only enhance training throughput, while intra-game parallelism improves both latency and throughput. However, the speedups from throughput improvements are capped and cannot increase even with extra compute resources. Consider the following example:

Suppose a training iteration requires collecting 8,192 games, with a batch size of 1024 per GPU. An 8-GPU machine can fully parallelize all 8,192 games by inter-game parallelism. Yet, when more computing resources are available than a single 8-GPU machine, additional training parallelism is required to utilize these resources fully, and thus, intra-game parallelism becomes crucial in this case. Moreover, in Section 2.2 of our paper, we discussed the limitation of intra-decision parallelism and related prior works. Furthermore, as HPC systems grow increasingly powerful, the batch size per GPU increases while maintaining the same latency. For instance, if the batch size is doubled to 2048 on next-gen GPUs, inter-game parallelism alone will be insufficient to saturate an 8-GPU machine since four next-gen GPUs can achieve a throughput of 8,912 games per iteration. 

Hence, the time-to-solution for training cannot be reduced via throughput improvement, even with infinite compute resources, especially in AlphaZero training, which typically experiences high latency due to the long game length. As a result, our proposed inter-decision parallelism complements existing parallelism methods, offering further parallelization opportunities in training.


## #2. Clarifications on 1600 simulations

The number of simulations for MCTS is a hyperparameter in AlphaZero training, whose values commonly seen and chosen ranging from 800 to 1600 in prior works such as AlphaGo Zero, AlphaZero, ELF OpenGo, KataGo, and MuZero. For our evaluation, we selected 1600 to demonstrate that our proposed approach is scalable to higher MCTS simulations compared to many prior works. In Section 2.2, we referred to the number 1600 as performing a complete tree search, which can also be set to 800 or other reasonable figures. Also, the result from a tree search with 800 or 1600 simulations should not be seen as the golden or optimal solution to a move, namely not a game-theoretical move, but rather as reaching the reference point for training, meaning that the simulation results can improve the previous iteration.

We also want to clarify the definition of "prediction accuracy" in Figure 2. In the figure, we use the search results from lower simulation counts to predict the results from 1600 simulations. Then, "prediction accuracy" is defined as the fraction of correct predictions when using fewer simulations compared to the results of 1600 simulations. Similar evaluations can be done with the number 1600 being substituted by other reasonable figures representing the compute resource budget for a complete tree search. It is also to be noticed that the prediction accuracy is compared against the baseline MCTS without speculation, not compared against the game-theoretical move, which we do not know. More importantly, we emphasize that we can reasonably predict the result of a complete tree search, thus motivating speculation.

Furthermore, we include additional evaluations with varying simulations ranging from 50 to 3200 in the attached file. Figure 1 from the file shows that the prediction accuracy generally follows a similar trend to the 1600 simulation results in the paper. The results not only indicate that MCTS has good scaling in prediction but also suggest that our speculative MCTS is scalable across various simulations.


## #3. Applications beyond the Go game

Our method applies to applications that utilize the AlphaZero algorithm, including board games, material sciences [1], chemical synthesis [2], and video compression [3]. In general, our proposed speculative MCTS parallelization also applies to AlphaZero-like algorithms, including MuZero [4], Stochastic MuZero [5], and other variants, since our method primarily leverages the Anytime Algorithm characteristics of MCTS and hence can be easily extended to our analysis to others. For instance, MuZero can train on Atari games and other video games.

Moreover, our proposed approach is not bound to a specific application domain. We implement and evaluate speculative MCTS on AlphaZero and Go games due to the well-known robustness and complexity of the algorithm and game. Also, we provided high-level insights into the potential for applying speculative parallelism to other Anytime Algorithms. Future research could explore similar analyses for other search algorithms with Anytime properties.

1. Gaymann, A., & Montomoli, F. (2019). Deep neural network and Monte Carlo tree search applied to fluid-structure topology optimization. Scientific reports, 9(1), 15916.
2. Segler, M. H., Preuss, M., & Waller, M. P. (2018). Planning chemical syntheses with deep neural networks and symbolic AI. Nature, 555(7698), 604-610.
3. Mandhane, A., Zhernov, A., Rauh, M., Gu, C., Wang, M., Xue, F., ... & Mann, T. (2022). Muzero with self-competition for rate control in vp9 video compression. arXiv preprint arXiv:2202.06626.
4. Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., ... & Silver, D. (2020). Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839), 604-609.
5. Antonoglou, I., Schrittwieser, J., Ozair, S., Hubert, T. K., & Silver, D. (2021, October). Planning in stochastic environments with a learned model. In International Conference on Learning Representations.

Meta-review: This paper received mixed reviews, some with low confidence. The discussion phase has been useful to clarify some important concerns raised by Reviewers, e.g., the significance of the contribution. The main remaining concerns are the reproducibility of results and the applications beyond Go.

Regarding reproducibility, I do not consider this a big problem with this submission. AlphaZero is notoriously difficult to code and handle, it is not critical that a paper of this kind does not extensively provide all reproducibility details.

Regarding the applications, the Authors have properly clarified that their method works in all applications where AlphaZero is used. Thus, the proposed method is relevant enough. The presence of other applications than Go would definitely be desirable to assess the general-purpose nature of the proposed method, but I consider Go relevant enough to advocate for the usefulness of the approach.

Overall, this paper is a well-described relevant upgrade of AlphaZero, with a clear description, clean implementation, and good empirical performance. I consider this paper good for acceptance.
Decision: Accept (poster)