[Retros] Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard

[Mario Velucchi - mario.velucchi.EU]

 [Submitted on 19 Oct 2020]
*https://arxiv.org/abs/2010.09271 <https://arxiv.org/abs/2010.09271>*
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative
Chess is Hard
Josh Brunner
<https://arxiv.org/search/cs?searchtype=author&query=Brunner%2C+J>, Erik D.
Demaine <https://arxiv.org/search/cs?searchtype=author&query=Demaine%2C+E+D>,
Dylan Hendrickson
<https://arxiv.org/search/cs?searchtype=author&query=Hendrickson%2C+D>, Julian
Wellman <https://arxiv.org/search/cs?searchtype=author&query=Wellman%2C+J>

We prove PSPACE-completeness of two classic types of Chess problems when
generalized to n-by-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: 14 pages, 12 figures
Subjects: Computational Complexity (cs.CC)
Cite as: arXiv:2010.09271 <https://arxiv.org/abs/2010.09271> [cs.CC]
  (or arXiv:2010.09271v1 <https://arxiv.org/abs/2010.09271v1> [cs.CC] for
this version)
Submission history From: Julian Wellman [view email
<https://arxiv.org/show-email/65d6963d/2010.09271>]
*[v1]* Mon, 19 Oct 2020 07:32:47 UTC (814 KB)

-- 
cordiali saluti
Mario Velucchi
[image: mario.velucchi.EU] <http://www.velucchi.net>
*Analisi** - Ricerca - Consulenza - Sviluppo Software*
Partita IVA  IT01977140506
eMail  mario at velucchi.net     web  www.velucchi.net

*Consulenza per Sviluppo Gestionali Personalizzati ed Applicativi Web
Sicurezza - Grafica e Pubblicità - Privati ed Aziende*
*MARIO VELUCCHI*
*Software Analyst and Developer*  *-*  *Computer Mathematician*
Via Emilia, 106  -  I-56121 Pisa  -  Italy
tel  +39 050.502400     cell  +39 348.7366652     fax  +39 06.233238786
eMail  mario at velucchi.eu     web  www.velucchi.eu
linkedin  it.linkedin.com/in/velucchi
avvertenze ai sensi del GDPR, General Data Protection Regulation -
Regolamento UE 2016/679: le informazioni contenute in questa email e/o nei
suoi allegati sono da considerarsi strettamente riservate. il loro utilizzo
è consentito esclusivamente al destinatario dell'email per le finalità
indicate nell'email stessa. qualora riceviate questa email senza esserne il
destinatario, vi preghiamo cortesemente di darcene notizia via email e di
procedere alla sua immediata distruzione. conservare l'email, divulgarla
anche in parte, distribuirla ad altri soggetti, copiarla, od utilizzarla
per finalità diverse, costituisce comportamento contrario ai principi
dettati del GDPR, General Data Protection Regulation - Regolamento UE
2016/679.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://pairlist1.pair.net/pipermail/retros/attachments/20210603/dd06911a/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2010.09271.pdf
Type: application/pdf
Size: 633390 bytes
Desc: not available
URL: <https://pairlist1.pair.net/pipermail/retros/attachments/20210603/dd06911a/attachment-0001.pdf>