On Tue, May 12, 2009 at 6:33 PM, Dave Dyer <dd...@real-me.net> wrote:
> > An essential feature of monte carlo is that it's search space is > random and extremely sparse, so consequently opportunity to re-use > nodes is also extremely sparse. That depends. Monte Carlo only expands node it considered promising and it's very focused on only expanding those nodes. At some point however, it does accumulate nodes that are "worthless" in the sense that (for the most part) it is very unlikely to visit again. But it may spend some time deciding that and it's information you don't really want to discard if you can avoid it. > > On the other hand, if the search close to the root is not sparse, my > previous arguments about the number of nodes and the number of them > that will continue to be useful still apply. I think we are talking about 2 different things. Tell me if I am correct, but I think you are trying to say that storing the tree won't help in most positions, because after even a very few moves you will get no utility out of this. If that's what you mean, then I agree. But that's not what I'm saying. Let's say I do a 10 second search and generate 50,000 nodes. I've generated 50,000 nodes that are all useful in accord with the MCTS algorithm I'm using. If I use persistent storage and do that search again in another game, I can start exactly where I left off and generate 50,000 more nodes. It will be the same as if I did 100,000 nodes instead of 50,000 nodes. Or put another way, it will be the same as if I spent 20 seconds on this move instead of 10 seconds. NONE of these nodes can be considered "not useful" and I think you are way off based to think that. They were generated by a search and we consider MCTS pretty useful, and a good MCTS is pretty effective about not generating a lot of "not useful" moves. What I'm saying is that we may not have to simply throw this hard earned information away. Will this help much on 19x19? I think it might a little. If you persistently save the tree, you will tend to play the same moves - which means you will get good utility out of this and may fairly quickly have accumulated a lot of saved search effort - even if for only a few of the first move choices. Is this better than a human generated book? No, but that doesn't matter. Even In 9x9 it seems like you need a human book, even in 7x7 it seems to be the case. But I opened this discussion specific about automated book generation. - Don > > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
