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

Authors Michael J. Coulombe, Jayson Lynch



PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.14.pdf
  • Filesize: 488 kB
  • 16 pages

Document Identifiers

Author Details

Michael J. Coulombe
  • MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA
Jayson Lynch
  • MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. Erik D Demaine, Joshua Lockhart, and Jayson Lynch. The computational complexity of portal and other 3d video games. arXiv preprint arXiv:1611.10319, 2016. Google Scholar
  5. 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. Google Scholar
  6. Linus Hamilton. Braid is undecidable. arXiv preprint arXiv:1412.0784, 2014. Google Scholar
  7. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, Ltd., Natick, MA, USA, 2009. Google Scholar
  8. 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.
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. John H Reif. The complexity of two-player games of incomplete information. Journal of computer and system sciences, 29(2):274-301, 1984. Google Scholar
  12. Matthew Stephenson, Jochen Renz, and Xiaoyu Ge. The computational complexity of angry birds and similar physics-simulation games. 2017. Google Scholar
  13. Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail