[computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Sat, 2007-04-07 at 01:12 +0200, Erik van der Werf wrote:
> On 4/6/07, Don Dailey <drd at mit.edu> wrote:
> > However, there is nothing wrong with using alpha beta
> > search with an evauation function that is not deterministic.
> 
> I agree that some limited amount of non-determinism isn't necessarily
> a bad thing, and in some cases it actually helps (e.g., when mobility
> is important, or to avoid the exploitation of repeatable blunders).
> However, do you really believe that this still holds if the variance
> causes a spread over the maximum range of possible values of the
> underlying ground-truths?

I don't understand your question.   I don't claim non-determinism
helps with alpha beta and I'm not recommending a fuzzy evaluation
function, I'm just saying it still works.  A deeper search will
produce better moves in general.

If you build a big tree and attach a score to all end nodes, 
the alpha beta mini-max procedure does not care how those
nodes got their score.    If the scores bear some resemblance
to reality, the search will probably return a relatively good
move.   Even if the scores are random, it could help if the
game is of the nature that maximizing your options is a good
thing - which is probably most games.  

Some randomness may have other advantages.  My theory is that 
in UCT, if your playouts have no randomness,  the search could
be locked into a deep conceptual misunderstanding that cannot
be recovered from.   This would be true of UCT constructed
with a deterministic evaluation function.   But it's only a
theory of mine.   

With alpha beta it's tricker, randomness introduces some 
difficulties that reduce the efficiency of alpha beta pruning
and make good move ordering more difficult.

- Don
 

> Erik