@inproceedings{1bf2cb050b4c421c93081f69f57481ad,
title = "The computational complexity of angry birds (Extended Abstract)",
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.",
keywords = "Angry Birds, AI and games, Computational complexity, Game playing, Physics simulation games",
author = "Matthew Stephenson and Jochen Renz and Xiaoyu Ge",
year = "2020",
doi = "10.24963/ijcai.2020/716",
language = "English",
series = "IJCAI International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",
pages = "5105--5109",
editor = "Christian Bessiere",
booktitle = "Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020",
note = "29th International Joint Conference on Artificial Intelligence, IJCAI 2020 ; Conference date: 01-01-2021",
}