CINXE.COM
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="csrf-token" content="5eFDFxWXAz5ndliiUEZyaW1pmiFIL9Ahyoy9prPX"> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17"> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <meta name="DC.Title" xml:lang="en" content="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard" > <meta name="DC.Creator.PersonalName" content="Brunner, Josh" > <meta name="DC.Creator.PersonalName" content="Demaine, Erik D." > <meta name="DC.Creator.PersonalName" content="Hendrickson, Dylan" > <meta name="DC.Creator.PersonalName" content="Wellman, Julian" > <meta name="DC.Subject" content="hardness" > <meta name="DC.Subject" content="board games" > <meta name="DC.Subject" content="PSPACE" > <meta name="DC.Date.created" scheme="ISO8601" content="2020-12-04" > <meta name="DC.Date.issued" scheme="ISO8601" content="2020-12-04" > <meta name="DC.Date.modified" scheme="ISO8601" content="2020-12-04" > <meta name="DC.Type" content="InProceedings" > <meta name="DC.Format" scheme="IMT" content="application/pdf" > <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-133618" > <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.ISAAC.2020.17" > <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17" > <meta name="DC.Source" content="31st International Symposium on Algorithms and Computation (ISAAC 2020)" > <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-181" > <meta name="DC.Language" scheme="ISO639-1" content="en" > <meta name="DC.Description" xml:lang="en" content="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." > <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/3.0/legalcode" > <meta name="citation_conference_title" content="31st International Symposium on Algorithms and Computation (ISAAC 2020)" > <meta name="citation_doi" content="10.4230/LIPIcs.ISAAC.2020.17" > <meta name="citation_firstpage" content="17:1" > <meta name="citation_lastpage" content="17:14" > <meta name="citation_title" content="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard" > <meta name="citation_language" content="en" > <meta name="citation_keyword" content="hardness" > <meta name="citation_keyword" content="board games" > <meta name="citation_keyword" content="PSPACE" > <meta name="citation_author" content="Brunner, Josh" > <meta name="citation_author_institution" content="Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" > <meta name="citation_author" content="Demaine, Erik D." > <meta name="citation_author_institution" content="Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" > <meta name="citation_author" content="Hendrickson, Dylan" > <meta name="citation_author_institution" content="Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" > <meta name="citation_author" content="Wellman, Julian" > <meta name="citation_author_institution" content="Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" > <meta name="citation_date" content="2020" > <meta name="citation_keyword" xml:lang="en" content="hardness" > <meta name="citation_keyword" xml:lang="en" content="board games" > <meta name="citation_keyword" xml:lang="en" content="PSPACE" > <meta name="citation_abstract_html_url" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17" > <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.pdf" > <meta name="citation_reference" content="Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch. Losing at Checkers is hard. In The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, pages 103-118. Princeton University Press, 2019." > <meta name="citation_reference" content="Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 × 1 Rush Hour with fixed blocks is PSPACE-complete. In Proceedings of the 10th International Conference on Fun with Algorithms, pages 7:1-7:14, La Maddalena, Italy, 2020." > <meta name="citation_reference" content="Marzio De Biasi and Tim Ophelders. Subway Shuffle is PSPACE-complete. Manuscript, February 2015. URL: http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/." > <meta name="citation_reference" content="FIDE. FIDE Laws of Chess. https://handbook.fide.com/chapter/E012018, 2018." > <meta name="citation_reference" content="Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n × n Chess requires time exponential in n. Journal of Combinatorial Theory, Series A, 31:199-214, 1981." > <meta name="citation_reference" content="Robert A. Hearn. Games, Puzzles, and Computation. PhD thesis, Massachusetts Institute of Technology, 2006. URL: http://erikdemaine.org/theses/bhearn.pdf." > <meta name="citation_reference" content="Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters/CRC Press, 2009." > <meta name="citation_reference" content="David Hooper and Kenneth Whyld. The Oxford Companion to Chess. Oxford University Press, 2nd edition, 1992." > <meta name="citation_reference" content="John Nunn. Solving in Style. Gambit Publications, 2nd edition, 2002." > <meta name="citation_reference" content="Yaroslav Shitov. Chess God’s number grows exponentially. arXiv:1409.1530, 2014. URL: http://arxiv.org/abs/1409.1530." > <meta name="citation_reference" content="Raymond M. Smullyan. The Chess Mysteries of Sherlock Holmes: 50 Tantalizing Problems of Chess Detection. Alfred A. Knopf, 1979. Reprinted by Dover, 2012." > <meta name="citation_reference" content="Raymond M. Smullyan. The Chess Mysteries of the Arabian Knights: 50 New Problems of Chess Detection. Alfred A. Knopf, 1981." > <meta name="citation_reference" content="James A. Storer. On the complexity of Chess. Journal of Computer and System Sciences, 27(1):77-100, 1983. URL: https://doi.org/10.1016/0022-0000(83)90030-2." > <meta name="citation_reference" content="Wikipedia. Chess problems. https://en.wikipedia.org/wiki/Chess_problem, 2020." > <meta name="citation_reference" content="Wikipedia. Helpmate. https://en.wikipedia.org/wiki/Helpmate, 2020." > <meta name="citation_publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <script type="application/ld+json"> { "@context": "https://schema.org/", "@type": "WebPage", "mainEntity": { "@type": "ScholarlyArticle", "url": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17", "headline": "Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard", "name": "Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard", "abstract": "We prove PSPACE-completeness of two classic types of Chess problems when generalized to n \u00d7 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.", "keywords": [ "hardness", "board games", "PSPACE" ], "author": [ { "@type": "Person", "name": "Brunner, Josh", "givenName": "Josh", "familyName": "Brunner", "email": "mailto:brunnerj@mit.edu", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Demaine, Erik D.", "givenName": "Erik D.", "familyName": "Demaine", "email": "mailto:edemaine@mit.edu", "sameAs": "https://orcid.org/0000-0003-3803-5703", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Hendrickson, Dylan", "givenName": "Dylan", "familyName": "Hendrickson", "email": "mailto:dylanhen@mit.edu", "sameAs": "https://orcid.org/0000-0002-9967-8799", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Wellman, Julian", "givenName": "Julian", "familyName": "Wellman", "email": "mailto:wellman@mit.edu", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" } ], "position": 17, "dateCreated": "2020-12-04", "datePublished": "2020-12-04", "isAccessibleForFree": true, "license": "https://creativecommons.org/licenses/by/3.0/legalcode", "copyrightHolder": [ { "@type": "Person", "name": "Brunner, Josh", "givenName": "Josh", "familyName": "Brunner", "email": "mailto:brunnerj@mit.edu", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Demaine, Erik D.", "givenName": "Erik D.", "familyName": "Demaine", "email": "mailto:edemaine@mit.edu", "sameAs": "https://orcid.org/0000-0003-3803-5703", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Hendrickson, Dylan", "givenName": "Dylan", "familyName": "Hendrickson", "email": "mailto:dylanhen@mit.edu", "sameAs": "https://orcid.org/0000-0002-9967-8799", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" }, { "@type": "Person", "name": "Wellman, Julian", "givenName": "Julian", "familyName": "Wellman", "email": "mailto:wellman@mit.edu", "affiliation": "Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA" } ], "copyrightYear": "2020", "creativeWorkStatus": "Published", "inLanguage": "en-US", "identifier": "https://doi.org/10.4230/LIPIcs.ISAAC.2020.17", "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "citation": [ "http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/", "https://handbook.fide.com/chapter/E012018", "http://erikdemaine.org/theses/bhearn.pdf", "http://arxiv.org/abs/1409.1530", "https://doi.org/10.1016/0022-0000(83)90030-2", "https://en.wikipedia.org/wiki/Chess_problem", "https://en.wikipedia.org/wiki/Helpmate" ], "pageStart": "17:1", "pageEnd": "17:14", "accessMode": "textual", "accessModeSufficient": "textual", "thumbnailUrl": "https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/thumbnails/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.png", "potentialAction": { "@type": "ReadAction", "target": { "@type": "EntryPoint", "urlTemplate": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17", "actionPlatform": [ "https://schema.org/DesktopWebPlatform", "https://schema.org/AndroidPlatform", "https://schema.org/IOSPlatform" ] } }, "isPartOf": { "@type": "PublicationVolume", "@id": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-181", "url": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-181", "volumeNumber": 181, "name": "31st International Symposium on Algorithms and Computation (ISAAC 2020)", "dateCreated": "2020-12-04", "datePublished": "2020-12-04", "editor": [ { "@type": "Person", "name": "Cao, Yixin", "givenName": "Yixin", "familyName": "Cao", "email": "mailto:yixin.cao@polyu.edu.hk", "sameAs": "https://orcid.org/0000-0002-6927-438X", "affiliation": "Hong Kong Polytechnic University, China" }, { "@type": "Person", "name": "Cheng, Siu-Wing", "givenName": "Siu-Wing", "familyName": "Cheng", "email": "mailto:scheng@cse.ust.hk", "sameAs": "https://orcid.org/0000-0002-3557-9935", "affiliation": "Hong Kong University of Science and Technology, China" }, { "@type": "Person", "name": "Li, Minming", "givenName": "Minming", "familyName": "Li", "email": "mailto:minming.li@cityu.edu.hk", "sameAs": "https://orcid.org/0000-0002-7370-6237", "affiliation": "City University of Hong Kong, China" } ], "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "isPartOf": { "@type": "BookSeries", "url": "https://drops.dagstuhl.de/entities/series/LIPIcs", "name": "Leibniz International Proceedings in Informatics", "issn": "1868-8969", "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "hasPart": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-181" } } } } </script> <link rel="alternate" type="application/xml" title="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard / XML" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/xml"> <link rel="alternate" type="application/x-bibtex" title="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard / BibTeX" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/bibtex/download"> <link rel="alternate" type="application/ld+json" title="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard / Schema.org" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/schema-org"> <link rel="alternate" type="application/xml" title="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard / OAI-DublinCore" href="/oai/?verb=GetRecord&metadataPrefix=oai_dc&identifier=13361"> <title>Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico"> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2025-01-23.1"> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height="62" alt="Schloss Dagstuhl - LZI - Logo"> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false" data-fix-width=" JournalsXXXXX "> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownArtifacts" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-braces-asterisk large-icon"></i> Artifacts </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/supplementary-materials"> Supplementary Materials (Software, Datasets, ...) </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/dblp"> dblp Artifacts </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/entities/journal/DARTS"> DARTS (Evaluated Artifacts) </a> </li> </ul> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="5eFDFxWXAz5ndliiUEZyaW1pmiFIL9Ahyoy9prPX" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2025-01-23.1" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.ISAAC.2020.17"> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.ISAAC.2020.17</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ISAAC.2020.17" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ISAAC.2020.17&title=Complexity+of+Retrograde+and+Helpmate+Chess+Problems%3A+Even+Cooperative+Chess+Is+Hard" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=Complexity+of+Retrograde+and+Helpmate+Chess+Problems%3A+Even+Cooperative+Chess+Is+Hard&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ISAAC.2020.17" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=Complexity+of+Retrograde+and+Helpmate+Chess+Problems%3A+Even+Cooperative+Chess+Is+Hard&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ISAAC.2020.17" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr> <h1>Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Brunner, Josh" class="name">Josh Brunner</a><!---->, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Demaine, Erik D." class="name">Erik D. Demaine</a> <a href="https://orcid.org/0000-0003-3803-5703"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a><!-- --><!---->, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Hendrickson, Dylan" class="name">Dylan Hendrickson</a> <a href="https://orcid.org/0000-0002-9967-8799"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a><!-- --><!---->, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Wellman, Julian" class="name">Julian Wellman</a><!----> </span> </h3> <hr> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-181">31st International Symposium on Algorithms and Computation (ISAAC 2020) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/ISAAC">International Symposium on Algorithms and Computation (ISAAC)</a> </li> <li class="mt-2">License: <a href="https://creativecommons.org/licenses/by/3.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 3.0 Unported license </a> </li> <li>Publication Date: 2020-12-04 </li> </ul> <hr> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/thumbnails/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.png" alt="Thumbnail PDF"></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol181-isaac2020/LIPIcs.ISAAC.2020.17/LIPIcs.ISAAC.2020.17.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.ISAAC.2020.17.pdf</a> <ul> <li>Filesize: 0.72 MB</li> <li>14 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2020.17">10.4230/LIPIcs.ISAAC.2020.17</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-133618&verb=FULL">urn:nbn:de:0030-drops-133618</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Josh Brunner</b></span> <a href="mailto:brunnerj@mit.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Brunner, Josh"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Erik D. Demaine</b></span> <a href="https://orcid.org/0000-0003-3803-5703"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="http://erikdemaine.org/"><i class="bi bi-house"></i></a> <a href="mailto:edemaine@mit.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Demaine, Erik D."><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Dylan Hendrickson</b></span> <a href="https://orcid.org/0000-0002-9967-8799"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:dylanhen@mit.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Hendrickson, Dylan"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Julian Wellman</b></span> <a href="mailto:wellman@mit.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Wellman, Julian"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA </li> </ul> </div> </section> <section class="acknowledgements mt-3"> <h2>Acknowledgements</h2> <div class="content"> This work was initiated during open problem solving in the MIT class on Algorithmic Lower Bounds: Fun with Hardness Proofs (6.892) in Spring 2019. We thank the other participants of that class - in particular, John Urschel - for related discussions and providing an inspiring atmosphere. </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As <span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman. Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2020.17">https://doi.org/10.4230/LIPIcs.ISAAC.2020.17</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{brunner_et_al:LIPIcs.ISAAC.2020.17, author = {Brunner, Josh and Demaine, Erik D. and Hendrickson, Dylan and Wellman, Julian}, title = {{Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17}, URN = {urn:nbn:de:0030-drops-133618}, doi = {10.4230/LIPIcs.ISAAC.2020.17}, annote = {Keywords: hardness, board games, PSPACE} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{brunner_et_al:LIPIcs.ISAAC.2020.17, author = {Brunner, Josh and Demaine, Erik D. and Hendrickson, Dylan and Wellman, Julian}, title = {{Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17}, URN = {urn:nbn:de:0030-drops-133618}, doi = {10.4230/LIPIcs.ISAAC.2020.17}, annote = {Keywords: hardness, board games, PSPACE} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <pre class="content" style="white-space: -moz-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word; white-space: pre-wrap;">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.</pre> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Theory of computation → Problems, reductions and completeness</li> </ul> </div> </div> <div class="keywords "> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>hardness</li> <li>board games</li> <li>PSPACE</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.ISAAC.2020.17" data-title="Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div> <!-- must be externally available for the series/journal case --> </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="related-version mt-3"> <h2>Related Versions</h2> <div class="content"> <ul> <li> The full version of this paper is available at <a href="https://arxiv.org/abs/2010.09271">https://arxiv.org/abs/2010.09271</a>.<br> </li> </ul> </div> </section> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch. Losing at Checkers is hard. In The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, pages 103-118. Princeton University Press, 2019. <a href="https://scholar.google.com/scholar?hl=en&q=Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch. Losing at Checkers is hard. In The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, pages 103-118. Princeton University Press, 2019." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 × 1 Rush Hour with fixed blocks is PSPACE-complete. In Proceedings of the 10th International Conference on Fun with Algorithms, pages 7:1-7:14, La Maddalena, Italy, 2020. <a href="https://scholar.google.com/scholar?hl=en&q=Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 × 1 Rush Hour with fixed blocks is PSPACE-complete. In Proceedings of the 10th International Conference on Fun with Algorithms, pages 7:1-7:14, La Maddalena, Italy, 2020." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Marzio De Biasi and Tim Ophelders. Subway Shuffle is PSPACE-complete. Manuscript, February 2015. URL: <a href="http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/">http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/</a>. </span> </li> <li> <span> FIDE. FIDE Laws of Chess. <a href="https://handbook.fide.com/chapter/E012018">https://handbook.fide.com/chapter/E012018</a>, 2018. </span> </li> <li> <span> Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n × n Chess requires time exponential in n. Journal of Combinatorial Theory, Series A, 31:199-214, 1981. <a href="https://scholar.google.com/scholar?hl=en&q=Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n × n Chess requires time exponential in n. Journal of Combinatorial Theory, Series A, 31:199-214, 1981." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Robert A. Hearn. Games, Puzzles, and Computation. PhD thesis, Massachusetts Institute of Technology, 2006. URL: <a href="http://erikdemaine.org/theses/bhearn.pdf">http://erikdemaine.org/theses/bhearn.pdf</a>. </span> </li> <li> <span> Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters/CRC Press, 2009. <a href="https://scholar.google.com/scholar?hl=en&q=Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters/CRC Press, 2009." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> David Hooper and Kenneth Whyld. The Oxford Companion to Chess. Oxford University Press, 2nd edition, 1992. <a href="https://scholar.google.com/scholar?hl=en&q=David Hooper and Kenneth Whyld. The Oxford Companion to Chess. Oxford University Press, 2nd edition, 1992." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> John Nunn. Solving in Style. Gambit Publications, 2nd edition, 2002. <a href="https://scholar.google.com/scholar?hl=en&q=John Nunn. Solving in Style. Gambit Publications, 2nd edition, 2002." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Yaroslav Shitov. Chess God’s number grows exponentially. arXiv:1409.1530, 2014. URL: <a href="http://arxiv.org/abs/1409.1530">http://arxiv.org/abs/1409.1530</a>. </span> </li> <li> <span> Raymond M. Smullyan. The Chess Mysteries of Sherlock Holmes: 50 Tantalizing Problems of Chess Detection. Alfred A. Knopf, 1979. Reprinted by Dover, 2012. <a href="https://scholar.google.com/scholar?hl=en&q=Raymond M. Smullyan. The Chess Mysteries of Sherlock Holmes: 50 Tantalizing Problems of Chess Detection. Alfred A. Knopf, 1979. Reprinted by Dover, 2012." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Raymond M. Smullyan. The Chess Mysteries of the Arabian Knights: 50 New Problems of Chess Detection. Alfred A. Knopf, 1981. <a href="https://scholar.google.com/scholar?hl=en&q=Raymond M. Smullyan. The Chess Mysteries of the Arabian Knights: 50 New Problems of Chess Detection. Alfred A. Knopf, 1981." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> James A. Storer. On the complexity of Chess. Journal of Computer and System Sciences, 27(1):77-100, 1983. URL: <a href="https://doi.org/10.1016/0022-0000(83)90030-2">https://doi.org/10.1016/0022-0000(83)90030-2</a>. </span> </li> <li> <span> Wikipedia. Chess problems. <a href="https://en.wikipedia.org/wiki/Chess_problem">https://en.wikipedia.org/wiki/Chess_problem</a>, 2020. </span> </li> <li> <span> Wikipedia. Helpmate. <a href="https://en.wikipedia.org/wiki/Helpmate">https://en.wikipedia.org/wiki/Helpmate</a>, 2020. </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60"> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60"> <br> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> <ul style="margin-top: -0.5em"> <li><a href="https://drops.dagstuhl.de/docs/about">More about DROPS</a></li> </ul> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/about">About DROPS</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2025-01-23.1"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.ISAAC.2020.17/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { app.methods.initTabLinks(); const innerAnchors =[]; $('.tab-pane').find('[id]').each(function() { innerAnchors.push(this.getAttribute('id')); }); const anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } }, initTabLinks: function() { $('[data-tab-link]').on('click', function(e) { e.preventDefault(); const $target = $(e.currentTarget); document.location.href = $target.attr('href'); document.location.reload(); }); }, }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>