> -----Original Message----- > From: Tapani Raiko <[EMAIL PROTECTED]> > To: computer-go <[email protected]> > Sent: Tue, 30 Oct 2007 6:39 am > Subject: Re: [computer-go] BOINC > > milestone 1: All network-nodes compute pure Monte-Carlo (no search > > tree) scores for the possible moves, the scores are combined centrally > > to pick the move. It's easy, it will wring out the system, and the > > bandwidth is low. The playing performance will always be poor because > > this algorithm doesn't scale well. > > > > milestone 2: Each network-node builds its own tree using UCT, but > > information is only combined at the root. This version will play much > > better because each node is smarter. The bandwidth will be higher. I > > can only guess at the scaling behavior, but this milestone might be > > the 80% solution. > > > > milestone 3: Information from the search-nodes is shared between > > network-nodes, but only for search-nodes close to the root of the > > tree. Sounds innocent enough. You just limit the shared nodes to the > > first couple of plys. But it's a trap that will suck you in: best > > scaling behavior requires too much communication-but what if you made > > each Monte-Carlo simulation smarter...? > Why not make each computer specialize in a certain branch of the tree? > That way the (implicit) combination of the trees of all the computers > could grow very large. Of course some central intelligence would need to > allocate resources to different branches dynamically, so it would be > more difficult to implement. In these three milestones, the different > computers would do a lot of overlapping work with the deeper nodes, if I > understood them correctly. That could be done too, but it wouldn't be my first choice. I'm envisioning a BOINC-like network where the number of processors available isn't known in advance and they can come and go unpredictably. My guess is that keeping everything balanced for specialized branches would be a big headache and the overhead would be excessive. And you'd need some redundancy in case a processor with a critical branch went offline at an inopportune moment. But it could be done. The overlapping work is not so bad because the playouts are stochastic and there would be some benefit from averaging. Milestone 1 is no different than if it were running on a single computer. Many of us have experimented with stunting the growth of the UCT search tree by only expanding nodes?after they?have been visited N times. There is a strength penalty, but it's pretty small compared to the reduction in tree size. I think milestone 3 has the most potential, but it would take some heavy lifting to make it work. - Dave Hillis ________________________________________________________________________ Check Out the new free AIM(R) Mail -- Unlimited storage and industry-leading spam and email virus protection.
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
