Paper by Erik D. Demaine

Josh Brunner, Erik D. Demaine, Dylan 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.

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.

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

The paper is 14 pages.

The paper is available in PDF (778k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated January 15, 2021 by Erik Demaine.