Renz, Jochen


Creating a Hyper-Agent for Solving Angry Birds Levels

AAAI Conferences

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.


The Computational Complexity of Angry Birds and Similar Physics-Simulation Games

AAAI Conferences

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.


Procedural Generation of Levels for Angry Birds Style Physics Games

AAAI Conferences

This paper presents a procedural generation algorithm for levels in physics-based puzzle games similar to Angry Birds. The proposed algorithm creates levels consisting of various self-contained structures placed throughout a 2D area. Each structure can be placed either on the ground or atop floating platforms within the available level space. These structures are created using a variety of different block types and do not require predefined substructures or composite elements. Target object locations are determined based on a combination of factors, including structural protection, occupancy estimation and overall dispersion. Experiments were performed in order to determine the ideal input parameters for generating desirable levels. The expressivity of the generator was also evaluated and the results show that the proposed method can generate a wide variety of interesting levels.


Creating a New Angry Birds Competition Track

AAAI Conferences

This paper introduces the new competitive track of the Angry Birds Artificial Intelligence Competition that was most recently hosted at IJCAI in August 2015. The goal of the competition is to inspire the creation of AI that can predict the effects of physical actions in the real world. Agents in the competitive track will have to focus on the AI techniques that will be useful in facing this challenge. The game the agents play is the popular Angry Birds created by Rovio. First, we discuss how we designed the competitive track and modelled it as an extensive form game. We show the pure strategy Nash Equilibrium for a single level of the competitive track. We then show that a single strategy is not dominant by defining simple cooperative strategies that outperform the optimal agent in the competition.


Angry Birds as a Challenge for Artificial Intelligence

AAAI Conferences

The Angry Birds AI Competition (aibirds.org) has been held annually since 2012 in conjunction with some of the major AI conferences, most recently with IJCAI 2015. The goal of the competition is to build AI agents that can play new Angry Birds levels as good as or better than the best human players. Successful agents should be able to quickly analyze new levels and to predict physical consequences of possible actions in order to select actions that solve a given level with a high score. Agents have no access to the game internal physics, but only receive screenshots of the live game. In this paper we describe why this problem is a challenge for AI, and why it is an important step towards building AI that can successfully interact with the real world. We also summarise some highlights of past competitions, including a new competition track we introduced recently.


The Angry Birds AI Competition

AI Magazine

The aim of the Angry Birds AI competition (AIBIRDS) is to build intelligent agents that can play new Angry Birds levels better than the best human players. This is surprisingly difficult for AI as it requires similar capabilities to what intelligent systems need for successfully interacting with the physical world, one of the grand challenges of AI. As such the competition offers a simplified and controlled environment for developing and testing the necessary AI technologies, a seamless integration of computer vision, machine learning, knowledge representation and reasoning, reasoning under uncertainty, planning, and heuristic search, among others. Over the past three years there have been significant improvements, but we are still a long way from reaching the ultimate aim and, thus, there are great opportunities for participants in this competition.


The Angry Birds AI Competition

AI Magazine

The aim of the Angry Birds AI competition (AIBIRDS) is to build intelligent agents that can play new Angry Birds levels better than the best human players. This is surprisingly difficult for AI as it requires similar capabilities to what intelligent systems need for successfully interacting with the physical world, one of the grand challenges of AI. As such the competition offers a simplified and controlled environment for developing and testing the necessary AI technologies, a seamless integration of computer vision, machine learning, knowledge representation and reasoning, reasoning under uncertainty, planning, and heuristic search, among others. Over the past three years there have been significant improvements, but we are still a long way from reaching the ultimate aim and, thus, there are great opportunities for participants in this competition.


AIBIRDS: The Angry Birds Artificial Intelligence Competition

AAAI Conferences

The Angry Birds AI Competition (aibirds.org) has been held in conjunction with the AI 2012, IJCAI 2013 and ECAI 2014 conferences and will be held again at the IJCAI 2015 conference. The declared goal of the competition is to build an AI agent that can play Angry Birds as good or better than the best human players. In this paper we describe why this is a very difficult problem, why it is a challenge for AI, and why it is an important step towards building AI that can successfully interact with the real world. We also summarise some highlights of past competitions, describe which methods were successful, and give an outlook to proposed variants of the competition. 


Qualitative Spatial Representation and Reasoning in Angry Birds: The Extended Rectangle Algebra

AAAI Conferences

Angry Birds is a popular video game where the task is to kill pigs protected by a structure composed of different building blocks that observe the laws of physics. The structure can be destroyed by shooting the angrybirds at it. The fewer birds we use and the more blocks we destroy, the higher the score. One approach to solve the game is by analysing the structure and identifying its strength and weaknesses. This can then be used to decide where to hit the structure with the birds. In this paper we use a qualitative spatial reasoning approach for this task. We develop a novel qualitative spatial calculus for representing and analysing the structure. Our calculus allows us to express and evaluate structural properties and rules, and to infer for each building block which of these properties and rules are satisfied. We use this to compute a heuristic value for each block that corresponds to how useful it is to hit that block. We evaluate our approach by comparing the suggested shot with other possible shots.


Efficient Extraction and Representation of Spatial Information from Video Data

AAAI Conferences

Vast amounts of video data are available on the weband are being generated daily using surveillancecameras or other sources. Being able to efficientlyanalyse and process this data is essential for a numberof different applications. We want to be ableto efficiently detect activities in these videos or beable to extract and store essential information containedin these videos for future use and easy searchand access. Cohn et al. (2012) proposed a comprehensiverepresentation of spatial features that canbe efficiently extracted from video and used forthese purposes. In this paper, we present a modifiedversion of this approach that is equally efficientand allows us to extract spatial informationwith much higher accuracy than previously possible.We present efficient algorithms both for extractingand storing spatial information from video,as well as for processing this information in orderto obtain useful spatial features. We evaluate ourapproach and demonstrate that the extracted spatialinformation is considerably more accurate than thatobtained from existing approaches.