<p>The state of the art for the theoretical complexity of go is well summed up on <a href="https://en.wikipedia.org/wiki/Go_and_mathematics#Computational_complexity" rel="noreferrer">Wikipedia</a>, with relevant references.</p>

<p>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.</p>

<p>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.</p>

<p>You can see a sketch of Robson's proof that Go with Japanese rules is EXPTIME-hard <a href="https://senseis.xmp.net/?RobsonsProofThatGOIsEXPTimeHard" rel="noreferrer">here</a>, with fun go positions using ladders to encode boolean formulas.</p>

CC BY-SA 4.0
2020-03-26T00:39:59.710Z
2020-03-26T11:22:57.603Z
2020-03-26T11:22:57.603Z
Denis
<p>What are the latest advances in theoretical complexity of Go?</p>

<p>I know some early works about the complexity of Go:</p>

<ol>
<li><p><a href="https://dl.acm.org/doi/abs/10.1145/322186.322201" rel="nofollow noreferrer">"Go is polynomial-space hard"</a> proved that Go is PSPACE-hard.</p></li>
<li><p><a href="https://link.springer.com/chapter/10.1007/3-540-45579-5_16" rel="nofollow noreferrer">"Ladders are PSPACE-complete"</a> proved that ladders are PSPACE-complete.</p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8186" rel="nofollow noreferrer">"Go endgames are PSPACE-hard"</a> proved that Go endgames (or yose) is PSPACE-hard.</p></li>
<li><p><a href="https://link.springer.com/chapter/10.1007/3-540-48957-6_15" rel="nofollow noreferrer">"On the complexity of Tsume-Go"</a> proved that the the complexity of Tsume-Go is NP-complete.</p></li>
<li><p><a href="https://link.springer.com/chapter/10.1007/978-3-319-27992-3_8" rel="nofollow noreferrer">"Go Complexities"</a> proved that Atari Go is PSPACE-complete.</p></li>
</ol>

<p>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.</p>

CC BY-SA 4.0
2020-03-25T20:44:51.670Z
The complexity of a GO-variant is studied in: [A Note on Computational Complexity of Kill-all Go](https://arxiv.org/abs/1911.11405). And notably in 2018 the AlphaGo engine (with no human hard-coded heuristics) beated the 18-time world champion Lee Sedol.
Marzio De Biasi
CC BY-SA 4.0
2020-03-26T03:42:31.713Z
@MarzioDeBiasi I consulted the author the other day. However the latest work I found was published in 2015.
Blanco
CC BY-SA 4.0
2020-03-26T04:29:19.687Z
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.
D.W.
<complexity-classes><gt.game-theory><complexity>
The theoretical complexity of Go - The state of the art
Blanco
# The theoretical complexity of Go - The state of the art

(Asked by: username_0 on 2020-03-25)

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"](https://dl.acm.org/doi/abs/10.1145/322186.322201) proved that Go is PSPACE-hard.
2. ["Ladders are PSPACE-complete"](https://link.springer.com/chapter/10.1007/3-540-45579-5_16) proved that ladders are PSPACE-complete.
3. ["Go endgames are PSPACE-hard"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8186) proved that Go endgames (or yose) is PSPACE-hard.
4. ["On the complexity of Tsume-Go"](https://link.springer.com/chapter/10.1007/3-540-48957-6_15) proved that the the complexity of Tsume-Go is NP-complete.
5. ["Go Complexities"](https://link.springer.com/chapter/10.1007/978-3-319-27992-3_8) 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.

**Tags:** complexity-classes, gt.game-theory, complexity

> **Comments:**
> **username_1**: The complexity of a GO-variant is studied in: [A Note on Computational Complexity of Kill-all Go](https://arxiv.org/abs/1911.11405). And notably in 2018 the AlphaGo engine (with no human hard-coded heuristics) beated the 18-time world champion Lee Sedol.  
> **username_0**: @MarzioDeBiasi I consulted the author the other day. However the latest work I found was published in 2015.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2020-03-26. Score: 8 | Accepted answer

The state of the art for the theoretical complexity of go is well summed up on [Wikipedia](https://en.wikipedia.org/wiki/Go_and_mathematics#Computational_complexity), 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](https://senseis.xmp.net/?RobsonsProofThatGOIsEXPTimeHard), with fun go positions using ladders to encode boolean formulas.


---

