Re: computer-go: Insight of a human continued

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

On Sat, Sep 02, 2000 at 11:52:50AM +0200, Mark Boon wrote:
> 
> ----- Original Message -----
> From: Christian Nentwich <c.nentwich@xxxxxxxxxxxxxxxxx>
> To: <computer-go@xxxxxxxxxxxxxxxxx>
> Sent: Friday, September 01, 2000 3:20 PM
> Subject: computer-go: Insight of a human continued
> 
> >
> > My question is then:
> >   - Does anyone have a cutoff mechanism for reading which detects a
> > "natural
> >     point for tenuki" instead of reaching a tree-depth cutoff ? (I'm
> >     not talking about 5-liberties-is-safe either)
> 
> Yes, Goliath does it. It first uses a set of rules and patterns to see if a
> situation needs continuation. Next it keeps a value of what it estimates as
> the current value of a move. If the change in score of a move is well below
> this value, it will allow that side to move again to see what damage it
> threatens to do. If the damage is high, the other side is forced to come up
> with an answer. Otherwise the branch terminates.

Not to criticize the way Goliath does it, which is probably quite
effective in most cases, but people should realize that getting this
right in *all* cases is a nontrivial problem. Once you allow tenuki
into your game trees, you fall into the wild world of combinatorial
game theory. See the book _Mathematical Go_ by Elwyn Berlekamp and
David Wolfe, as well as various later papers by Berlekamp, Wolfe,
Martin Mueller, and others. (The book seems to've been published by at
least two publishers, Ishi Press and A K Peters, with at least two
subtitles, "Nightmares for the Professional Player" and "Chilling Gets
the Last Point"). Some highlights:
  * The value of a position is no longer simply a real number,
    but an element of a nontrivial group, with only partial
    ordering. So now you get to rewrite your search algorithms
    so that they can deal with the possibility that the values
    of some nodes can't be ranked directly.
  * Even once you have the values of a set of positions, it is
    in principle NP-hard to determine who wins. But note:
    ** In practice, this NP-hardness might not be a significant
       problem, since various approximate analyses seem to be
       very effective in real games. Certainly it's a less
       important problem than many of the other things which
       keep computers from playing Go effectively!
    ** The proof of NP-hardness given in _Mathematical Go_ is
       incorrect (requiring an exponentially large board in order
       to be exponentially hard), but Wolfe later made a different
       proof which does look correct.
  * When you try to analyze ko, things get hairier still.

If you want to see how hairy the group theory gets, take a look at the
Gamesman's Toolkit, available from Wolfe's web site at
<http://www.gac.edu/~wolfe/papers-games/>. Look at the logic used to
represent endpoint values, and to generalize the concept of "greater
than or equal to". This is what you use to replace what used to be a
simple floating point comparison in your program before you started
considering tenuki.:-|

Incidentally, this makes me marvel at how much secret stuff my brain
is doing to analyze Go. In my brain, at least, the analysis of tenuki
goes on below the level which is visible to introspection. I'm dimly
aware that it took me many games to learn to deal with tenuki. (I'm
AGA 2 dan now, so that was a while ago.:-) But what was my brain doing
during that time? And what lurks in my brain now, thinking about
tenuki without me being able to understand how?

Also incidentally, the Gamesman's Toolkit was the thing which
convinced me to switch my Go-playing program from C++ to Common Lisp.
Doing the Gamesman's Toolkit thing in Lisp is still messy, but it's
substantially less messy than doing it in C++ (or C!). I took this as
strong evidence that some fundamental problems in Go would be easier
to analyze in Lisp (or, probably, in a functional language like ML)
than in C++. I still think that's correct, but man, oh man, they're
still hard problems. I've been working on them a long time since then,
and I still haven't been able to turn my analysis into something which
plays a decent game of Go.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C