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

Re: [computer-go] citation

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.

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.
These are only meant to avoid trashing. They must still read through every possible move, even though they do it in a less wasteful way.

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.
As I explained above, board side itself is more than enough already.

Another one is the number of moves to read. Problems start showing a solution only from certain depth. Besides, you must take snapbacks and similar patterns into accounts, thus allowing problems to run very deep (at least larger than the investigated area).

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.

Of course, even for more conservative scenarios, fact is that most games are being decided in fights and many are lost because a player chose either to run from a fight he could win or pick up a fight he couldn't. Optimal reading abilities are 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/