Parallelism can potentially be exploited for all search problems. We focus on parallel search in Monte Carlo Tree Search and in satisficing planning.
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.
(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.
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. An updated version was entered into the 2018 competition, which unfortunately was cancelled by the organizers.
The program was developed by Rick Valenzano, Hootan Nakhost, Martin Müller, Jonathan Schaeffer, and Nathan Sturtevant.
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.