Parallel Monte-Carlo Tree Search

By Guillaume M, J-B Chaslot, Mark H. M. Winands, H. Jaap Van Den Herik. Computers and Games, 2008

304 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Economics and Econometrics, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/3b41773cf65c4d7cde97e3b8c82295433b9a8f39

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Mohit Bansal
2. Yuxi Li
3. Josh Tenenbaum
4. Chuang Gan
5. Yuandong Tian
6. Sergey Levine
7. Ruslan Salakhutdinov
8. Luke S. Zettlemoyer

In Economics and Econometrics

1. Qucheng Gong
2. Edward Jack Powley
3. J. Kolter
4. Cameron Browne
5. Simon M. M. Lucas
6. Simon Colton
7. Peter I. Cowling
8. Josh Tenenbaum

In Sociology and Political Science

1. Chuang Gan
2. J. Kolter
3. C. Lawrence Zitnick
4. Josh Tenenbaum
5. Yuxin Wu
6. Julian Togelius

Citations in the corpus

• Variance Reduction in Monte-Carlo Tree Search (2011, unknown): “Noteworthy enhancements include the addition of domain knowledge [12, 13], parallelization [7], Rapid Action Value Estimation (RAVE) [11], automated parameter tuning [8] and rollout policy optimization [21].”
• ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero (2019, methodology): “MCTS can be multithreaded using the virtual loss technique (Chaslot et al., 2008), and MCTS’s performance intuitively improves as the number of iterations (“rollouts”) increases.”
• Planning with Large Language Models for Code Generation (2023, methodology): “We also consider using parallel tree search algorithms (Chaslot et al., 2008) for the evaluation step to parallelize the computation for different states.”
• Monte Carlo Tree Search With Iteratively Refining State Abstractions (2021, background): “However, high performance MCTS implementations almost ubiquitously use large amounts of parallelization [8].”
• PACHI: State of the Art Open Source Go Program (2011, background): “Historically, various thread parallelization approaches for MCTS have been explored [6].”
• HyperTree Proof Search for Neural Theorem Proving (2022, methodology): “In order to batch calls to the policy and critic models over more nodes to expand, we run several selections sequentially, using a virtual loss [21, 5] to produce different partial proof-trees.”
• AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search (2019, methodology): “…to parallelize MCTS is by introducing a virtual loss , which is a method to avoid making all the processors to traverse the same trajectory by backpropagating a score (i.e. performance of the DNN) of 0 before the rollout finishes and the actual score becomes available to the agent [4, 6, 47, 35].”
• ELF: An Extensive, Lightweight and Flexible Research Platform for Real-time Strategy Games (2017, methodology): “We use root parallelization [9] in which each thread independently expands a tree, and are combined to get the most visited action.”
• A Survey of Monte Carlo Tree Search Methods (2012, background): “1) Leaf Parallelization: Leaf parallelization as defined in [59] involves performing multiple simultaneous simulations every time the MCTS tree policy reaches (or creates) a leaf”