The computational complexity of Angry Birds

DOI10.1016/j.artint.2019.103232zbMath1476.68224arXiv1812.07793OpenAlexW2997768066WikidataQ126410422 ScholiaQ126410422MaRDI QIDQ2302303

Jochen Renz, Matthew Stephenson, Xiaoyu Ge

Publication date: 26 February 2020

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.07793

zbMATH Keywords

computational complexitygame playingAI and gamesAngry Birdsphysics simulation games

Mathematics Subject Classification ID

Game theory (91A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in artificial intelligence (68T01) General theory of simulation (00A72) Agent technology and artificial intelligence (68T42)

Related Items (1)

Cooperating in video games? Impossible! Undecidability of team multiplayer games

Cites Work

• Gaming is a hard job, but someone has to do it!
• Computing a perfect strategy for nxn chess requires time exponential in n
• Pushing blocks is hard.
• Lemmings is PSPACE-complete
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• Tetris is Hard, Even to Approximate
• The Computational Complexity of Portal and Other 3D Video Games
• N by N Checkers is Exptime Complete
• Computational Complexity of Two-Dimensional Platform Games
• Provably Difficult Combinatorial Games
• Super Mario Bros. Is Harder/Easier than We Thought
• Computational Complexity
• Minesweeper is NP-complete.
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

This page was built for publication: The computational complexity of Angry Birds