@inproceedings{9b5c4cac818d45b29261ac8177b5e1e6,
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.",
keywords = "Angry Birds, NP-hard, NP-complete, Computational Complexity, Physics games",
author = "Matthew Stephenson and Jochen Renz and Xiaoyu Ge",
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",
note = "13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017 ; Conference date: 05-10-2017 Through 09-10-2017",
}