• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the Complexity of Connection Games

Thumbnail
Date
2016
Link to item file
https://hal.archives-ouvertes.fr/hal-01994450
Dewey
Probabilités et mathématiques appliquées
Sujet
PSPACE; Slither; Hex; Complexity; Havannah; Twixt
Journal issue
Theoretical Computer Science
Volume
644
Publication date
2016
Article pages
2-28
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2016.06.033
URI
https://basepub.dauphine.fr/handle/123456789/21006
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bonnet, Edouard
Jamain, Florian
Saffidine, Abdallah
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper, we study three connection games among the most widely played: havannah, twixt, and slither. We show that determining the outcome of an arbitrary input position is PSPACE-complete in all three cases. Our reductions are based on the popular graph problem generalized geography and on hex itself. We also consider the complexity of generalizations of hex parameterized by the length of the solution and establish that while short generalized hex is W[1]-hard, short hex is FPT. Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.