DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.10

How Did They Design This Game? Swish: Complexity and Unplayable Positions

Authors: Antoine Dailly, Pascal Lafourcade, and Gaël Marcadet

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

Swish is a competitive pattern recognition card-based game, in which players are trying to find a valid cards superposition from a set of cards, called a "swish". By the nature of the game, one may expect to easily recover the logic of the Swish’s designers. However, no justification appears to explain the number of cards, of duplicates, but also under which circumstances no player can find a swish. In this work, we formally investigate Swish. In the commercial version of the game, we observe that there exist large sets of cards with no swish, and find a construction to generate large sets of cards without swish. More importantly, in the general case with larger cards, we prove that Swish is NP-complete.

Cite as

Antoine Dailly, Pascal Lafourcade, and Gaël Marcadet. How Did They Design This Game? Swish: Complexity and Unplayable Positions. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dailly_et_al:LIPIcs.FUN.2024.10,
  author =	{Dailly, Antoine and Lafourcade, Pascal and Marcadet, Ga\"{e}l},
  title =	{{How Did They Design This Game? Swish: Complexity and Unplayable Positions}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.10},
  URN =		{urn:nbn:de:0030-drops-199185},
  doi =		{10.4230/LIPIcs.FUN.2024.10},
  annote =	{Keywords: Game, Complexity, Algorithms}
}

Search Results

Documents authored by Marcadet, Gaël

How Did They Design This Game? Swish: Complexity and Unplayable Positions

Abstract

Cite as

Thanks for your feedback!

Could not send message