Re: computer-go: Two ways to program a GO-engine

[John Tromp <John.Tromp@xxxxxx>]

> This is one occasion when it is useful to call on the theoretical result,
> that Go is NP complete.  Therefore there cannot be this sort of hidden
> secret, valid on boards of all sizes, depending only on computation linear
> in the board size.
> 
> Charles
> 
Correction: GO is not NP complete. It's NP hard of course, but not in NP.

GO was shown PSPACE hard by sipser, and later shown EXPTIME complete in
a special sense (he assumed only basic ko and studied the question 
does black have a forced win) by Robson.

At the coming ComputerGames2000 conference in Japan, I'll present a paper
by Marcel Crasmaru and myself showing that Ladders in Go are
PSPACE complete. A sample ladder problem illustrating the reduction can
be found at the bottom of my Go page at http://www.cwi.nl/~tromp/go.html

regards,

-John