Re: [computer-go] citation

[Martin Girard <arister@xxxxxxxxxxxx>]

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

Reading n moves ahead is 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.

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

Ladder reading is so trivial it can be done in linear-time. Give me a break.

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

[Zzz]

--Martin

> 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/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/