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

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

On Mon, Oct 02, 2000 at 01:44:28PM +0100, TMCooper wrote:
> > 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
> 
> Do you know a reference for this result?   Thanks.  Tom.

a specific early reference, not available online: 
  "Go is Polynomial-Space Hard"
  David Lichtenstein and Michael Sipser
  Journal of the Association for Computing Machinery, 27:2, 393-401 (1980).

a specific stronger, more recent result, available online:
  "Go Endgames are PSPACE-hard"
  David Wolfe
  (See the general reference below for the complete citation.)

a general reference to results available online:
  "Online Computer Go Bibliography"
  http://home.t-online.de/home/markus.enzenberger/compgo_biblio.html

Things like the Lichtenstein paper aren't in the online bibliography
directly because that bibliography is only for works which are
available online. But a lot of the things in the online bibliography
are academic papers and theses, which tend to have extensive
bibliographies of their own. Therefore, you can often find things like
the Lichtenstein paper indirectly through the online bibliography.
(E.g., Wolfe cites Lichtenstein and Sipser.)

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