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/