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.
Type de document :
Communication dans un congrès
Advances in Computer Games, 2015, Leiden, Netherlands. 2015, Advances in Computer Games. 〈10.1007/978-3-319-27992-3_8〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01256660
Contributeur : Olivier Teytaud <>
Soumis le : vendredi 15 janvier 2016 - 10:50:42
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 07:10:13

Fichier

gocomplexities_draft.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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

Partager

Métriques

Consultations de la notice

600

Téléchargements de fichiers

215