@inproceedings{11fbfeeab1c04b0aa4fbdb6d95c6bca6,
title = "The computational complexity of angry birds and similar physics-simulation games",
abstract = "This paper presents several proofs for the computational complexity of the popular physics-based puzzle game Angry Birds. By using a combination of different gadgets within this game{\textquoteright}s environment, we can demonstrate that the problem of solving Angry Birds levels is NP-hard. Proof of NP-hardness is by reduction from a known NP-complete problem, in this case 3-SAT. In addition, we are able to show that the original version of Angry Birds is within NP and therefore also NP-complete. These proofs can be extended to other physics-based games with similar mechanics.",
author = "Matthew Stephenson and Jochen Renz and Xiaoyu Ge",
note = "Publisher Copyright: Copyright {\textcopyright} 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017 ; Conference date: 05-10-2017 Through 09-10-2017",
year = "2017",
language = "English",
series = "Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017",
publisher = "AAAI Press",
pages = "241--247",
booktitle = "Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017",
}