> MoGo's parallelization has been published, but with moderate results because > at that time we were only using ethernet. The > same algorithm with good networks provide good results in 9x9 and very > good results in 19x19. The trick is just that sharing only nodes of the tree > with at least 5% of the total number of simulations, say 20 times > per second, is enough for a nice speed-up. This is not possible with > ethernet, but it is possible with myrinet, infiniband, or things like taht.
Interesting. It's fairly similar to what I was envisioning, but relies much more on the network. Mine was oriented more towards a distributed cluster, connected over the internet. Given this information, my approach is most likely useless, at least on a setup like yours. I'll tell you sort of what I was thinking about though: Each node in the network communicates with just a few others in the network. These relationships are arranged hierarchically, but they can adjust dynamically. Each node has a parent and some siblings. Each node sets its own root node somewhere in the tree below the root of its parent (in most cases one move after). The parent and the children communicate in the following way: every X nodes, the parent sends the move list of its root with the number of playouts, the number of wins, and the number of children searching below each. The children send back which move they choose to search (based both on UCT or whatever tree search algorithm you use, and what the other children are doing) and the results along with a PV. Sometimes children will dissociate with a parent and try to find a better place in the tree to search. The strength of this approach is a self-regulating tree of nodes that will automatically find the most lucrative places to search without needing to communicate with a master server. The tree of nodes will end up looking somewhat like a UCT tree. Add in the possibility of the network regulating its connections as well based on lag time, and it gets pretty complicated. It might be the only viable approach when running on a cluster though... What do you think? > With 32 nodes, you get > 95% winning rate against the one-node baseline, and this can be implemented > using MPI within just a few lines (recursive sharing of the nodes in the > tree). The reference (conference icinco2008) > is on my web page (http://www.lri.fr/~teytaud/cv/cv.html), but the results > in the paper are disappointing > as the results on this paper were with ethernet only. We'll publish > the new speed-up curves soon (preliminary results below). In 9x9, it's far > less impressive, unfortunately; but perhaps improvements are possible. > Note that these results are with very good networks, but better hardware > exists... if you have plenty of money :-) And 64 quad cores are cheap? ;) Seriously though, thanks for the information. I guess the paper is not available on the web anywhere? I think I understand your basic idea pretty well though. One interesting trend that I see is that the uncertainty increases for 19x19 when the matches get closer, while that doesn't happen in 9x9. Maybe 9x9 is just shallow enough that the matches are more decisive. Or is it just based on how many games were used to get this result? _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
