Parallel Nested Rollout Policy Adaptation

Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo tree search algorithm that excels in the domain of single agent optimization problems. It was applied to a wide class of problems, including vehicle routing, DNA alignment, 3D packing, travelling salesman problem, combinatorial puzzles and more. We develop a parallel version of NRPA that replicates results of the sequential version. The parallelization allows us to run deeper calculations. The experimental data shows that depth of the calculation is a deciding factor in the result quality. Earlier parallelization attempts used parallel architecture to run wider, but not deeper, calculations. We applied the parallel version to the Morpion Solitaire benchmark. To aid parallelization, we used a different best result replacement rule. Using the new rule, on a distributed architecture with 768 cores we obtained an average speedup over a single core computation by a factor 547.48. For the first time a level 6 NRPA computation with 80 iterations per level was finished. It was completed in less than 20 hours of wall-clock time. The different replacement rule was effective. In each run, the record 178-move sequence was found.