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.

Bilo, D., Guala, L., Leucci, S., Proietti, G., Rossi, M. (2018). On the PSPACE - Completeness of peg duotaire and other peg-jumping games. In 9th International Conference on Fun with Algorithms (FUN 2018) (pp.81-815) [10.4230/LIPIcs.FUN.2018.8].

On the PSPACE - Completeness of peg duotaire and other peg-jumping games

Guala L.;
2018-01-01

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.
9th International Conference on Fun with Algorithms (FUN 2018)
Rilevanza internazionale
contributo
2018
Settore INF/01 - INFORMATICA
English
peg duotaire, pspace-completeness, peg solitaire, two-player games
Intervento a convegno
Bilo, D., Guala, L., Leucci, S., Proietti, G., Rossi, M. (2018). On the PSPACE - Completeness of peg duotaire and other peg-jumping games. In 9th International Conference on Fun with Algorithms (FUN 2018) (pp.81-815) [10.4230/LIPIcs.FUN.2018.8].
Bilo, D; Guala, L; Leucci, S; Proietti, G; Rossi, M
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/208870
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact