1
$\begingroup$

I am trying to better understand the article "Mastering the Game of Go without Human Knowledge" (link) and I'm confused about the parallel implementation of Monte-Carlo-Tree-Search.

On page 25 under "Search Algorithm", the authors say (emphasis mine)

AlphaGo Zero uses a much simpler variant of the asynchronous policy and value MCTS algorithm (APV-MCTS)

Multiple simulations are executed in parallel on separate search threads.

On page 26 under "Select",

an action is selected according to the statistics in the search tree

There are some math details on how an action is selected based on (among other things) the mean action value (Q).

I find this confusing because the choice of action at each simulation depends on the statistics of the previous simulations (the value of Q).

How can simulations be run in parallel given that the choice of action in each simulation depends on the value obtained by the end of the last simulation?

$\endgroup$

2 Answers 2

2
$\begingroup$

To understand how AlphaGo Zero performs parallel simulations think of each simulation as a separate agent that interacts with the search tree. Each agent starts from the root node and selects an action according to the statistics in the tree, such as:

(1) mean action value (Q), (2) visit count (N), and; (3) prior probability (P).

The agent then follows the action to the next node and repeats the process until it reaches a leaf node. At the leaf node, the agent evaluates the state using the neural network and propagates the value back to the root node, updating the statistics along the way.

However, since there are multiple agents running in parallel, they may not have access to the most updated statistics in the tree. For example, one agent may select an action that another agent has already explored and updated its value. To avoid this problem, AlphaGo Zero uses a virtual loss mechanism that temporarily reduces the Q value of a node when an agent visits it. This discourages other agents from selecting the same node until the first agent finishes its evaluation and restores the Q value. This way, each agent can explore different parts of the tree without waiting for each other.

Pseudo code of the parallel search engine

$\endgroup$
0
$\begingroup$
  1. you have a board in front of you
  2. you pick N most likely moves from the optimal policy (likely = doing this move you are more likely to win)
  3. you create N threads
  4. in each thread, you simulate doing one of these moves, and in parallel, you can go on with this reasoning recursively

Once you reach the terminal node, or you finished you time budget, you use the V function to approximate the result, and you back-propagate the information using usual methods

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .