TY - GEN
T1 - The computational complexity of angry birds and similar physics-simulation games
AU - Stephenson, Matthew
AU - Renz, Jochen
AU - Ge, Xiaoyu
N1 - Publisher Copyright:
Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2017
Y1 - 2017
N2 - 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’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.
AB - 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’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.
UR - http://www.scopus.com/inward/record.url?scp=85070843272&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85070843272
T3 - Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017
SP - 241
EP - 247
BT - Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017
PB - AAAI Press
T2 - 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2017
Y2 - 5 October 2017 through 9 October 2017
ER -