It is very clear that nonuniform random playouts is a far better evaluator than any reasonable static evaluation, given the same amount of time. Many people (including myself) spent decades creating static evaluations, using many techniques, and the best ones ended up with similar strength programs. The strongest MCTS programs are far stronger.
I put 25 years effort into a static evaluation, and replaced it with an MCTS system that I worked on for 6 months, and got about 5 stones strength improvement. MCTS playouts are not uniform random, so I can't say how they would perform, but why build a system with uniform random playouts, when it is so easy to do better? David > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of George Dahl > Sent: Tuesday, February 17, 2009 3:36 PM > To: computer-go > Subject: Re: [computer-go] Re: static evaluators for tree search > > Really? You think that doing 20-50 uniform random playouts and > estimating the win probability, when used as a leaf node evaluator in > tree search, will outperform anything else that uses same amount of > time? I must not understand you. What do you mean by static > evaluator? When I use the term, I mean something quite general, > basically any function of the board state that doesn't do explicit > lookahead. > > I guess 20-50 optimized playouts take so little time they would just > be so much faster than the sort of evaluators I might make that could > use hundreds of thousands of floating point multiplies. But more > towards that costly end of the regime, I think doing thousands of > random playouts would be really bad (but then maybe you could just > expand more nodes in the tree and do fewer playouts instead). I am > looking for higher quality, more costly evaluators than 50 MC > playouts. But that is a good point that I should compare to those > evaluators since if my evaluator is going to take more time it had > better show some other advantage. > > - George > > On Tue, Feb 17, 2009 at 6:13 PM, Darren Cook <dar...@dcook.org> wrote: > >> I think it would be much more informative to compare evaluator A and > >> evaluator B in the following way. > >> Make a bot that searched to a fixed depth d before then calling a > >> static evaluator (maybe this depth is 1 or 2 or something small). Try > >> and determine the strength of a bot using A and a bot using B as > >> accurately as possible against a variety of opponents. The better > >> evaluator is defined to be the one that results in the stronger bot. > > > > If you do this I'd suggest also including monte-carlo as one of your > > static evaluators. You want a score, but monte carlo usually returns > > information like "17 black wins, 3 white wins". However you can instead > > just sum ownership in the terminal positions, so if A1 is owned by black > > 15 times, white 5 times, count that as a point for black. If exactly > > equal ownership count the point for neither side. (Alternatively just > > sum black and white score of each terminal position.) > > > > You could have two or three versions using different number of playouts > > (with the result trade-off of more playouts means fewer nodes visited in > > the global search); I suspect 20-50 playouts will be optimum. > > > > My hunch is that monte carlo version will always out perform any static > > evaluation, given the same overall time (*). But it would be interesting > > to know. > > > > Darren > > > > *: Or run the experiment giving the static evaluation four times the > > clock time, on the assumption there is more potential for optimization > > in complex code. > > > > -- > > Darren Cook, Software Researcher/Developer > > http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic > > open source dictionary/semantic network) > > http://dcook.org/work/ (About me and my work) > > http://dcook.org/blogs.html (My blogs and articles) > > _______________________________________________ > > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
