LIPIcs.FUN.2018.14.pdf
- Filesize: 488 kB
- 16 pages
Document
Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.FUN.2018.14
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- computational complexity
- undecidable
- team games
- imperfect information
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games are (NP-)hard. In Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1-3 2014.
-
Jeffrey Bosboom, Erik D Demaine, Adam Hesterberg, Jayson Lynch, and Erik Waingarten. Mario kart is hard. In Japanese Conference on Discrete and Computational Geometry and Graphs, pages 49-59. Springer, 2015.
-
Erik D Demaine and Robert A Hearn. Constraint logic: A uniform framework for modeling computation as games. In Computational Complexity, 2008. CCC'08. 23rd Annual IEEE Conference on, pages 149-162. IEEE, 2008.
-
Erik D Demaine, Joshua Lockhart, and Jayson Lynch. The computational complexity of portal and other 3d video games. arXiv preprint arXiv:1611.10319, 2016.
-
Luciano Guala, Stefano Leucci, and Emanuele Natale. Bejeweled, candy crush and other match-three games are (np-) hard. In IEEE Conference on Computational Intelligence and Games, pages 1-8. IEEE, 2014.
-
Linus Hamilton. Braid is undecidable. arXiv preprint arXiv:1412.0784, 2014.
-
Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, Ltd., Natick, MA, USA, 2009.
- G. Peterson, J. Reif, and S. Azhar. Lower bounds for multiplayer noncooperative games of incomplete information. Computers and Mathematics with Applications, 41(7):957-992, 2001. URL: http://dx.doi.org/10.1016/S0898-1221(00)00333-3.
-
Gary L Peterson and John H Reif. Multiple-person alternation. In Foundations of Computer Science, 1979., 20th Annual Symposium on, pages 348-363. IEEE, 1979.
-
John H Reif. Universal games of incomplete information. In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 288-308. ACM, 1979.
-
John H Reif. The complexity of two-player games of incomplete information. Journal of computer and system sciences, 29(2):274-301, 1984.
-
Matthew Stephenson, Jochen Renz, and Xiaoyu Ge. The computational complexity of angry birds and similar physics-simulation games. 2017.
-
Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014.