Re: [computer-go] citation

[Jan Ramon <Jan.Ramon@xxxxxxxxxxxxxxxxx>]

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

I remember a paper on Computers&Games 2000 (hamamatsu, japan, Springer
Verlag Lecture notes in computer science) that proves
the ladder-reading is pspace-complete in the board size.

So except if you're paper is dealing with arbitrary board sizes, I think
it's better to go for other arguments, such as the classic comparison
with chess, the unclaimed prize money, etc.

Jan


On Mon, 12 Jul 2004, Martin Girard wrote:

> On Jul 12, 2004, at 17:11, Imran Ghory wrote:
> >
> > I haven't seen the proof, but I'd assume that the proof would say that
> > in the average (worst?) case developing a perfect evaluation function
> > would be PSPACE-complete rather than saying that Go was hard forAI.
>
> The proof is in Computational Complexity by Papadimitriou. It applies
> to a subcase of the rules (for example, we terminate when stones are
> taken), which means it is far more difficult than the average
> PSPACE-Complete problem, at least when it comes to encoding. And PSPACE
> completeness would only allow to solve problems (like life and death)
> since the number of moves must be bounded. And even then this wouldn't
> come close to solving Go as an optimization problem, without going
> through every possible game down to the last move one way or the other
> (!). In comparison, PSPACE completeness is a broad generalization of NP
> completeness, which is already known to be hair-pulling hard for every
> known AI technique.
>
> I suppose demonstrating that Go is harder for known AI techniques than
> hard problems generalized ten times over is enough to conclude that Go
> is hard itself.
>


                                          \\\|///
                                        \\  ^ ^  //
                                         (  @ @  )
+--------------------------------------oOOo-(_)-oOOo----+
|  Jan Ramon                                            |
|  Departement Computerwetenschappen K.U.Leuven         |
|  Celestijnenlaan 200 A 01.27                          |
|  3001 Heverlee                                        |
|  janr@xxxxxxxxxxxxxxxxx; jan.ramon@xxxxxxxxxxxxxxxxx  |
|  +32-16-32.75.60 (A01.27)                             |
|  +32-16-32.75.52 (Secretariaat deptcw)                |
|  +32-486-968518 (Gsm)                                 |
+-----------------------------------------------Oooo----+
                                        oooO   (   )
                                        (   )   ) /
                                         \ (   (_/
                                          \_)




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