Skip to Main content Skip to Navigation
Conference papers

Go Complexities

Abdallah Saffidine 1 Olivier Teytaud 2, 3 Shi-Jim yen 4 
3 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The game of Go is often said to exptime-complete. The result refers to classical Go under Japanese rules, but many variants of the problem exist and affect the complexity. We survey what is known on the computational complexity of Go and highlight challenging open problems. We also propose a few new results. In particular, we show that Atari-Go is pspace-complete and that hardness results for classical Go carry over to their Partially Observable variant.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01256660
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Friday, January 15, 2016 - 10:50:42 AM
Last modification on : Saturday, June 25, 2022 - 10:18:48 PM
Long-term archiving on: : Friday, November 11, 2016 - 7:10:13 AM

File

gocomplexities_draft.pdf
Files produced by the author(s)

Identifiers

Citation

Abdallah Saffidine, Olivier Teytaud, Shi-Jim yen. Go Complexities. Advances in Computer Games, 2015, Leiden, Netherlands. ⟨10.1007/978-3-319-27992-3_8⟩. ⟨hal-01256660⟩

Share

Metrics

Record views

470

Files downloads

449