\documentclass{llncs}
\usepackage{url}
\usepackage{textcomp}
\usepackage{amsmath}
\usepackage{amssymb}
\newcommand{\Program}{\mathcal P}
\newcommand{\ru}{r}
\newcommand{\naf}{not}
\newcommand{\answerSet}{\mathcal M^\Program}
\newcommand{\answerSetReduct}{\mathcal M^{\reductP}}
\newcommand{\groundLitP}{Lit}
\newcommand{\subsetReduct}{\mathcal R}
\newcommand{\reductP}{\mathcal P^{\mathcal R}}
\newcommand{\modelX}{\mathcal X}
\newcommand{\modelY}{\mathcal Y}
%%
\title{DualHEX: an extension of the AngryHEX Artificial Player for AngryBirds}
\author{Ana Oliveira da Costa, Isabelly Louredo Rocha, Slavco Elena}
\institute{Technische Universit\"at Dresden\\Computational Logic Group\\Seminar: Practical Planning for AngryBirds}
\begin{document}
\maketitle
\begin{abstract}
The goal of the Angry Birds AI competition is to build an intelligent agent which can complete the levels of the game better than human players. This task is very challenging, because humans have a good prediction about the physic world, while for computers it is hard to reason about an unknown environment. In this paper we describe our DualHEX AI agent, which is based on the AngryHEX agent of participants of the Angry Birds competition 2013. Our agent models the knowledge of the game by means of Answer Set Programming. In this project we improved the AngryHEX approach by extending the knowledge base of the domain. Our DualHEX agent plans a shot taking into consideration the current and the next bird. It compares the damage probability of both birds to discard targets that suits more the next bird features.
\end{abstract}
\begin{keywords}
Answer Set Programming, Artificial Intelligence, Angry Birds
\end{keywords}
\section{Introduction}\label{sec:introduction}
Angry Birds is a popular video game series which was released in December 2009 and immediately gained user’s attention.
The main goal of the game is to destroy pigs and damage their shelters, with the help of different types of birds. The number of birds is fixed for each level and every bird shoots only once per level. Pig’s shelters can represent very difficult constructions made of different materials like: ice, wood, stone and etc. %This materials will be affected differently by each type of bird. As an example..%
%In addition to this, %
Each bird has different abilities that are activated when the user taps on the playable area. For example, blue birds split in three smaller birds, yellow birds are speeding up and white birds drop a egg bomb.
The game is popular due to its colorful and fun interface, free basic use of the program and interesting and challenging tasks. The game respect the laws of physics and the problem of choosing the best target is not trivial.
The Angry Birds AI Competition was created to deal with this problem \cite{DBLP:journals/aim/RenzGGZ15}. The task of the competition is to create an artificial intelligent agent that can play the game better than human players and without human interference. The task itself include a lot of problems to be solved: analyzing the structures and birds abilities, planning the shot, developing the intelligent agent. Organization provides the basic game software that consists of:
\begin{itemize}
\item \textbf{computer vision component}, which segments the image and outputs a list of the minimum bounding rectangles of essential objects in the image and outputs real shapes instead.
\item \textbf{trajectory model}, which evaluate the trajectory that a bird will follow from the exact point.
\item \textbf{game playing component}, which represents the intelligent agent we need to create.
\end{itemize}
Our project is based on the work of the competition participants in 2013, the AngryHEX agent \cite{DBLP:conf/aiia/CalimeriFGIRW13}. Their approach was to create an agent which models the knowledge of the game by means of an Answer Set Programming knowledge base. They implemented around 300 rules and our goal is to improve their approach by extending the knowkedge base. In our implenentation, DualHEX, we consider the probability of damage on the objects in the game scene for two birds: current and next one, and use this knowledge to choose the most advantageous target.
% Missing: Why AI? Why AngryHEX? Beucase Ana thinks it is easier :D %
\section{Preliminaries}\label{sec:preliminaries}
In this section we will introduce the syntax and semantics of Answer Set Programming (ASP).
\subsection{Answer set programming (ASP)}
Answer Set Programming (ASP) is a declarative programming approach with roots in Logic Programming and Non-monotonic Reasoning \cite{conf/rweb/EiterIK09}. It is a fully declarative paradigm optimized for finding solutions of search problems \cite{journals/cacm/BrewkaET11}. Its declarative nature along with its non-monotonicity makes it a powerful tool to use in Knowledge Representation related problems \cite{journals/cacm/BrewkaET11,DBLP:conf/aiia/CalimeriFGIRW13}. In the ASP paradigm, solutions to a problem correspond to the answer sets of our problem's logic encoding. We will now define the syntax of ASP programs and later we introduce answer sets semantics.
\subsubsection{Syntax}
A general logic program is a finite set of general rules. A general rule is an expression of the form \cite{Gelfond91classicalnegation}:
\begin{align*}
a \gets b_1 \land \dots \land b_m \land \ \naf \ b_{m+1} \land \dots \land \ \naf \ b_n
\end{align*}
where $a$ and $b_j$, with $1 \leq j \leq n$, $ m \leq n$, are atoms; $\naf$ is negation as failure.
Rules are implicitly universally quantified over the set of variables that occur in them. A rule is composed by \emph{head} and \emph{body}. Given a general rule $\ru$ they are defined as follows:
\begin{itemize}
\item $head(\ru) := \{a\}$;
\item $body(\ru) := \{b_{l+1},\dots, b_m, \ \naf \ b_{m+1},\dots,\ \naf \ b_n \}$;
\end{itemize}
In this paper we use an extended version of general logic programs. The rules of our program will include classically negated atoms as well as more than one element in the head of the rule. Those rules are called extended rules with disjunction in the head and are defined as follows:
\begin{multline} \label{rule:extendedDisjunction}
A_1 \lor \dots \lor A_k \lor \ \naf \ A_{k+1} \lor \dots \lor \ \naf \ A_l \gets \\ B_{l+1} \land \dots \land B_m \land \ \naf \ B_{m+1} \land \dots \land \ \naf \ B_n
\end{multline}
where $A_i$ and $B_j$, with $1\leq i \leq l$ and $l < j \leq n$, are literals; $\naf$ is negation as failure; and $k \leq l \leq m \leq n$. The \emph{head} and \emph{body} of a rule $\ru$ of this form are:
\begin{itemize}
\item $head(\ru) := \{A_1,\dots, A_k, \ \naf\ A_{k+1},\dots,\ \naf \ A_l \}$;
\item $body(\ru) := \{B_{l+1},\dots, B_m, \ \naf \ B_{m+1},\dots,\ \naf \ B_n \}$;
\end{itemize}
A rule $\ru$ with no literals in the body is called a fact. In our setting, facts can be used to describe the expected target's damage after a specific type of bird hits it. This knowledge is known beforehand and it is independent of the current game state. We can encode it by adding the predicate \emph{damageProbability (Bird, Material, Damage)} where \emph{Bird}, \emph{Material} and \emph{Damage} are instantiated with bird types, materials (like wood or ice) and a numerical value that quantifies the expected damage when the first hits the second. In the example shown below we are defining that a yellow bird induces more damage in a wood structure than in an ice structure:
\begin{align*}
damageProbability(yellowbird, wood, 100) \leftarrow \\
damageProbability(yellowbird, ice, 10) \leftarrow
\end{align*}
A rule $\ru$ with no literals in the head is called constraint. Constraints are used to remove undesired answer sets from our solution. For example, in our Angry Birds encoding into ASP we want to have at most one definition per possible target in the list of admissible targets to shoot at. This can be encoded by defining the predicate \emph{target(Object, Trajectory)}. This predicate associates a trajectory to an object in the game field. The constraint shown below encodes this restriction:
\begin{align*}
\gets \ target(Obj1,Traj1) \land \ target(Obj2,Traj2) \land \ Obj1 \neq Obj2
\end{align*}
\subsubsection{Answer Set Semantics}
An ASP program describes properties of our problem's solution. We can then intuitively define the meaning of an ASP program as justifications for our intended solutions. This is the main idea behind stable model semantics for general logic programs introduced by Gelfond and Lifschitz \cite{Gelfond88thestable}. Later they defined answer set semantics \cite{Gelfond91classicalnegation} as an extension to stable model semantics to handle programs with rules as defined in \eqref{rule:extendedDisjunction}. We start by defining the answer set semantics of general programs without occurrences of $\naf$ (negation as failure), and later we explain how to extend this definition to programs with rules with occurrences of $\naf$ and disjunction in the head.
The semantics of an ASP program $\Program$ is defined over the set of the ground literals defined by the language of $\Program$. This set will be denoted by $\groundLitP$. Without loss of generality, a rule with variables can be seen as shorthand for the set of its ground instances \cite{Gelfond91classicalnegation}. Consider an arbitrary program $\Program$ defined by rules of the form:
\begin{align} \label{rule:simple}
A \gets B_1 \land \dots \land B_m
\end{align}
where $A$ and $B_j$, with $0\leq j \leq m$, are literals. The answer set $\answerSet$ of $\Program$ is the smallest subset of $\groundLitP$ such that:
\begin{itemize}
\item $\answerSet$ is a classical model of $\Program$;
\item all literals in $\answerSet$ are justified by some rule of $\Program$, i.e. each element in $\answerSet$ is in the head of some rule $\ru \in \Program$ such that $body(\ru)\subseteq \answerSet$.
\end{itemize}
This definition is a straightforward implementation of the idea of programs as justifications.
Lets now consider that our arbitrary program $\Program$ contains rules with occurrences of both classical negated atoms and negation as failure, i.e., $\Program$ is an extended program. We start by defining $\reductP$ as the reduct of $\Program$ with respect to the subset $\subsetReduct$ of $\groundLitP$.
Given a set of ground literals $\subsetReduct$ such that $\subsetReduct \subseteq \groundLitP$, $\reductP$ is the extended program obtained from $\Program$ by performing the following actions:
\begin{itemize}
\item if a literal $L \in \subsetReduct $, then delete each rule that has a formula $\naf\ L$ in its body,
\item delete all formulas of the form $\naf\ L$ in the bodies of the remaining rules.
\end{itemize}
$\reductP$ is a program containing only rules of the form \eqref{rule:simple}. Hence, its answer set is already defined. Lets assume that $\answerSetReduct$ is the answer set of $\reductP$, then if $\answerSetReduct = \subsetReduct$ we say that $\subsetReduct$ is an answer set of $\Program$. It is important to note that an extended logic program may have zero, one or more answer sets.
Lets now consider that our program $\Program$ contains rules with disjunction in the head and none of its rules have occurences of $\naf$. Rules of $\Program$ will be of the form:
\begin{align} \label{rule:simpleDisjunction}
A_1 \lor \dots \lor A_k \gets B_1 \land \dots \land B_m
\end{align}
where $A_i$ and $B_j$, with $0\leq i \leq k$ and $0\leq j \leq m$, are literals. The answer set of this program is defined in a similar way to a program with rules of form \eqref{rule:simple}.
The answer set $\answerSet$ of $\Program$ is the smallest subset of $\groundLitP$ such that:
\begin{itemize}
\item $\answerSet$ is a classical model of $\Program$;
\item for each rule $\ru$, if $body(\ru)\subseteq \answerSet$ then for some $1\leq i \leq k$ $A_i \in \answerSet$, i.e. our body justifies one or more literals in head's rule.
\end{itemize}
Finally, we define answer sets for extended rules with disjunction in the head. For an arbitrary program $\Program$ that contains such rules a set of ground literals $\subsetReduct$ is an answer set of $\Program$, if $\answerSetReduct = \subsetReduct$ where $\answerSetReduct$ is the answer set as defined above for the reduct of $\Program$ with respect to $\subsetReduct$.
\section{The DualHEX agent}
\subsection{Framework}
The framework used in our project is the combination of a basic framework given by the organizators of AI competition with extensions that were implemented by the participants of the AI competition 2013 \cite{DBLP:conf/aiia/CalimeriFGIRW13}. The basic framework interacts with the game while it is running on Google Chrome with Angry Birds' Extension. The framework's Game Server component processes this interaction. This reciprocity is implemented by the Proxy module, which consists of four commands: CLICK, DRAG, MOUSEWHEEL, SCREENSHOT.
The Vision Module divides the image, that is displayed to the user into small parts and recognizes the bounding box of every object. The bounding objects can be: all types of birds, different types of shelters, pigs and the slingshot. The AngryHEX team implemented an extension in the Vision module that improved the orientation recognition of the block.
Trajectory Module is needed to plan the shot. As soon as we have a target point, this module can be used to evaluate the trajectory that the bird will follow from the exact point. In the framework provided by the organizers of the competition, this module aims only at the center of the target object. Therefore, the AngryHEX team extended it with the ability of guiding the trajectory to the top or left side of the object.
The Server and Client Communications Ports allow the interaction between Game Server and Game Client. They receive commands from the server and after executing them send a feedback. In our implementation the AI Agent represents the DualHEX agent which is an extension of AngryHEX agent. AngryHEX added an Executor to the original Framewok that encodes the information about the environment into logic assertions and then runs the DLVHEX solver to compute a list of good shots based on that information and on the knowledge base. DLVHEX \cite{dlvhex} is an ASP solver that computes models of HEX-programs, which are answer set programs that allow integration of external computing sources.
\subsection{AngryHEX AI agent}
Our approach is based on the AngryHEX AI agent, which makes use of Answer Set Programming (ASP) to model the internal knowledge of the game. It has two main layers: Strategy and Tactic. The Strategy layer is implemented in Java and decides which level to play next. It considers the achieved scores and keeps track of the previously selected objects, in order to exclude them and to force a different tactic every time a level is played again. The Tactic layer does the reasoning by taking information about the current scene from the vision component and returning the best shot according to the result of the HEX program, which is declaratively implemented using ASP.
Our logic program has about 300 statements represented by rules and facts encoding fixed knowledge of the domain. We would like to introduce some examples.
Facts in the program can describe different types of objects. For example, the following fact encodes all type of birds: white, red, blue, yellow and black.
\begin{align*}
birdType(Bird)\leftarrow
\end{align*}
In the knowledge base there are three types of trajectories: low, high and egg. Trajectory egg is used when the white bird is in the slingshot, because this bird has the property to shoot with an egg bomb. Low and high trajectories are used to aim at the left and top side of an object, respectively. Therefore, facts to represent different trajectories were introduced. They respect the following schema:
\begin{align*}
trajectory(TrajectoryType)\leftarrow
\end{align*}
Targets are represented by pigs, different kinds of material or TNT, as it is described by instances of the following fact:
\begin{align*}
objectType(Obj,ObjMaterialType)\leftarrow
\end{align*}
Facts are also introduced to count the value of energy which can be spread from an object to another after the execution of a shot. Those are instances of the following:
\begin{align*}
energyLoss(Bird,ObjectType,EnergyLoss)\leftarrow
\end{align*}
Besides that, we can describe that a specific bird is not good for the object stone by listing an instance of the fact:
\begin{align*}
nogoodForStone(Bird)\leftarrow
\end{align*}
The importance of the target object to be destroyed is also estimated, in order to calculate the damage of a fall:
\begin{align*}
materialFallImportance(MaterialType,FallImportance)\leftarrow
\end{align*}
Rules in the program can be represented as normal rules with literals in their head and body, rules containing negation as failure, constraints and weak constraints. To calculate the percentage perturbations on tap time depending on bird type we have the rule
\begin{align*}
tap(Perturbation)\leftarrow birdType(Bird)
\end{align*}
There are three different types of damage for a target object. \textit{pushDamage}, when it has been pushed by another object. \textit{fallDamage}, when the target is on the top of an object which has been shot. \textit{directDamage}, when the bird is shot directly on the target. The rules to describe this types of damage are similar to each other, so here we will only describe how \textit{pushDamage} is evaluated.
\begin{align*}
fallDamage(Obj,P\_N) \leftarrow & directDamage(RemovedObj,P\_R,E), \\
& E >= 10, \\
& P\_R > 0, \\
& ot(RemovedObj,Obj), \\
& objectType(Obj,T), \\
& materialFallImportance(T,P\_N), \\
& P\_temp = P\_R * P\_N, P = P\_temp / 100. \\
\end{align*}
First of all, the damage probability of a direct shoot on the removed object and the energy left is computed. The removed object can be any object that will suffer damage according to our prediction. Then, we check whether this probability and energy are greater than zero and ten, respectively. After that, we check whether our object is on the top of the removed object. If so, the damage probability of the object which is on the top is computed by checking its type and computing the fall importance of an object with such a material type. This material fall importance is defined by facts and it's known, for instance, that the fall of an object with stone material is more important than one with ice.
All rules of damage follow the same structure. The object, we want to evaluate the damage for, is compared with the other objects from our scene, because in game's structures all objects are interacting with eact other. The damage probability of a given object is computed in the last line of the rules, where its probability of damage is multiplied by the probability of the objects related to it. However, that is not the case for the \textit{fallDamage} rule, because, in our point of view, the target that falls doesn't influence the other objects from our scene.
\subsection{AngryHEX extension}
A suggestion of improvement for the AngryHEX agent reported by its developers in \cite{DBLP:conf/aiia/CalimeriFGIRW13} was to introduce the planning of multiple shots based on the order of the birds that must be shot. We liked this suggestion and decided to work on it. In our point of view, when people try to solve a level they plan according to the available birds to shoot. One possible strategy is to use each bird to hit the material that it affects the most. As AngryHEX AI agent selects a random target from the answer set that result from the reasoning on the knowledge base and scene information, we would like to improve this approach by minimizing this answer set. This can be done by also considering the next bird to be shot. In other words, we want to remove from our solutions the targets with high probability of damage if hit by the next bird in line. However, this is advantageous only if the birds are of different type.
Our idea was to make a small change to guarantee that it will not have a big impact on the overall performance. We decided to restrict the possible targets instead of establishing a plan, because it is hard to have a good prediction of consequences in the game scene after a shot and we would need to check if our plan is still valid after each shot. If the plan is not valid anymore we would need to compute a new plan.
In order to implement this, we need to have additional information about the current scene: the type of the next bird (first bird after the slingshot). We compare the \textit{damageProbability} of an object for the current bird and the next one. If the next bird induces more damage on the target than the current one, the target is discarded. In other words, we want to keep the targets which are good for the next bird. This idea can be encoded by adding a rule to check if a target will suffer more damage if hit by the next bird:
\begin{align*}
goodForNextBird(Obj1) \leftarrow & secondBird(secondBirdType), \\
& birdType(currentBirdType), \\
& currentBirdType \neq secondBirdType, \\
& target(Obj1,Traj1), target(Obj2,Traj2), \\
& objectType(Obj1,Obj1Type), \\
& objectType(Obj2,Obj2Type), \\
& damageProbability(secondBirdType, Obj1Type, D1), \\
& damageProbability(secondBirdType, Obj2Type, D2), \\
& D1 > D2.
\end{align*}
And then we don't consider targets that we prove to be good for next bird by adding $\naf\ goodForNextBird(secondBirdType)$ to the predicate that represents the possible targets for the current bird:
\begin{align*}
\textit{targetData}(X,Y,Z,T,0) \leftarrow & target(X,Y), \\
& \naf \ goodForNextBird(X),\\
& \textit{offset(T), tap(Z), } Y \neq egg
\end{align*}
We show above how the rule for possibe targets with trajectories that are not egg's trajectories ($Y \neq egg$) looks like after our extension.
In the original AI agent, the decision of the target is already reasonable. With our approach, we don't guarantee that the next bird will be shot to one of the removed targets. As we will play levels more than once, the probability of having a good combination of shots increases. We strongly believe that this small improvement will minimize our answer sets such that it gets closer to people choices and, thus, allow our agent to achieve good scores.
\section{Conclusion}\label{sec:conclusion}
In this paper we presented an extension called DualHEX of AngryHEX AI agent, which performed very well in the Angry Birds Competition 2013. The DualHEX agent represents a declarative approach implemented by means of Answer Set Programming (ASP) techniques to play Angry Birds. Our goal is to minimize the answer set by taking into consideration the damage probabitly of targets for two birds, current and next. Since the answer set is already a good solution for the current bird, this simple improvement allows to keep more advantageous solutions for the next one. This may lead to complete the levels with better scores with few impact on performance.
In order to evaluate our approach, we first started by setting up the AngryHEX agent to run. In this process, an error while running the code was identified. We then contacted its developers and they are also facing the same problem. Due to this problem, we were not able to test our extension of the AngryHEX agent. In the future, we plan to run Benchmarks to compare the efficiency and performance of its results with the results obtained by the AngryHEX agent.
\bibliographystyle{splncs03} % Springer Style
\bibliography{literature} % this is the "literature.bib" file in the directory!
\end{document}
