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.7

1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

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

Abstract

Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.

Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  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.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}

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

Document

DOI: 10.4230/LIPIcs.ITP.2019.11

A Verified and Compositional Translation of LTL to Deterministic Rabin Automata

Authors: Julian Brunner, Benedikt Seidl, and Salomon Sickert

Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)

Abstract

We present a formalisation of the unified translation approach from linear temporal logic (LTL) to omega-automata from [Javier Esparza et al., 2018]. This approach decomposes LTL formulas into "simple" languages and allows a clear separation of concerns: first, we formalise the purely logical result yielding this decomposition; second, we develop a generic, executable, and expressive automata library providing necessary operations on automata to re-combine the "simple" languages; third, we instantiate this generic theory to obtain a construction for deterministic Rabin automata (DRA). We extract from this particular instantiation an executable tool translating LTL to DRAs. To the best of our knowledge this is the first verified translation of LTL to DRAs that is proven to be double-exponential in the worst case which asymptotically matches the known lower bound.

Cite as

Julian Brunner, Benedikt Seidl, and Salomon Sickert. A Verified and Compositional Translation of LTL to Deterministic Rabin Automata. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.ITP.2019.11,
  author =	{Brunner, Julian and Seidl, Benedikt and Sickert, Salomon},
  title =	{{A Verified and Compositional Translation of LTL to Deterministic Rabin Automata}},
  booktitle =	{10th International Conference on Interactive Theorem Proving (ITP 2019)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-122-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{141},
  editor =	{Harrison, John and O'Leary, John and Tolmach, Andrew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.11},
  URN =		{urn:nbn:de:0030-drops-110664},
  doi =		{10.4230/LIPIcs.ITP.2019.11},
  annote =	{Keywords: Automata Theory, Automata over Infinite Words, Deterministic Automata, Linear Temporal Logic, Model Checking, Verified Algorithms}
}

4 Search Results for "Brunner, Julian"

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

Abstract

Cite as

1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Abstract

Cite as

An Optimal Algorithm for Online Freeze-Tag

Abstract

Cite as

A Verified and Compositional Translation of LTL to Deterministic Rabin Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message