News for hackers. Stuff that matters.

A comment on What we learned in Seoul with AlphaGo. Parent comment

Re:What we learned in Seoul with AlphaGo by abecedarius on Thursday March 17, 2016 @02:23AM (#11302857)
NxN Go is PSPACE-complete.[1] That's an even bigger deal than NP-complete.

[1] According to some comment in /r/MachineLearning the other day. I haven't looked into it myself.

[ Parent | on HN ]
Re:What we learned in Seoul with AlphaGo by jeeyoungk on Thursday March 17, 2016 @05:05AM (#11303278)
That is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.
[ Parent | on HN ]
Re:What we learned in Seoul with AlphaGo by jxy on Thursday March 17, 2016 @06:12PM (#11308038)
Yes. Source here: http://senseis.xmp.net/?ComplexityOfGo
[ Parent | on HN ]
Re:What we learned in Seoul with AlphaGo by euyyn on Thursday March 17, 2016 @02:32PM (#11306485)
To be fair, AlphaGo can only play 19x19 Go. It's unrelated to solving NxN Go.
[ Parent | on HN ]