Re: [computer-go] citation

[Jan Ramon <Jan.Ramon@xxxxxxxxxxxxxxxxx>]

On Tue, 13 Jul 2004, Martin Girard wrote:

> On Jul 13, 2004, at 4:28, Jan Ramon wrote:
> >
> > The problem with NP and PSPACE is that these usually say something
> > about
> > the complexity in function of the input (e.g. the size of the board).
> > For a fixed board size (19x19), the complexity is a constant (except if
> > you introduce other parameters such as "find the best move whose proof
> > requires only looking $n$ moves ahead" which is not a natural concept
> > in go).
>
> Besides, we are dealing with variable board sizes. Remember the
> majority of Go programs cannot compete at a decent level on a 19x19
> board, although they can on 9x9 and 13x13 ones. Since there isn't that
> much of a gap, it tells a lot about the complexity of the problem, at
> least using classical approaches.

this is not relevant for complexity results.  Complexity results
(NP-hardness, PSPace, ...) give complexity upper bounds as a function of
the problem size n, when n becomes _very large_.  e.g. as 9 and 19 are
small numbers, i don't think the mentioned complexity results explicitely
prove that 19x19 requires exponentially more time than 9x9.  After all,
your implementation might have a constant size-invariant cost (loading
the program into memory from very slow tape e.g.) which may exceed the
running on 19x19 on your super-fast processor. Such constant costs only
get (relatively) small when the cost depending exponentially on n becomes
very large.


besides,
> Reading n moves ahead is a natural concept in Go.
Reading exactly n moves ahead causes horizon-effect problems.
Most algorithms read ahead "until the group is saved or captured" (for a
ledder, e.g.)  As the horizon effect is very strong in Go (due to the
large number of irrelevant sente moves e.g.), many go search
algorithms use techniques such as lambda-search, abstract proof search,
quiesence search, etc. which are not limited to a fixed depth.
On the other hand, in go, one can prove many things (life e.g.) without
reading even 1 move.
Nevertheless, this was not my main point:  That was that you could
introduce other parameters for "problem size" of a particular class
of problems which are not the board size, and might allow similar
np-hardness results.  Unfortunately, i do not know of a very "natural"
problem size parameter and i do not know of any complexity result in go
based on such parameters.  Still, if you find such a parameter, you would
have to prove then that to solve the full game you would have to be able
to solve the full problem class for which you proved your complexity
result.  (e.g. the pspace-hardness result on generalized-ladder-reading
does not necessarily say something on the full game complexity as no one
has proven that the optimal strategy involves generalized ladder
reading).


jan


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