I don't think you have any understanding of what I'm suggesting. You don't actually store the whole tree, you store whatever part of it is generated by the program and that is an infinitesimal subset. I have noticed that many times you tend to think in purely theoretical terms when it was completely out of context and I think you are doing it again.
So basically you can only store nodes at the rate the computer can generate them while doing heaving playouts. Since monte carlo tree's are pruned in very severe ways, in practice you cannot even come close to storing the entire tree even to a very modest depth. In theory MC probably would, after a few million years, grow a complete tree to some pretty good depth while discovering a complete solution. The storage cost is probably still prohibitive, as you can probably store only a few thousand moves worth of nodes on a large disk. You will constantly grow nodes and presumably for a book learning system you will stop storing nodes beyond some modest move number. If you look carefully at what MC search does, you will notice that the tree almost looks like a beam search. There is no significant depth for the vast majority of lines. If you don't know that, you have not been paying much attention to the discussion on MCTS. As has been mentioned, there may be ways to stretch this. The most obvious, other than direct compression, is to design your tree search to be heavy on CPU time whenever a reasonable compromise is possible and a decision must be made. For instance if you have a choice between doing super heavy playouts or looking at twice the number of nodes, and it's pretty much all the same, then choose the heavy playouts. If you can do 10 playouts instead of one and get almost as good results, then do that. In general emphasize the quality of the nodes over quantity whenever it's a reasaonble decision. - Don On Tue, May 12, 2009 at 5:10 PM, Dave Dyer <dd...@real-me.net> wrote: > > Storing an opening book for the first 10 moves requires > 33147774514824220000000000 nodes. Even with some reduction for symmetry, > I don't see that much memory becoming available anytime soon, and you still > have to evaluate them somehow. > > Actually storing a tree, except for extremely limited special cases, is not > even conceptually possible, and doesn't save much time. Consider that if > you store the tree you saw at the previous move, by the time you get to > use the stored tree 99% of it is useless because your opponent chose his > move. > > _______________________________________________ > 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/
