11
$\begingroup$

What are the latest advances in theoretical complexity of Go?

I know some early works about the complexity of Go:

  1. "Go is polynomial-space hard" proved that Go is PSPACE-hard.

  2. "Ladders are PSPACE-complete" proved that ladders are PSPACE-complete.

  3. "Go endgames are PSPACE-hard" proved that Go endgames (or yose) is PSPACE-hard.

  4. "On the complexity of Tsume-Go" proved that the the complexity of Tsume-Go is NP-complete.

  5. "Go Complexities" proved that Atari Go is PSPACE-complete.

Since there are several rules of Go (They are different but similar), it is a little complicated to analysis it. We only know that the lower bound of the complexity of Go is PSPACE-hard and the upper bound of it is EXPSPACE.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The complexity of a GO-variant is studied in: A Note on Computational Complexity of Kill-all Go. And notably in 2018 the AlphaGo engine (with no human hard-coded heuristics) beated the 18-time world champion Lee Sedol. $\endgroup$
    – Marzio De Biasi
    Commented Mar 25, 2020 at 20:44
  • $\begingroup$ @MarzioDeBiasi I consulted the author the other day. However the latest work I found was published in 2015. $\endgroup$
    – Blanco
    Commented Mar 26, 2020 at 3:42
  • 1
    $\begingroup$ Have you searched on Google Scholar to find all recent papers that cite those? I would expect that any recent advances on the complexity of Go would cite those earlier papers on the complexity of Go. We expect you to do a significant amount of research before asking here. $\endgroup$
    – D.W.
    Commented Mar 26, 2020 at 4:29

1 Answer 1

Reset to default
7
$\begingroup$

The state of the art for the theoretical complexity of go is well summed up on Wikipedia, with relevant references.

The main remaining open problem is for rules using a superko, i.e. repeating any past position is forbidden. This is the rule used for instance in China and western countries. It is simple to state, but could bring some difficulties to actually play in some situations, as players need (in theory) to remember all the history of the game. In reality, these situations are so rare that it does not matter. For this rule, as you mention, we only know that deciding the winner from a given position is PSPACE-hard and in EXPSPACE.

On the other hand, it is known from Robson that Go with Japanese rules is EXPTIME-complete. These are the rules using local ko, only forbidding to repeat the last position, and declaring draw if a longer cycle occur. These rules have to include many special cases to settle the situation for particular configurations, and although they are considered more practical for human players, especially for beginners to learn about the ko rule, they are not elegant mathematically.

You can see a sketch of Robson's proof that Go with Japanese rules is EXPTIME-hard here, with fun go positions using ladders to encode boolean formulas.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.