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, and defended its title in 2014.

The program was 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: Jun 21, 2018
Martin Müller