Document Open Access Logo

The complexity of speedrunning video games

Author Manuel Lafond

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.27.pdf
  • Filesize: 2 MB
  • 19 pages

Document Identifiers

Author Details

Manuel Lafond
  • Department of Mathematics and Statistics, University of Ottawa, Canada

Funding

  • Lafond, Manuel: The author acknowledge the Natural Sciences and Engineering Research Council of Canada (NSERC) for the financial support of this project.

Cite As Get BibTex

Manuel Lafond. The complexity of speedrunning video games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.27

Abstract

Speedrunning is a popular activity in which the goal is to finish a video game as fast as possible. Players around the world spend hours each day on live stream, perfecting their skills to achieve a world record in well-known games such as Super Mario Bros, Castlevania or Mega Man. But human execution is not the only factor in a successful speed run. Some common techniques such as damage boosting or routing require careful planning to optimize time gains. In this paper, we show that optimizing these mechanics is in fact a profound algorithmic problem, as they lead to novel generalizations of the well-known NP-hard knapsack and feedback arc set problems.
We show that the problem of finding the optimal damage boosting locations in a game admits an FPTAS and is FPT in k + r, the number k of enemy types in the game and r the number of health refill locations. However, if the player is allowed to lose a life to regain health, the problem becomes hard to approximate within a factor 1/2 but admits a (1/2 - epsilon)-approximation with two lives. Damage boosting can also be solved in pseudo-polynomial time. As for routing, we show various hardness results, including W[2]-hardness in the time lost in a game, even on bounded treewidth stage graphs. On the positive side, we exhibit an FPT algorithm for stage graphs of bounded treewidth and bounded in-degree.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Approximation algorithms
  • parameterized complexity
  • video games
  • knapsack
  • feedback arc set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Classic damage data charts mega man 1 damage data chart. http://megaman.wikia.com/wiki/Mega_Man_1_Damage_Data_Chart. Accessed: 2018-02-21.
  2. Games done quick. https://gamesdonequick.com/. Accessed: 2018-02-21.
  3. Paola Alimonti and Viggo Kann. Hardness of approximating problems on cubic graphs. In Italian Conference on Algorithms and Complexity, pages 288-298. Springer, 1997. Google Scholar
  4. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms (TALG), 2(2):153-177, 2006. Google Scholar
  5. Greg Aloupis, Erik D Demaine, Alan Guo, and Giovanni Viglietta. Classic nintendo games are (computationally) hard. Theoretical Computer Science, 586:135-160, 2015. Google Scholar
  6. Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. On directed feedback vertex set parameterized by treewidth. arXiv preprint arXiv:1707.01470, 2017. Google Scholar
  7. 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
  8. Liming Cai and Jianer Chen. On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences, 54(3):465-474, 1997. Google Scholar
  9. Jianer Chen, Yang Liu, Songjian Lu, Barry O’sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM (JACM), 55(5):21, 2008. Google Scholar
  10. William Cook, László Lovász, Paul D Seymour, et al. Combinatorial optimization: papers from the DIMACS Special Year, volume 20. American Mathematical Soc., 1995. Google Scholar
  11. Graham Cormode. The hardness of the lemmings game, or oh no, more NP-completeness proofs. In Proceedings of Third International Conference on Fun with Algorithms, pages 65-76, 2004. Google Scholar
  12. Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4. Springer, 2015. Google Scholar
  13. Erik D Demaine, Giovanni Viglietta, and Aaron Williams. Super Mario Bros. is harder/easier than we thought. In Proceedings of Third International Conference on Fun with Algorithms, 2016. Google Scholar
  14. Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science &Business Media, 2012. Google Scholar
  15. Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin. Polynomial kernels for weighted problems. Journal of Computer and System Sciences, 84:1-10, 2017. Google Scholar
  16. Guy Even, J Seffi Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  17. Michal Forišek. Computational complexity of two-dimensional platform games. In International Conference on Fun with Algorithms, pages 214-227. Springer, 2010. Google Scholar
  18. Harold N Gabow, Zvi Galil, Thomas Spencer, and Robert E Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2):109-122, 1986. Google Scholar
  19. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 573-582. IEEE, 2008. Google Scholar
  20. Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm, 1992. Google Scholar
  21. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of operations research, 12(3):415-440, 1987. Google Scholar
  22. Richard Kaye. Minesweeper is NP-complete. The Mathematical Intelligencer, 22(2):9-15, 2000. Google Scholar
  23. Daniel Lokshtanov. New methods in parameterized algorithms and complexity. University of Bergen, Norway, 2009. Google Scholar
  24. Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014. Google Scholar
  25. Giovanni Viglietta. Lemmings is PSPACE-complete. Theoretical Computer Science, 586:120-134, 2015. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact