License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.8
URN: urn:nbn:de:0030-drops-87994
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8799/
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido ; Rossi, Mirko

On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games

pdf-format:
LIPIcs-FUN-2018-8.pdf (1 MB)

Abstract

Peg Duotaire is a two-player version of the classical puzzle called Peg Solitaire. Players take turns making peg-jumping moves, and the first player which is left without available moves loses the game. Peg Duotaire has been studied from a combinatorial point of view and two versions of the game have been considered, namely the single- and the multi-hop variant. On the other hand, understanding the computational complexity of the game is explicitly mentioned as an open problem in the literature. We close this problem and prove that both versions of the game are PSPACE-complete. We also prove the PSPACE-completeness of other peg-jumping games where two players control pegs of different colors.

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2018:8799,
  author =	{Davide Bil{\`o} and Luciano Gual{\`a} and Stefano Leucci and Guido Proietti and Mirko Rossi},
  title =	{{On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8799},
  URN =		{urn:nbn:de:0030-drops-87994},
  doi =		{10.4230/LIPIcs.FUN.2018.8},
  annote =	{Keywords: peg duotaire, pspace-completeness, peg solitaire, two-player games}
}

Keywords: peg duotaire, pspace-completeness, peg solitaire, two-player games
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI