Re: computer-go: Mathematical Go

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Thu, Oct 11, 2001 at 10:47:33AM +0900, Darren Cook wrote:
> >> If you're trying to write a strong go-playing program this book will not be
> >> any use. And for the part of the game it covers (very late endgame) brute
> >> force search is just as practical.
> >
> >Brute force search scales differently, so that on a sufficiently large
> >board, it's not necessarily true that brute force search is just as
> >practical.
> 
> By "practical" I meant brute force will give you an equally good move
> within tournament time limits (e.g. 10 secs/move) on just about all
> positions that will come up in real games.

You might not need to be able to analyze every situation on the board
to be useful. If you can just reliably show that some areas are cold
enough that the best move is not there, that could be very useful
input to your main search. Again, this is like what I do as a human go
player: "The biggest move in that area is no more than 3 points in
sente, so I won't worry about that area now." Such situations seem
pretty common, and not only in the late endgame.

> And is much easier to implement
> that CGT analysis.

I think that this is the real killer. It's very difficult to make a
program which automatically generates CGT trees for real Go positions.
But there seem to be no fundamental reasons that it can't be done.

> So my point was that until CGT can work further back in the endgame it is
> not needed for computer go. But I'm behind on my computer go reading, so
> maybe Martin and others are managing to do this now.

Until someone makes a powerful automated implementation, it'll be hard
to tell how early CGT can be applied in a typical game. My guess is
that it's moderately common for some areas to be provably too cold to
worry about even in the late middlegame. But it's too tedious to try
to do even one late middlegame by hand, and sampling 100 or even 10
games to see how common this is would be insane. So right now I can
only speculate.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"Those who study history are doomed to watch others repeat it."
    - Susan E. Cohen
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C