The Computational Complexity of Angry Birds (Extended Abstract)

The Computational Complexity of Angry Birds (Extended Abstract)

Matthew Stephenson, Jochen Renz, Xiaoyu Ge

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Journal track. Pages 5105-5109. https://doi.org/10.24963/ijcai.2020/716

In this paper we present several proofs for the computational complexity of the physics-based video game Angry Birds. We are able to demonstrate that solving levels for different versions of Angry Birds is either NP-hard, PSPACE-hard, PSPACE-complete or EXPTIME-hard, depending on the maximum number of birds available and whether the game engine is deterministic or stochastic. We believe that this is the first time that a single-player video game has been proven EXPTIME-hard.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Multidisciplinary Topics and Applications: Computer Games