2

I would like to parallelize my MCTS program. There are several ways to do this:

  1. Leaf parallelization, where each leaf is expanded and simulated in parallel.
  2. Root parallelization, where each thread/process creates a separate tree and when some number of simulations are finished, trees are combined to give a better statistic
  3. Tree parallelization, where all threads/processes share the same tree and each thread/process explores different parts of the tree.

(If my explanation is unclear, checkout this review paper on MCTS. On page 25, different methods on parallelizing MCTS are described in detail.)

Question:

Since multiprocessing in Python has to create separate subprocesses, 2. Root parallelization fits quite nicely, whereas I am assuming that 3. Tree parallelization is not feasible. (Since for tree parallelization, all subprocesses would have to share the same tree - which is difficult to do in Python)

Am I correct? I skimmed through the multiprocessing documentation and if I understood correctly, it seems like it is possible to pass information back and forth between subprocesses for some basic data types, but are highly discouraged due to speed etc.

If so, tree parallelization in Python would be a bad idea right?

Semin Park
  • 650
  • 6
  • 20
  • Have you had a look at `multiprocessing.Value` and `.Array`? This answer explains how they work with numpy: https://stackoverflow.com/questions/5549190 – Thomas Ahle Jul 29 '19 at 19:13
  • Yes I have but this is not really applicable in my case because for tree parallelization it is required that all threads can *dynamically* allocate and deallocate shared memory, which is impossible using `mp.Value` or `mp.Array`. Actually I ended up implementing it in C++. – Semin Park Oct 12 '19 at 08:35

1 Answers1

2

Yes, you're correct that Root Parallelization would be the easiest of those variants to implement. The different processes would essentially be able to run completely independent of each other. Only at the end of your search process would you have to aggregate results in whatever way you choose, which I don't believe should be problematic to implement.

I am familiar enough with multiprocessing in Python to know it's... a little bit of a pain when you want more communication (the kind of communication the other two approaches need). I am not familiar enough with it to tell with 100% certain that it's really "impossible" or "highly discouraged", but there's certainly a clear difference in ease of implementation.

Dennis Soemers
  • 8,090
  • 2
  • 32
  • 55