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/
