The Computational Complexity of Angry Birds (Extended Abstract)

Matthew Stephenson; Jochen Renz; Xiaoyu Ge

IJCAI 2020poster0 citations

The Computational Complexity of Angry Birds (Extended Abstract)

Matthew Stephenson, Jochen Renz, Xiaoyu Ge

Abstract

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.

Knowledge Representation and Reasoning: Computational Complexity of ReasoningMultidisciplinary Topics and Applications: Computer Games

BibTeX

@inproceedings{ijcai2020p716,
  title     = {The Computational Complexity of Angry Birds (Extended Abstract)},
  author    = {Stephenson, Matthew and Renz, Jochen and Ge, Xiaoyu},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {5105--5109},
  year      = {2020},
  month     = {7},
  note      = {Journal track},
  doi       = {10.24963/ijcai.2020/716},
  url       = {https://doi.org/10.24963/ijcai.2020/716},
}