Any distributed parallel tree search algorithm suggestions?

Question

I'm writing a distributed Go/Gomoku bot.

Basically the point is to distribute tree search onto many computers. With basic tree search algorithms like DFS this would be very simple, as I could just partition search space into subtrees. Though I'd rather have something more efficient, like mini-max with alpha-beta pruning - but from my understanding it's quite pointless without any kind of shared memory. So I'm kind of stuck.

Any ideas what algorithm could I use that's efficient and distributed easily? And more importantly, where can I find some (pseudo) code for it or maybe implementation?

Thanks,

Answer 1

You need to read up about Monte Carlo Tree Search, not because it's inherently easier to distribute (it is neither easier nor harder than another tree search), but because it's the state of the art and that people working on the problem are working on distributed version of that algorithm.

If you are going to the trouble of making a distributed algorithm, there's no reason to start with a lesser one. Unless you are making a distributed algorithm for educational reasons, in which case, go ahead, there will be something deeply educational in the experiment of distributing a basic algorithm and seeing it perform worse than the non-distributed state-of-the-art algorithm :)

Some slides

The MoGo homepage

See the "recent developments" section in the Wikipedia page on computer go.

Answer 2

Try Map Reduce approach. For example, see

Breadth-First Search (BFS) & MapReduce

Answer 3

DDS* and ABDADA are 2 distributed/parallel minimax algorithms. Some communication is necessary, but this could be done by relaying certain results back to the controller.

The easier approach as you mentioned would be something like map reduce with different search tree roots.

As @Pascal Cuoq rightly mentions, Monte Carlo Tree Search is the state-of-the-art in Go.

Here you can find a good explanation of MoGo's search algorithm and how its parallelized:

http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf

nodes which are playing out with better outcomes based on random play are more deeply explored. At each step a leaf node is selected for a one-ply expansion. This could be distributed by having each machine choose a different leaf to expand.

a good overview of the monte carlo tree search is here:

http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf