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

Re: [computer-go] citation


On Jul 12, 2004, at 17:11, Imran Ghory wrote:

On Mon, 12 Jul 2004, Martin Girard wrote:

On Jul 12, 2004, at 16:25, venghaus@xxxxxxxxxxxxxxxxx wrote:

I was wondering if anyone knew of a good citation for the claim that
Go is one of the grand challenges of AI

Look for the claim that Go is PSPACE-Complete. That pretty much follows.

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.

--Martin

Imran
--
http://bits.bris.ac.uk/imran
_______________________________________________
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/