首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games
  • 作者:Davide Bil{\`o ; Luciano Gual{\`a ; Stefano Leucci
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:100
  • 页码:8:1-8:15
  • DOI:10.4230/LIPIcs.FUN.2018.8
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:peg duotaire; pspace-completeness; peg solitaire; two-player games
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有