DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2018.14

Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games

Authors: Michael J. Coulombe and Jayson Lynch

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract

We show the undecidability of whether a team has a forced win in a number of well known video games including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart.To do so, we give a simplification of the Team Computation Game [Hearn and Demaine, 2009] and use that to give an undecidable abstract game on graphs. This graph game framework better captures the geometry and common constraints in many games and is thus a powerful tool for showing their computational complexity.

Cite as

Michael J. Coulombe and Jayson Lynch. Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{coulombe_et_al:LIPIcs.FUN.2018.14,
  author =	{Coulombe, Michael J. and Lynch, Jayson},
  title =	{{Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.14},
  URN =		{urn:nbn:de:0030-drops-88051},
  doi =		{10.4230/LIPIcs.FUN.2018.14},
  annote =	{Keywords: computational complexity, undecidable, team games, imperfect information}
}

Search Results

Documents authored by Coulombe, Michael J.

Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games

Abstract

Cite as

Thanks for your feedback!

Could not send message