License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.5
URN: urn:nbn:de:0030-drops-159753
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15975/
Go to the corresponding LIPIcs Volume Portal


Aravind, N.R. ; Misra, Neeldhara ; Mittal, Harshil

Chess Is Hard Even for a Single Player

pdf-format:
LIPIcs-FUN-2022-5.pdf (1.0 MB)


Abstract

We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left.
We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board.
Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.

BibTeX - Entry

@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5,
  author =	{Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil},
  title =	{{Chess Is Hard Even for a Single Player}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15975},
  URN =		{urn:nbn:de:0030-drops-159753},
  doi =		{10.4230/LIPIcs.FUN.2022.5},
  annote =	{Keywords: chess, strategy, board games, NP-complete}
}

Keywords: chess, strategy, board games, NP-complete
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022


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