3 ms·

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

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.

jeeyoungk 11y ago
That is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.
- jxy 11y ago
  Yes. Source here: http://senseis.xmp.net/?ComplexityOfGo http://senseis.xmp.net/?ComplexityOfGo
euyyn 11y ago
To be fair, AlphaGo can only play 19x19 Go. It's unrelated to solving NxN Go.