The Computational Complexity of Angry Birds (Extended Abstract)

Matthew Stephenson, Jochen Renz, Xiaoyu Ge

IJCAI 2020 pp. 5105-5109

doi:10.24963/IJCAI.2020/716 /ijcai/2020/stephenson2020ijcai-computational/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Stephenson et al. "The Computational Complexity of Angry Birds (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/716

Markdown

[Stephenson et al. "The Computational Complexity of Angry Birds (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/stephenson2020ijcai-computational/) doi:10.24963/IJCAI.2020/716

BibTeX

@inproceedings{stephenson2020ijcai-computational,
  title     = {{The Computational Complexity of Angry Birds (Extended Abstract)}},
  author    = {Stephenson, Matthew and Renz, Jochen and Ge, Xiaoyu},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {5105-5109},
  doi       = {10.24963/IJCAI.2020/716},
  url       = {https://mlanthology.org/ijcai/2020/stephenson2020ijcai-computational/}
}