DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.16

Tetris Is Not Competitive

Authors: Matthias Gehnen and Luca Venier

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

Abstract

In the video game Tetris, a player has to decide how to place pieces on a board that are revealed by the game one after another. We show that the missing information about the upcoming pieces is indeed crucial to a player’s success. We present a construction for piece sequences that force (online) players without or with a finite preview of upcoming pieces to lose while (offline) players who know the entire piece sequence can clear the board and continue to play. From a competitive analysis perspective, it follows that there cannot be any c-competitive online algorithm for various optimization goals in the context of playing Tetris. Furthermore, we improve existing results by providing a construction for piece sequences which force every player to lose for every possible board size with at least two columns. With this construction, we are also able to show that an instance with just 435 pieces is sufficient to force every player to lose on a standard-size board with ten columns and twenty rows.

Cite as

Matthias Gehnen and Luca Venier. Tetris Is Not Competitive. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.FUN.2024.16,
  author =	{Gehnen, Matthias and Venier, Luca},
  title =	{{Tetris Is Not Competitive}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{16:1--16:16},
  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.16},
  URN =		{urn:nbn:de:0030-drops-199242},
  doi =		{10.4230/LIPIcs.FUN.2024.16},
  annote =	{Keywords: Online Algorithms, Tetris}
}

Search Results

Documents authored by Venier, Luca

Tetris Is Not Competitive

Abstract

Cite as

Thanks for your feedback!

Could not send message