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)
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.
2011 International Planning Competition (IPC 2011) Planner Description Booklet.
Some External Links for Parallel Search
Created: Jan 10, 2012. Last modified: Feb 1, 2012
Martin Müller