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

[Thomas Johnson <tjohnson@xxxxxxxxxxxxxxxxxxxxxxxx>]

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

I wouldn't say "cannot".  Just because something's NP complete doesn't mean it
can't be done in polynomial time.  It just means that we don't "know" if it
can.  From what we've seen so far, NP complete problems seem to be exponential.
But nobody's proven it - either way.

For all we know, somebody may just come up with a solution for Go that shows
that NP complete problems can, in fact, be solved in polynomial time.  (Although
I doubt it.)

By the way, I would also be interested in a reference that shows Go to be an NP
complete problem.

And if Go is a NP complete problem, there may be a secret method that is valid
on all board sizes (polynomially - I think linearly is too strong) that
"approximates" the perfect NP complete solution.  There are a lot of
approximation algorithms that do wonders for NP complete problems.

There may be a secret trick for Go that wins "most" games - just not all.

-Tom J.

---
Thomas P. Johnson
Strategic Forecasting                       ph:  (607) 266-7636
Box 1034 Langmuir Lab                       fax: (607) 257-4279
95 Brown Rd.                  tjohnson@xxxxxxxxxxxxxxxxx
Ithaca, NY 14850            http://www.strategicforecasting.com