[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] citation


On Jul 15, 2004, at 6:50, Jan Ramon wrote:

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)

All your conceptions about NP-Completeness are utterly wrong. Forget everything you believe you know, down to the artihmetics, because obviously you don't even know how to count. Really. Go back to your elementary math books, then study algorithmics and complexity for a while. Then perhaps you'll start making some sense.

But if you must be told in very, very simple terms, exponential complexity is all about small differences in problem size making a huge difference in computation time.

Perhaps these links will help you understand the truth of this statement:
http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
http://www.certicom.com/resources/ecc_chall/challenge.html
Each one of them has a FAQ explaining while small gaps make huge differences for anything that is suprapolynomial.

And since you obviously have no clue what I explained in my last post is about, the difference in problem size is not 19 - 9; it is much larger than that. Read back my last post as many times as you need; eventually you'll get it, I suppose.

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.


Oh, sorry, I have this bad habit of explaining things in simple terms instead of providing pedantic references to prestigious publications in order to make a point. You have my most hypocritical apologies.

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.

Again, revise your maths:
If the size of a problem grows by f(x) for some parameter x (let it be the width of the board) and the complexity of the problem to solve grows by g(x) (where x is the size of the problem), then you get a progression of g(f(x)). In short, if the complexity of encoding Go grows in O(n^4) with the board size AND solving such a problem takes O(a^n), then it gives O(a^(kn^4)), which is awfully large.

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


I was talking about encoding size, dammit. I don't remember even remotely talking about algorithms.

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.


grrr...

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.



If it was that minor, the average SAT solver would be able to crack the RSA in no time on your average script-kiddie's desktop PC.

Again: Read back my previous post. Whenever you have the urge to reply so misinformed and ridiculous again, bash your head against a brick wall a few hundred times, then read back the post. Wash, rince, repeat. I heard you can exorcise demons that way.

Oh, and quit reading Slashdot. That helps too.

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


This assumes a few things, namely that both players will play sanren-sei . You can force your opponent into a fight any time, while it's pretty foolish to believe he'll let you play sanren-sei and do the same.

Face it; if there was an obvious winning strategy that didn't involve forcing moves and fighting, Go would be very boring. This is why deep reading is intrinsically linked to optimal strategy.

--Martin

Jan




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


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