I would not be so quick to dismiss what Chrilly is saying. I have noticed that over time, in science, things blend together. For instance mtd(f) is a systematic way to think of aspiration search, (tampering with the alpha/beta window in a search) and helps us to appreciate how they are all pretty much variations of the same basic concepts.
I noticed a trend in computer chess towards throwing out more and more moves. Years ago it was only alpha/beta pruning but then later null move pruning, then other kinds of pruning and now the tree is being cut in many places. Chess search trees now look much more like the intial (highly selective) approach that was rejected just a few decades ago. UCT and Monte Carlo. It's not as much Monte Carlo any longer. It's turning more into an evaluation function. When it first started the play-outs were random, now they are semi random - essentially forming a binary evaluation function. In fact they ARE a binary evaluation function - since that exact node will never have this function directly applied to it again (with the standard UCT formulation.) So what we have is a best first search with an evaluation function! (I would still argue that some randomness is important - but I can't explain why in this email but a clue: it has to do with recovering from misconception if you can figure that out!) If you look at what mtd(f) is, it's not alpha/beta, it's more like a hybrid - a best first search that iterates. But it's only a hop, skip, and jump away from standard alpha/beta. It's not hard to imagine that with work, the Chrilly approach will start looking more like the UCT approach. After all, if anything, things have moved more TOWARDS the Chrilly approach and away from the initial things we tried in UCT/monte/carlo. Mabye in a few years we will look back and see that we started from a lot of different places and ended up at the same location. This happens all the time in science. In my opinion, the insight that Chrilly articulated was that all of sudden we are now all using some type of global search - the very idea was considered blasphemy just 2 or 3 years ago. - Don On Fri, 2007-04-06 at 13:54 +0200, Rémi Coulom wrote: > Chrilly wrote: > > I think on 9x9 the superiority of search based programms is now > > clearly demonstrated. Its only the question if UCT or Alpha-Beta is > > superior. > Hi Chrilly, > > Thanks for your report. > > The question of UCT versus Alpha-Beta is not open any more in my > opinion. The current state of the art of Monte Carlo tree search is > about 500 Elo points stronger than the version of Crazy Stone you tested > against. Do you believe you can easily catch up with those 500 Elo > points ? Also, I am convinced that UCT has tremendous potential for > further improvement. I have improved Crazy Stone by about 50 Elo points > per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 > is much more). I am very confident that I can easily improve it further > very much. > > Rémi > _______________________________________________ > 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/
