Over the past few years the Angry Birds AI competition has been held in an attempt to develop intelligent agents that can successfully and efficiently solve levels for the video game Angry Birds. Many different agents and strategies have been developed to solve the complex and challenging physical reasoning problems associated with such a game. However, the performance of these various agents is non-transitive and varies significantly across different levels. No single agent dominates all situations presented, indicating that different procedures are better at solving certain levels than others. We therefore propose the construction of a hyper-agent that selects from a portfolio of sub-agents whichever it believes is best at solving any given level. This hyper-agent utilises key features that can be observed about a level to rank the available candidate algorithms based on their expected score.The proposed method exhibits a significant increase in performance over the individual sub-agents, and demonstrates the potential of using such an approach to solve other physics-based games or problems.

This paper presents several proofs for the computational complexity of the popular physics-based puzzle game AngryBirds. By using a combination of different gadgets within this game’s environment, we can demonstrate that the problem of solving Angry Birds levels is NP-hard. Proof of NP-hardness is by reduction from a known NP-complete problem, in this case 3-SAT. In addition, we are able to show that the original version of Angry Birds is within NP and therefore alsoNP-complete. These proofs can be extended to other physics-based games with similar mechanics.