Paper by Erik D. Demaine

Reference:

Josh Brunner, Erik D. Demaine, Della Hendrickson, and Julian Wellman, “Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard”, in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 33:1–33:14.

BibTeX

@InProceedings{RetroChess_ISAAC2020,
  AUTHOR        = {Josh Brunner and Erik D. Demaine and Della Hendrickson and Julian Wellman},
  authororig    = {Josh Brunner and Erik D. Demaine and Dylan Hendrickson and Julian Wellman},
  TITLE         = {Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard},
  BOOKTITLE     = {Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  bookurl       = {https://algo2020.comp.polyu.edu.hk/isaac.html},
  ADDRESS       = {Hong Kong},
  MONTH         = {December 14--18},
  YEAR          = 2020,
  PAGES         = {33:1--33:14},

  length        = {14 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.ISAAC.2020.17},
  dblp          = {https://dblp.org/rec/conf/isaac/BrunnerDHW20},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.ISAAC.2020.17">LIPIcs</A>, and from <A HREF="https://arxiv.org/abs/2010.09271">arXiv</A>.},
  updates       = {The figures of this paper use <A HREF="https://commons.wikimedia.org/wiki/Standard_chess_diagram">piece shapes from Wikimedia authored by Colin M.L. Burnett</A>, licensed under BSD License. See <A HREF="https://github.com/edemaine/svgtiler/tree/main/examples/chess">SVG Tiler chess definitions</A> for more details.},
}

Abstract:

We prove PSPACE-completeness of two classic types of Chess problems when generalized to n × n boards. A “retrograde” problem asks whether it is possible for a position to be reached from a natural starting position, i.e., whether the position is “valid” or “legal” or “reachable”. Most real-world retrograde Chess problems ask for the last few moves of such a sequence; we analyze the decision question which gets at the existence of an exponentially long move sequence. A “helpmate” problem asks whether it is possible for a player to become checkmated by any sequence of moves from a given position. A helpmate problem is essentially a cooperative form of Chess, where both players work together to cause a particular player to win; it also arises in regular Chess games, where a player who runs out of time (flags) loses only if they could ever possibly be checkmated from the current position (i.e., the helpmate problem has a solution). Our PSPACE-hardness reductions are from a variant of a puzzle game called Subway Shuffle.

Comments:

This paper is also available from LIPIcs, and from arXiv.

Updates:

The figures of this paper use piece shapes from Wikimedia authored by Colin M.L. Burnett, licensed under BSD License. See SVG Tiler chess definitions for more details.

Length:

The paper is 14 pages.

Availability:

The paper is available in PDF (778k).

See information on file formats.

[Google Scholar search]