Hacker News Reader

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.

That is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.

To be fair, AlphaGo can only play 19x19 Go. It's unrelated to solving NxN Go.