[computer-go] Monte-Carlo for Tactical Search

[Darren Cook]

> Global search is fine, as long as it does something more than just
> playing out games until the end - of course, even that might be a
> misconception of mine.
> And while others are working to improve the search in general, I'd like
> to think about the things needed in an evaluation function, ...

This is interesting because my viewpoint is very different: I think
global search should always search to the end of the game.

I also think this is exactly why monte carlo programs are doing well (or
at least better than would be expected from an algorithm that just plays
lots of random moves).

The reason why you *have* to search to the end of the game is that
evaluation before then is *too* difficult.

I've been toying over a proof of that statement, which goes something
like: you cannot evaluate accurately without knowing which endgame moves
are sente/gote, and you cannot know that (in the general case) without
doing life/death analysis. And life/death analysis is hard. Q.E.D.

(Now if that doesn't win me the Nobel Prize For Mathematics then I don't
know what will!)

Incidentally I came to this opinion a number of years ago by accident: I
set ManyFaces to self-play on level 1 from a midgame 19x19 position. It
finished the game in 1-2 seconds and the final score was considerably
more accurate than its score estimate had been at the start point. Level
1 is dumb but quick. But it turns out "dumb search to the end of the
game" beats sophistication.

Another name for this is quiescence search. And a go position is never
quiet until the dame have been filled. :-).

Darren