Paper by Erik D. Demaine

Reference:

Aviv Adler, Hayashi Layers, Lily Chung, Michael Coulombe, Erik D. Demaine, Jenny Diomidova, Della Hendrickson, and Jayson Lynch, “This Game Is Not Going To Analyze Itself”, in Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2022), edited by Jin Akiyama, Hiro Ito, and Toshinori Sakai, Lecture Notes in Computer Science, volume 14364, Tokyo, Japan, September 9–11, 2022, pages 34–63.

BibTeX

@InProceedings{ThisGame_JCDCGGG2022full,
  AUTHOR        = {Aviv Adler and Hayashi Layers and Lily Chung and Michael Coulombe and Erik D. Demaine and Jenny Diomidova and Della Hendrickson and Jayson Lynch},
  TITLE         = {This Game Is Not Going To Analyze Itself},
  BOOKTITLE     = {Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2022)},
  bookurl       = {https://www.rs.tus.ac.jp/jcdcggg/},
  ADDRESS       = {Tokyo, Japan},
  MONTH         = {September 9--11},
  YEAR          = 2022,
  PAGES         = {34--63},
  EDITOR        = {Jin Akiyama and Hiro Ito and Toshinori Sakai},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 14364,

  length        = {30 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-032-00281-5_4},
  dblp          = {https://dblp.org/rec/conf/jcdcg/AdlerLCCDDHL22},
  comments      = {The paper is also available as <A HREF="https://arxiv.org/abs/2302.01145">arXiv:2302.01145</A> and from <A HREF="https://doi.org/10.1007/978-3-032-00281-5_4">SpringerLink</A>.},
  papers        = {ThisGame_JCDCGGG2022},
  replaces      = {ThisGame_JCDCGGG2022},
}

Abstract:

We analyze the puzzle video game This Game Is Not Going To Load Itself, where the player routes data packets of three different colors from given sources to given sinks of the correct color. Given the sources, sinks, and some previously placed arrow tiles, we prove that the game is in Σ^P₂; in NP for sources of equal period; and NP-complete for three colors and six equal-period sources with player input. Without player input, we prove that just simulating the game is in Δ^P₂, and both NP- and coNP-hard for two colors and many sources with different periods. On the other hand, we characterize which locations for three data sinks admit a perfect placement of arrow tiles that guarantee correct routing no matter the placement of the data sources, effectively solving most instances of the game as it is normally played.

Comments:

The paper is also available as arXiv:2302.01145 and from SpringerLink.

Length:

The paper is 30 pages.

Availability:

The paper is available in PDF (8532k).

See information on file formats.

[Google Scholar search]

Related papers:

ThisGame_JCDCGGG2022 (This Game Is Not Going To Analyze Itself)