On Tue, 2009-02-17 at 23:29 -0800, David Fotland wrote: > It's not true that MCTS only goes a few ply. In 19x19 games on 32 CPU > cores, searching about 3 million play outs per move, Many Faces of Go > typically goes over 15 ply in the PV in the UCT tree.
That's what I meant when I said a few ply. Lazarus doesn't get that deep but it also goes several ply. A few years ago I got the impression that many people felt that anything other than local search was completely worthless because you couldn't go the 100+ ply you needed to understand a lot of things. Perhaps I exaggerate, but that was the gist. It's pretty clear of course that you cannot cover these 15 ply (or whatever) with anything resembling a brute force search, where other than alpha/beta pruning you look at every move to some goal depth with perhaps some kind of brief quies search. That's probably what the previous list member meant. > > I agree that it is much easier to reliably prune bad moves in go than > it is > in chess. > > Many Faces (pre MCTS) was a selective alpha-beta searcher. Switching > to > MCTS made it much stronger, so I think MCTS is better than alpha-beta > for > go. The reason is that to get any depth out of alpha-beta I had to > hard-prune most moves, and misses too many good moves. MCTS is full > width, > so misses nothing, and still searches twice as deep as the pruned > alpha-beta. Perhaps a dumber but faster evaluation function could do > better > than I did though. This may be the case. I believe that MCTS is just easier to think about and manage and I just have a hunch that a very similar thing could be formulated within the alpha/beta framework. Even if I'm right, there may be no benefit to doing this if they are (as I tentatively believe) more or less equivalent. But alpha/beta has one advantage, that perhaps could be taken advantage of, and that is the hard pruning you talk about. Even though it's "hard pruning" in some sense, it's fully admissible pruning and there are parts of the tree that MCTS always looks at, but that alpha/beta knows can be correctly rejected. Of course I appreciate the MCTS doesn't waste much time on those, but maybe it wastes enough time to make a difference, I don't know. I think of a proper alpha/beta search as full width too, it is just iterative. There is no move that gets un-admissibly and permanently pruned in alpha/beta even with modern techniques like null move and late move reductions. Those moves are effectively picked up and explored to greater depths on the NEXT iterations. Unless of course they are outside the alpha/beta window in which case it doesn't matter. So modern alpha/beta to me is looking more and more like the TS in MCTS, without the MC with at least one possible advantage. MCTS is really easy to reason about and control however and in comparison alpha/beta is temperamental. If some move in the tree that looks bad is really good, MCTS explores it gradually and in a controlled way and alpha/beta has to wait much longer to modify it's decision. And it's so well integrated with Monte Carlo and it's not clear how to do that so nicely with alpha/beta. So I am only open to the possibility that they are equivalent in some implementable sense, but I may be wrong about this. - Don > > Davdi _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
