Search code examples
pythonpython-3.xparallel-processingmultiprocessingmonte-carlo-tree-search

MCTS *tree* parallelization in Python - possible?

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?

Solution

  • 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.