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.
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. Davdi > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of Don Dailey > Sent: Tuesday, February 17, 2009 11:58 AM > To: computer-go > Subject: RE: [computer-go] static evaluators for tree search > > On Tue, 2009-02-17 at 20:04 +0100, dave.de...@planet.nl wrote: > > A simple alfabeta searcher will only get a few plies deep on 19x19, so > > it won't be very useful (unless your static evaluation function is so > > good that it doesn't really need an alfabeta searcher) > > I have to say that I believe this is very simplistic, and a lot of > people have said things like this so you are certainly not alone. > > But how deep it goes is not particularly relevant, it's only a very > small part of the picture. Before MCTS programs were playing > "reasonably well" with continuous refinements to 1 ply searches. > > You can probably conceptually separate a tree searching program into 3 > parts, and in this sense alpha/beta is no different than MCTS: > > 1. search > 2. selectivity > 3. evaluation > > selectivity is a nebulous term which involves all kinds of decisions > about what to do inside the tree. It all boils down to 1 thing however, > when to stop and when not to (and possibly what score to assume.) > > Evaluation has always been the most important part of any tree searching > program and alpha/beta just doesn't work without it. Even if you > search to the very end of a game, such as tic-tac-toe, you must know > whether the game is a win, loss or draw, so you are forced to evaluate > in the non-recursive sense. When you cannot go to the end of the > game, which is true of any interesting game before it's played out, you > really must have a high quality evaluation. > > The interesting part of MCTS, is not the TS part, it's the MC part. > That's the part that does the evaluation. I am convinced that the tree > search part could be done in a number of ways which can be seen as more > or less equivalent. Even in the papers on MCTS the tree search was > shown to be a type of mini-max search. > > It's possible to structure alpha/beta to have incredibly low branching > factors, with modern chess programs for instance it is about 2. That > involves a lot of domain specific knowledge and assumptions about the > tree. This same thing can be done in GO and would also require a lot of > domain specific knowledge. That knowledge could be obtained with the > same methods used by MCTS, statistics gathered by playout analysis. The > evaluation function could also be merged into the nodes in a similar way > to MCTS. > > I believe what makes go different, is that you can be a lot more > selective than you can in chess, it's much easier to evaluate bad moves > in GO, but it's much harder to evaluate the quality of positions. > > You stated that alpha/beta can only go a few ply, but that is also true > of MCTS. It only goes a few ply unless you count the Monte Carlo part - > in which case you also do that with alpha/beta. > > So in my opinion the jury is still out. Is the "TS" in MCTS really so > fundamentally different that alpha/beta with selectivity? I'm not so > sure and I don't think anyone has really tried very hard probably due to > the wonderful success of the original bandit algorithm. > > There are a bunch of things in computer science that were rejected, and > then later found much success due to some simple discovery or even > research that showed people were just looking at it wrong, or missed > something relatively simple about it, or it simply went out of fashion > because something else came along that at the time appeared to better or > simpler and became the fad. That could easily happen here I think. > > > - 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/
