How would you design a machine learning system to play Angry Birds?

Question

After playing way too much Angry Birds, I started to observe my own strategies. It turns out that I developed a very specific approach to getting 3 stars on each level.

That made me wonder about the challenges of developing a machine learning system that would be able to play Angry Birds. Interacting with the game and launching the birds is trivial. But one question that I had is about the "building blocks" of the system.

Machine learning systems seem to work with simple concepts or understanding about the problem. This is often encoded as features as inputs. So it seems that the system needs to have the ability to understand some high level concepts to generate a strategy.

Is this true? Also, what are the challenges or difficult parts of developing such a system?

EDIT #1:

Here's some clarification. Getting 3 stars is a difficult problem because you have to maximize the points. This can be done in two non-exclusive ways: 1) Minimizing the number of birds used (you get 10,000 points for every unused bird). 2) Maximized the destruction of glass, wood and other objects. Each object destroyed gives you points. It is possible to destroy more than 10,000 points worth of objects with a single bird.

Here's a little more explanation about "high level concepts". In order to maximize the points described above, you need to use the special powers of each bird. So, that means launching different birds with different trajectories, depending on the layout of the map. And, while playing I develop a strategy that destroys certain areas with certain birds in a certain order.

It seems that without an understanding of how to use each bird to destroy a specific area the system could not learn to get 3 stars. So, how do you manage and encode something like that? How do you ensure that the system can learn these high level concepts?

Answer 1

Assuming you could get the right hooks into the software (or you work with your own mock-up), some things would be easy here, and some less so. This is quite a tough problem I think. As carlosdc mentioned, Reinforcement Learning (RL) is one possible avenue, although I'm not sure it's the right one.

When you begin, you have to define what your state space, action space, transition dynamics, and reward function are. The state/action spaces can be continuous or discrete, and the transition dynamics could be given by the problem or modelled mathematically. Finally the reward function may be given a-priori, or may be sampled (with or without noise).

The action space is simple: it's simply the direction and power that you shoot the current bird at. For the human, this is a discrete problem (the mouse/touchscreen is a digital input device) - let's say (for example) there are 32 possible directions and 10 possible powers, giving 320 possible actions.

The reward function is also fairly easy to derive: the goal is to get rid of all of the pigs with the fewest number of birds (OK so there extra points for other things but let's ignore that for now). The best thing would be if we knew the actual function that generates points from killing pigs (depends on the size of pig etc IIRC) - but for a single level this could be modelled perfectly.

The state space and transition dynamics are much more difficult. In order to model this correctly, we'd have to know the entire layout of the map and the physics of the game. The transition dynamics say "If I am in state x and I perform action y, I will land in state z". You can see the difficulty of this, firstly as the complex physics of the system mean that this will be extremely difficult to model accurately, and secondly as there are so many possible resultant states after even the first round (320), and this is if we assume there is no stochasticity in the physics engine, which from having played it I suspect there is. I think at this stage you would give up and go home.

Another approach is to treat it like a human does at the very start - i.e. trial and error. The human, at least to begin with, fires virtually randomly (although with a fairly strong prior to send the birds towards the pigs, but this can easily be coded in), until a range of good actions are found. This is more like the multi-armed bandit setting. The "arms" of the bandits here are the possible actions. The algorithm tries to balance exploration and exploitation - i.e. exploring the action space and exploiting good actions when they're found. For this you don't need to know anything about the underlying dynamics - you only need to know about actions and rewards. To do it fully you would have to have an arm for each possible action over all the rounds (e.g. you have 5 birds * 320 action = 320^5 = approx 10^12 actions), so the action space is very large! However you could use some tricks to improve this if you know a little bit about the state space. For example, you could probably rule out actions that send the bird away from the pigs, down into the ground, or without enough power to reach any of them. Also you only need to reach the 5th bird if you haven't killed the pigs in the previous rounds, so a proportion of the action states aren't actually possible. This is somewhat reminiscent of the approach used in the algorithm MoGo, which is a computer programme for playing Go based on Upper Confidence bounds applied to Trees, one approach to solving the multi-armed bandit problem.

Answer 2

Cool question!

It seems like this question is about the natural technique for this type of problem. I think think the natural technique for this type of problem is reinforcement learning (RL). RL is about how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward. Perhaps the best known algorithm for RL is Q-learning. I think this is the first question in this site about reinforcement learning.

I think what you're asking is true if you try to approach this as classification/regression, but those do not seem like the right tool for this problem. This is naturally a RL problem where sequences of actions and outcomes need to be taken into account.

Answer 3

Check here how others are doing it or participate yourself: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

Answer 4

just mentioned this over in meta. there was a pioneering use of genetic algorithms by Koza to solve the video game Pacman. he constructed algorithmic primitives that could sense and act. as I recall these were combined in Lisp-like trees to create larger algorithms. crossover with Lisp trees involves substituting or exchanging subtrees that represent the algorithm expressions. the success function is something like "dots eaten" or "dots plus ghosts eaten" or "time stayed alive". there is still some work in this area. there is a koza ref in this paper following. training time may be very long and "convergence" very gradual for these types of problems.

Learning to Play Pac-Man: An Evolutionary, Rule-based Approach by Gallagher and Ryan