HackerPapers

arXiv:1201.4995cs.CC

Gaming is a hard job, but someone has to do it!

Giovanni Viglietta

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble~3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.

arXiv comments
37 pages, 22 figures
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Jan 2012 to Jan 2012. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.