Parallel Search

Parallelism can potentially be exploited for all search problems. We focus on parallel search in Monte Carlo Tree Search and in satisficing planning.

Parallel Monte Carlo Tree Search

There are several ways of parallelizing MCTS. Our Go program Fuego directly supports lock-free shared memory parallelism. In conjunction with the BlueFuego library developed by Rich Segal at IBM Fuego can be used on a distributed memory system which supports MPI.

Publications - Parallel MCTS

(external publication, collaborator using Fuego) R. Segal. On the Scalability of Parallel UCT. Computers and Games, Lecture Notes in Computer Science 6515, pp. 36-47, editors van den Herik, H.; Iida, H. and Plaat, A., Springer Berlin / Heidelberg, DOI link 2011.

M. Enzenberger, M. Müller, B. Arneson and R. Segal. Fuego - An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 259-270. Special issue on Monte Carlo Techniques and Computer Go, 2010.

M. Enzenberger and M. Müller. A lock-free multithreaded Monte-Carlo tree search algorithm, 2009. Advances in Computer Games 12, LNCS 6048, pages 14-20, Springer. DOI link.

Parallel Search in Satisficing Planning

ArvandHerd is a parallel, portfolio-based planner based on a combination of LAMA and Arvand planners. The program won the sequential multicore track of the Seventh International Planning Competition, IPC 2011. The program is being developed by Rick Valenzano, Hootan Nakhost, Martin Mueller, Jonathan Schaeffer, and Nathan Sturtevant.

Publications - Parallel Planning

R. Valenzano, H. Nakhost, M. Müller, J. Schaeffer, and N. Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. In ECAI, 2012.

R. Valenzano, H. Nakhost, M. Müller, J. Schaeffer, and N. Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. 2011 International Planning Competition (IPC 2011) Planner Description Booklet.

Some External Links for Parallel Search


Created: Jan 10, 2012. Last modified: Apr 18, 2013

Martin Müller