Re: [computer-go] citation

[Jan Ramon <Jan.Ramon@xxxxxxxxxxxxxxxxx>]

On Wed, 14 Jul 2004, Martin Girard wrote:

>
> On Jul 14, 2004, at 4:09, Jan Ramon wrote:
>
> > 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.
> >
>
> I've got this very weird feeling you have no clue what you're talking
> about.
>
> May I suggest you read a bit on encoding problems into boolean circuits?
>
> For example: One of the reasons prime factoring is hard for SAT solvers
> is that circuits require up to O(n^2) (less if you use better
> multiplication algorithms, but still way above linear). You must of
> course take that into account when you evaluate the complexity of the
> problem. And we're only talking about a simple, one-dimensional
> multiplier circuit.
>
> Now imagine encoding all necessary mechanisms to handle even something
> as small as a 9x9 Go board, which is bidimensional and requires
> somewhat complicated rules handling. Of course you must encode shortage
> of liberties detection, ko detection, territory and prisoners counting,
> and have one board layer for each move down to the end of the game.
> Such a circuit would blow your computer's RAM. It might grow as fast as
> O(n4); therefore a circuit for a 19x19 board would be something like
> ((19^2)/(9^2))^4 = ~394.65 times larger. [correct me if my calculations
> are wrong]
>
> Of course one does not need to work with boolean circuits directly in a
> Go solver (fortunately), although for all practical purposes, an
> optimal engine would be just as complex in the worst case.

1. In my original mail, i said a reference to NP-hardness is not
recommendable as the only reference for an article arguing that 19x19 go
is difficult, and that intuitive arguments such as number of possiblities
etc. would be more interesting citations.
I explained in the above argument that 9 and 19 are small,
and so the NP-hardness proofs do not really prove much for 19x19 go (as
they apply to large numbers)
As in your arguments you do not seem to object against this (you dont
say anything about NP-hardness results), and as you adopt other means to
argue that 19x19 is more difficult than 9x9, I assume we agree on the
citation question.

2. On the other hand, forgive me for commenting on your arguments on some
less-on-topic points

2.a. NP-hardness etc. concerns the question if there exists a polynomial
time algorithm to solve some class of problems.  You claim that
complexity for go grows as fast as O(n^4), but this is still a polynomial
bound.  Even if you would be able to prove that the complexity would be
bounded O(n^1000), then you might have a very important theoretical
result if someone else proves that the same problem is NP-hard.

2.b. I don't think your proof resulting in the factor 394.65 is
technically correct, because for lower numbers, the lower order terms
might not be negligible.  Lets assume that we have an algorithm of
complexity c(n)=n^4+1000000n^3, which is O(n4). then we would have
c(19^2)/c(9^2)=8.85 < 394.65.  In fact, you are giving an upper bound on
the factor (assuming non-negative lower-order terms).

2.c. None of the above means that i think that 19x19 is not more complex
than 9x9 go.  I only stated that hardness proofs not necessarily prove
this.

2.d. I'm not sure prime factoring is related to go.  Still, I personally
believe that the cryptography literature assumes prime factoring to be
hard even if multiplication could be done in unit time O(1).  Anyway,
O(n^2) (with n the length of the numbers) for multiplication would only be
a minor factor for current factorization algorithms compared to the
complexity of the factoring itself.



> ...
> >   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).
>
> That last statement is rather trivial to demonstrate:
>
> Start up a fight that will drag through the whole board. Then either
> player must wipe out the other opponent in order to win, thus becoming
> a huge life and death problem. Of course capture problems are already
> known to be complete ten times over.

Especially for large board sizes, I'm not convinced that there is hard
evidence that reading is as global (relatively) as on a 19x19. Perhaps
there exists an optimal strategy on a 6019x6019 board which avoids
board-filling ladders? asume we play first on the 103^2 star points
(generalized san-sen-rei ;-) (4+6i,4+6j).  After that, all ladders are
broken, even if our opponent starts a large fight (except if some star
points would become ladder benders, which we could perhaps avoid)  Has
anyone shown that such a strategy would certainly be suboptimal?  If not,
perhaps it might be that board-filling ladder reading is not necessary to
play the game optimally from an empty board?
(of course, one can construct artificial problem in which it is necessary,
but these are 'different games/goals').

Jan




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