Re: [computer-go] Search = Bad!

[Tom Cooper <t.cooper@xxxxxxxxxxxxxx>]

At 10:43 23/02/2005, you wrote:

> > For go, a shortcut formula is even less likely, since its PSPACE 
> completeness
> > implies that any fast (subexponential) algorithm for go would translate to
> > a fast algorithm for *any* problem whatsoever solvable in polynomial space.
>
> This has come up before, but I think it worthwhile to repeat.
> Properties such as NP-completeness or PSPACE completeness are
> properties about decision problems.
>
> (from www.complexityzoo.com)
> ====
> decision problem: A problem for which the desired answer is a single
> bit (1 or 0, yes or no). For simplicity, theorists often restrict
> themselves to talking about decision problems.
>
> problem: A function from inputs to outputs, which we want an algorithm
> to compute. A crossword puzzle is not a problem; it's an instance. The
> set of all crossword puzzles is a problem.
> ====
>
> The PSPACE-completeness result in go is (AFAIK) related to
> ladder-reading, which is a problem in the sense described above. 19x19
> go is a problem instance, not a problem.
>
> Maarten.
> _______________________________________________
There are a number of holes in the argument that Go being p-space complete 
implies that
it is not practically possible to programme a perfect player for 19 x 19 go 
starting on
an empty board.  I don't think the distinction between a decision problem 
and the problem of
finding a winning move is one of these holes.  It is possible to find a 
winning move by asking
successively 'Is a1 a winning move?', 'Is a2 a winning move?' etc.

The holes I see are
1) It has not been proven that p-space complete problems are not p-time.
2) P-space complete is statement about the way the complexity of an 
infinite sequence of problems of
increasing size increases, and not a statement about the complexity of any 
one problem.  In
fact this is necessarily so: the solution to a single decision problem is 
just a single bit, and
which ever value it has, it only requires a trivial programme to print out 
this value.
3) It may be that even if there is a sequence of go problems of rapidly 
increasing complexity (as a
function of boardsize), that it is still possible to solve the open board 
problem more simply, though
this would involve the winner having an algorithm that not only wins, but
can stop the opponent steering the game into one of the P-space hard problems.

Personally I don't find any of these holes very plausible, and I don't 
expect to see a perfect 19x19
player within the next 50 years say.  I think the useful lesson to learn 
from this is that we have to
use heuristics in our programmes, but I think everyone does this anyway. 

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/