Chess Is Hard Even for a Single Player

Aravind, N.R. and Misra, N. and Mittal, H. (2022) Chess Is Hard Even for a Single Player. In: International Conference on Fun with Algorithms, FUN 2022, 30 May 2022 through 3 June 2022, Sicily.

[img] Text
Leibniz_International_Proceedings_in_Informatics.pdf - Published Version
Available under License Creative Commons Attribution.

Download (1MB)

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. © N.R. Aravind, Neeldhara Misra, and Harshil Mittal.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Aravind, N Rhttps://orcid.org/0000-0002-6590-7952
Item Type: Conference or Workshop Item (Paper)
Additional Information: The second author acknowledges support from IIT Gandhinagar and the SERB-MATRICS grant MTR/2017/001033. The second and third authors also acknowledge support from the SERBECR grant ECR/2018/002967.
Uncontrolled Keywords: board games, Chess, NP-complete, strategy
Subjects: Computer science
Computer science > Algorithm Analysis
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 28 Jun 2022 05:05
Last Modified: 28 Jun 2022 05:38
URI: http://raiith.iith.ac.in/id/eprint/9416
Publisher URL: https://doi.org/10.4230/LIPIcs.FUN.2022.5
OA policy: https://v2.sherpa.ac.uk/id/publication/29495
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9416 Statistics for this ePrint Item