AAAI Publications, Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
The Computational Complexity of Angry Birds and Similar Physics-Simulation Games
Matthew Stephenson, Jochen Renz, Xiaoyu Ge

Last modified: 2017-09-19

Abstract


This paper presents several proofs for the computational complexity of the popular physics-based puzzle game AngryBirds. 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 alsoNP-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

Full Text: PDF