Show simple item record

dc.contributor.author
Bilò, Davide
dc.contributor.author
Gualà, Luciano
dc.contributor.author
Leucci, Stefano
dc.contributor.author
Proietti, Guido
dc.contributor.author
Rossi, Mirko
dc.contributor.editor
Ito, Hiro
dc.contributor.editor
Leonardi, Stefano
dc.contributor.editor
Pagli, Linda
dc.contributor.editor
Prencipe, Giuseppe
dc.date.accessioned
2018-12-11T17:46:07Z
dc.date.available
2018-12-07T19:41:20Z
dc.date.available
2018-12-11T17:46:07Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-067-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/lipics.fun.2018.8
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/309435
dc.identifier.doi
10.3929/ethz-b-000309435
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
peg duotaire
en_US
dc.subject
pspace-completeness
en_US
dc.subject
peg solitaire
en_US
dc.subject
two-player games
en_US
dc.title
On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
100
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
8
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
9th International Conference on Fun with Algorithms (FUN 2018)
en_US
ethz.event.location
Maddalena Island, Italy
en_US
ethz.event.date
June 13-15, 2018
en_US
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.date.deposited
2018-12-07T19:41:24Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-12-11T17:46:19Z
ethz.rosetta.lastUpdated
2018-12-11T17:46:19Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=On%20the%20PSPACE-completeness%20of%20Peg%20Duotaire%20and%20other%20Peg-Jumping%20Games&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2018&rft.volume=100&rft.spage=8&rft.issn=1868-8969&rft.au=Bil%C3%B2,%20Davide&Gual%C3%A0,%20Luciano&Leucci,%20Stefano&Proietti,%20Guido&Rossi,%20Mirko&rft.isbn=978-3-95977-067-5&rft.genre=proceeding&rft_id=info:doi/978-3-95977-067-5&rft.btitle=Proceedings%20of%20the%209th%20International%20Conference%20on%20Fun%20with%20Algorithms%20(FUN%202018)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record