Chess is hard even for a single player

Show simple item record

dc.contributor.author Aravind, N. R.
dc.contributor.author Misra, Neeldhara
dc.contributor.author Mittal, Harshil
dc.date.accessioned 2022-04-06T05:31:53Z
dc.date.available 2022-04-06T05:31:53Z
dc.date.issued 2022-03
dc.identifier.citation Aravind, N. R.; Misra, Neeldhara and Mittal, Harshil, "Chess is hard even for a single player", arXiv, Cornell University Library, DOI: arXiv:2203.14864, Mar. 2022. en_US
dc.identifier.issn
dc.identifier.uri http://arxiv.org/abs/2203.14864
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/7642
dc.description.abstract We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on this http URL. The standard version of the game is played on a regular 8 x 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.
dc.description.statementofresponsibility by N. R. Aravind, Neeldhara Misra and Harshil Mittal
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.subject Chess en_US
dc.subject Strategy en_US
dc.subject Board games en_US
dc.subject NP-complete en_US
dc.title Chess is hard even for a single player en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account