DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.17

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard

Authors: Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

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.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.FUN.2021.8

An Optimal Algorithm for Online Freeze-Tag

Authors: Josh Brunner and Julian Wellman

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract

In the freeze-tag problem, one active robot must wake up many frozen robots. The robots are considered as points in a metric space, where active robots move at a constant rate and activate other robots by visiting them. In the (time-dependent) online variant of the problem, each frozen robot is not revealed until a specified time. Hammar, Nilsson, and Persson have shown that no online algorithm can achieve a competitive ratio better than 7/3 for online freeze-tag, and posed the question of whether an O(1)-competitive algorithm exists. We provide a (1+√2)-competitive algorithm for online time-dependent freeze-tag, and show that this is the best possible: there does not exist an algorithm which achieves a lower competitive ratio on every metric space.

Cite as

Josh Brunner and Julian Wellman. An Optimal Algorithm for Online Freeze-Tag. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 8:1-8:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.8,
  author =	{Brunner, Josh and Wellman, Julian},
  title =	{{An Optimal Algorithm for Online Freeze-Tag}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{8:1--8:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.8},
  URN =		{urn:nbn:de:0030-drops-127693},
  doi =		{10.4230/LIPIcs.FUN.2021.8},
  annote =	{Keywords: Online algorithm, competitive ratio, freeze-tag}
}

Search Results

Documents authored by Wellman, Julian

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard

Abstract

Cite as

An Optimal Algorithm for Online Freeze-Tag

Abstract

Cite as

Thanks for your feedback!

Could not send message