Re: computer-go: Mathematical Go

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

On Wed, Oct 10, 2001 at 07:05:36PM +0200, Mark Boon wrote:
> "The poison is in the tail", a popular Dutch expression. Pure brute-force is
> not affected by ko of course, but CGT is completely destroyed by it since it
> cancels any possible locality.

At one time I understood the loop-free CGT stuff in enough detail to
write a program which did arithmetic on CGT game values. My knowledge
of anything involving loops/kos is much more superficial, so maybe I'm
confused. But I was under the impression that many ko-containing
situations can be analyzed effectively by CGT. See e.g. Berlekamp's
article "The Economist's View of Combinatorial Games" in Nowakowski,
_Games Of No Chance_; or other articles referring to ko at
<http://www.markus-enzenberger.de/compgo_biblio/compgo_biblio.html>.

If you're just pointing out that for the worst cases of ko, CGT
doesn't help, then I agree with that. But similarly, for the worst
cases of other kinds of nonlocality, like a single life-and-death
struggle which dominates the entire game, CGT doesn't help. As far as
I can see, CGT is "completely destroyed by" ko any more than CGT is
"completely destroyed" by life and death or by any other source of
nonlocality, since it doesn't say anything about the average
complexity of cases involving ko.

Can you really show that no significant proportion of situations
involving ko can be effectively analyzed by decomposition into
subproblems? That seems counter to the way that I, as a human player,
analyze ko situations. Some ko situations do truly defy local
analysis, but many do not: some can be solved exactly down to the last
point, in other cases you can prove that X is the best move even
though you don't know its exact point value, and in others you can
prove that Y is a good enough move to win the game even though you
don't know whether it actually maximizes your point value. My
impression is that having local analysis in my mental toolkit
noticeably reduces the average-case complexity of 19x19 games. I'd
expect that the same would be true of computer analysis: CGT
algorithms should be able to help reduce average-case complexity.

-- 
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