Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard
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 ret...
| প্রধান লেখক: | , , , |
|---|---|
| অন্যান্য লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| প্রকাশিত: |
2022
|
| অনলাইন ব্যবহার করুন: | https://hdl.handle.net/1721.1/143960 |
| _version_ | 1826214948781424640 |
|---|---|
| author | Brunner, J Demaine, ED Hendrickson, D Wellman, J |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Brunner, J Demaine, ED Hendrickson, D Wellman, J |
| author_sort | Brunner, J |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:14:05Z |
| format | Article |
| id | mit-1721.1/143960 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:14:05Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1439602023-01-10T15:08:33Z Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard Brunner, J Demaine, ED Hendrickson, D Wellman, J Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2022-07-22T14:21:39Z 2022-07-22T14:21:39Z 2020-12-01 2022-07-22T14:19:21Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143960 Brunner, J, Demaine, ED, Hendrickson, D and Wellman, J. 2020. "Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard." Leibniz International Proceedings in Informatics, LIPIcs, 181. en 10.4230/LIPIcs.ISAAC.2020.17 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf DROPS |
| spellingShingle | Brunner, J Demaine, ED Hendrickson, D Wellman, J Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title | Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title_full | Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title_fullStr | Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title_full_unstemmed | Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title_short | Complexity of retrograde and helpmate chess problems: Even cooperative chess is hard |
| title_sort | complexity of retrograde and helpmate chess problems even cooperative chess is hard |
| url | https://hdl.handle.net/1721.1/143960 |
| work_keys_str_mv | AT brunnerj complexityofretrogradeandhelpmatechessproblemsevencooperativechessishard AT demaineed complexityofretrogradeandhelpmatechessproblemsevencooperativechessishard AT hendricksond complexityofretrogradeandhelpmatechessproblemsevencooperativechessishard AT wellmanj complexityofretrogradeandhelpmatechessproblemsevencooperativechessishard |