Chess Is Hard Even for a Single Player

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



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.5.pdf
  • Filesize: 0.98 MB
  • 20 pages

Document Identifiers

Author Details

N.R. Aravind
  • Department of Computer Science and Engineering, Indian Institute of Technology, Hydrebad, India
Neeldhara Misra
  • Department of Computer Science and Engineering, Indian Institute of Technology, Gandhinagar, India
Harshil Mittal
  • Department of Computer Science and Engineering, Indian Institute of Technology, Gandhinagar, India

Acknowledgements

The authors would like to thank the anonymous reviewers of FUN 2022 for their useful feedback.

Cite AsGet BibTex

N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.5

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Design and analysis of algorithms
Keywords
  • chess
  • strategy
  • board games
  • NP-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess is hard even for a single player, 2022. URL: https://doi.org/10.48550/ARXIV.2203.14864.
  2. Elwyn R Berlekamp, John H Conway, and Richard K Guy. Winning ways for your mathematical plays. A K Peters, Natick, MA, 2 edition, January 2001. Google Scholar
  3. Josh Brunner, Erik D Demaine, Dylan Hendrickson, and Julian Wellman. Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard. arXiv preprint arXiv:2010.09271, 2020. Google Scholar
  4. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms, volume 5. Springer, 2015. Google Scholar
  5. Aviezri S Fraenkel and David Lichtenstein. Computing a Perfect Strategy for n × n Chess Requires Time Exponential in n. Journal of Combinatorial Theory, Series A, 31(2):199-214, 1981. Google Scholar
  6. Michael R Garey and David S Johnson. Computers and Intractability, volume 174. freeman San Francisco, 1979. Google Scholar
  7. Douglas Brent West et al. Introduction to Graph Theory, volume 2. Prentice hall Upper Saddle River, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail