Since the game tree of Go is finite (with positional superko), unlimited memory could be not necessary.
Hideki Michael Williams: <[email protected]>: >Absolutely that harms the convergence. It is completely out the window when >you start deleting nodes. The convergience property exists only in the >presence of unlimited time and memory. > > > >On Tue, Jun 7, 2011 at 8:02 PM, Hideki Kato <[email protected]> wrote: > >> Darren Cook: <[email protected]>: >> >> The math escapes me here. I think doubling the playouts gains in the >> >> neighborhood of 70 ELO points. If adding a thread costs 10 ELO, >> >> adding more threads would stop being beneficial after about 14 >> >> threads. Doubling from 7 to 14 would lose 7*10 ELO, equaling the gain >> >> of the extra playouts. After that, adding threads should actually >> >> lose ELO. Yet we see people trying to put together systems with 100s >> >> of CPUs. What am I missing? >> > >> >Richard Segal (who operates Blue Fuego) has a paper on the upper limit >> >for scaling: >> > http://www.springerlink.com/content/b8p81h40129116kl/ >> >(Sorry, I couldn't find an author's download link for the paper; Richard >> >is on the Fuego list but I'm not sure he is even a lurker here.) >> > >> >I didn't fully understand the methodology, but what I did take away from >> >it (and discussions with Richard) was that though we're satisfied that >> >pure UCT eventually expands all nodes and can solve a position just like >> >minimax, this is not the case once you start adding enhancements such as >> >rave and virtual loss and *parallelizing the algorithm*. >> >> Hm, even if the theory guarantee the convergence, not only time but >> also memory are finite in practice. Good GC (garbage collection), or >> actually, pruning-less-important-leaf-node algorithms are important for >> MCTS because MCTS requires much more memory than depth first search. My >> question is, then, is it possible to design a GC algorithm for MCTS >> which does not harm the convergence? Currently most developers use the >> visit-count of a node to prune the node or not, I guess. One more >> question, does this harm the convergence? >> >> Hideki >> >> -- >> Hideki Kato <mailto:[email protected]> >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >---- inline file >_______________________________________________ >Computer-go mailing list >[email protected] >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go -- Hideki Kato <mailto:[email protected]> _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
