In this paper, we present a CBR approach for implementing an agent playing the well-known Angry Birds game. We adopt a preference-based procedure for constructing the case base, collecting experience from a random agent that continually explores the problemsolution space and improves the quality of already found solutions. As the retrieve phase involves nding a game scene similar to a given one, we develop a measure to assess the dissimilarity between two game scenes, which is based on solving appropriate linear assignment problems. A comparison of our agent with state-of-the-art computer programs shows promising results.
Angry Birds is a popular video game, in which the player has to shoot birds from a slingshot at pigs that are protected with objects from di erent types of materials, including wood, stone, and ice. Some birds have speci c capabilities that allow them to explode, split into several birds, pick up speed, etc. The game has di erent levels, each level coming with its speci c representation of pigs and objects hiding them. A level is solved when all the pigs are destroyed, and the goal of a player is to solve all the levels, keeping the number of shot birds as low as possible.
Since the rst edition of the Angry Birds AI competition in 2012, di erent approaches, ranging from qualitative representation and reasoning over simulation of game scenes to classical supervised machine learning algorithms, have been leveraged to build agents playing the game. In this paper, we develop an Angry Birds agent on the basis of the case-based reasoning (CBR) paradigm. To the best of our knowledge, this is the rst CBR approach to Angry Birds. One of the main components of our Angry Birds agent is a case base that stores problem-solution pairs, i.e., game scenes and appropriate best shots. We use a preference-based approach to build the case base, which compares di erent solutions for a given problem and maintains the better one.
The rest of the paper is organized as follows. In the next section, we brie y review some of the existing approaches for agents playing the Angry Birds game. In Section 3, we present our approach, and in Section 4, we analyze its performance experimentally. We conclude our work and outline possible directions for future work in Section 5.
Copyright © 2015 for this paper by its authors. Copying permitted for private and academic purposes. In Proceedings of the ICCBR 2015 Workshops. Frankfurt, Germany.
Most of the work so far has been concerned with the representation of the
different types of objects in Angry Birds. Lin et al. [
In [
Simulation-based approaches include the work by Polceanu and Buche [
The remaining category of approaches encompasses agents that leverage
di erent machine learning algorithms. In order to learn how to judge shots,
Narayan-Chen et al. [
We employ the CBR approach [
The core of a CBR system is a case base that stores previously encountered problems and associated solutions. In the context of Angry Birds, a single case should enclose a problem description part, with a representation of a game scene, covering the slingshot and all objects and pigs, and a solution part, containing the best shot one can execute in the given scene. The notion of an optimal solution in a given game scene, i.e., the shot that will lead to the highest change in score, is actually not well-de ned. Therefore, we need a procedure to nd solutions of at least close-to-optimal quality.
Inspired by the general framework of preference-based CBR [
In the context of Angry Birds, we concretise the approach as follows. We let arbitrary agents play in di erent game scenes and record the game scene along with the shot executed by the agent and the change in score. Once we encounter a game scene which is similar to another one already contained in the case base, and where the agent performs better, we replace the solution part of the old case (i.e., the shot) with the new one. The steps of the process of case base construction are outlined in Figure 1 as a owchart diagram. 3.2
The Angry Birds game involves di erent types of objects: a sling, hills, pigs,
blocks of stone, wood or ice, TNTs and birds with di erent capabilities
expressed in terms of colours, including red, yellow, blue, black, and white. The
Angry Birds Basic Game Playing Software [
Start
Observe a game Play a random shot and
observe the score Search for the most similar game scene to the played one Store the played game NO scene, the shot, and the score achieved
Similar game scene found?
Compare the score achieved Yes with the score corresponding
to the most similar scene NO
Achieved score > score of the most similar scene?
Yes Replace the shot and the score of the most similar scene with those of the new one
For describing the rectangles, we adopt the interval-based representation, where a rectangle in the 2-dimensional space R2 has the following form: R = [l; u] = [l1; u1] [l2; u2] ; where l = (l1; l2) and u = (u1; u2) are the coordinates of the lower left and upper right vertex of R, respectively. A complete game scene is represented through the set of the MBRs of all objects, together with their type when an object and colour when a bird.
Besides the game scene, collecting the cases also involves recording shots, which constitute the solution part of a case. In the Angry Birds Basic Game Playing Software, a shot is represented in the form of a 6-dimensional vector s = (x; y; dx; dy; tshot; ttap), where (x; y) and (x + dx; y + dy) are the coordinates of the focus and release point, respectively, tshot speci es the releasing and ttap the tapping time of the bird in milliseconds.
To illustrate how a case is constructed, we consider the situation shown in Figure 2. The start game scene is shown in the picture on the left. The resulting scene after performing the shot with the trajectory indicated by the red line is shown in the picture on the right, where the change in score is seen as well.
The case extracted from this scenario will contain the original scene, the performed shot and the achieved score, which we represent as follows: When the agent is playing, it gets a representation of the current game scene, searches the case base for the case with the most similar game scene and adopts its shot. Therefore, an appropriate measure to assess the similarity respectively dissimilarity between two game scenes is a key prerequisite for a successful agent. We compute the overall dissimilarity between two game scenes as the sum of the dissimilarities between their individual components: diss(scene1; scene2) = diss(scene1:Sling; scene2:Sling) + diss(scene1:BirdT ype; scene2:BirdT ype) + diss(scene1:Hills; scene2:Hills + diss(scene1:P igs; scene2:P igs) + diss(scene1:T N T s; scene2:T N T s) + diss(scene1:BlocksS ; scene2:BlocksS ) + diss(scene1:BlocksW ; scene2:BlocksW ) + diss(scene1:BlocksI ; scene2:BlocksI ) ; where BlocksS ; BlocksW and BlocksI denote blocks of stone, wood and ice, respectively.
The dissimilarity of two slings is just the dissimilarity between their MBRs. For the bird type, we compute the dissimilarity as follows: (0;
if the types are equal; constant; otherwise: diss(scene1:BirdT ype; scene2:BirdT ype) = Measuring the dissimilarity between two game scenes in each of the remaining components (hills, pigs, TNTs, and blocks) reduces to measuring the dissimilarity between the two sets of rectangles, with potentially di erent cardinality, corresponding to the MBRs surrounding them. This requires building pairs from the elements of the two sets, between which the dissimilarity is to be computed. The overall dissimilarity between the two sets is then the sum of the dissimilarities between all pairs. We formulate the task of computing the dissimilarity between two sets of rectangles as a (potentially unbalanced) linear assignment problem, where the agents are the elements of one set, tasks are the elements of the other set and the total cost of an assignment is the overall sum of the dissimilarities between all built pairs.
In the following, we proceed with the description of the measure we use
for assessing the dissimilarity between two rectangles, prior to detailing our
approach to computing the dissimilarity between two game scenes in the
abovementioned components through solving appropriate assignment problems.
Dissimilarity Between Two Rectangles. Di erent measures exists to assess
the dissimilarity between two rectangles in a p-dimensional space. We use the
vertex-type distance dv [
The linear assignment problem consists of mutually assigning objects of two sets A = fa1; : : : ; ang and B = fb1; : : : ; bng in a cost-optimal manner. Formally, assignment costs are de ned in terms of a matrix C = (cij ), where cij denotes the cost of assigning ai to bj (and vice versa), i:j 2 [N ] = f1; : : : ; N g. The goal, then, is to nd an assignment that minimizes the total cost with subject to the following constraints:
X X i2[N] j2[N]
cij xij xij = (1; if ai and bj are mutually assigned; 0; otherwise: ; j2[N] i2[N] X xij = 1 for all i 2 [N ];
X xij = 1 for all j 2 [N ];
The Hungarian algorithm [
In the simplest form of the assignment problem, the number of objects in A and B are equal. For the problem at hand, this assumption does not hold; instead, we are dealing with an unbalanced assignment problem. To handle such problems, one usually introduces dummy rows or columns in the cost matrix, depending on which number exceeds the other. Normally, the introduced entries are lled with zeros, but this does not t our purpose, because the addition or removal of objects will normally in uence the best shot in a scene. We overcome this issue by associating a penalty with objects that remain unassigned. The penalty term for an unassigned rectangle is its distance to the zero-perimeter rectangle located at the origin, i.e., R = [0; 0] [0; 0] : 4
We begin our experimental analysis with the construction of the case base, in which we proceed as follows. We run a random agent that chooses the coordinates of the shot to be executed fully at random, and we restrict ourself to the rst 21 levels of the \Poached Eggs" episode of Angry Birds. The agent plays each level several times and the cases from each level are rst collected in separate les. The distribution of the number of cases we gathered over the di erent levels of the game, shown in Table 1, was not uniform. That is, we dedicate more examples to harder levels than to easier ones. At the end, we combine all cases in one le, ending up with a case base of total size of 11; 703, which serves as the main case base for our agent.
After the case base was constructed, we rst tested the performance of our agent on the above-mentioned levels. To this end, we let the agent play 10 games and report the minimal, maximal, and average score for each level, together with the standard deviation, in Table 2.
To get an idea of how our agent performs in comparison to others, Figure 3 plots the average score of our agent from Table 2 together with the scores of the naive agent, the top-3 agents of the 2013 and 2014 participants of the AI competition, and the average scores of all 30 participants, on all 21 levels, based on the 2014 benchmarks provided on the aibirds.org website. This comparison shows that our agent clearly outperforms both the naive and the average agent in both per-level and total scores, and is even competitive to the top-3 agents. 5
We made use of CBR to build an Angry Birds playing agent. The results of an experimental study, in which we compared our agent with others, including the top-3 systems of previous AI competitions, are very promising, especially in light of the rather simple implementation of our agent so far. In fact, we are convinced that our agent's performance can be further enhanced through the collection of more cases and the re nement of the di erent steps of the CBR cycle.
More concretely, this work can be extended along the following directions. First, the real shape instead of the MBR representation can be used to represent the objects involved in the game. Second, a weighted version of the distance measure between game scenes can be learnt. Third, cases from levels of the game other than the ones of the \Poached Eggs" episode can be extracted to increase the size and coverage of the case base. Fourth, since our agent does not realize any adaptation of the retrieved solutions so far, a sophisticated adaptation strategy could be another means to improve performance.
Acknowledgments. This work has been supported by the German Research Foundation (DFG).