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
- This paper is also available from LIPIcs, and from arXiv.
- 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.
- 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
Last updated August 19, 2022 by