2026-07-24T05:44:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13361 2024-03-06T10:51:47Z ddc:004 open_access

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard Brunner, Josh Demaine, Erik D. Hendrickson, Dylan Wellman, Julian hardness board games PSPACE 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Josh Brunner and Erik D. Demaine and Dylan Hendrickson and Julian Wellman 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.17 urn:nbn:de:0030-drops-133618 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode