If you have never seen "Angry Birds”, the game’s goal is to crush pigs by catapulting angry birds towards them. It is the most downloaded game of all time on mobile platforms.
Jason Li, postdoctoral researcher at EPFL, together with Mirko Katanic and Arnaud Jutzeler, created a program that is able to reproduce the way humans play this game and it became the “Angry Birds” world champion in August at the Beijing International Joint Conference on Artificial Intelligence (IJCAI).
Obviously no one wants a program to play a program for them, but it will have real-world applications, like when the United States NSA wants to monitor how French and German leaders play "Angry Birds".
It's always fun and games until they round up all of the mutants and we have to send an X-Man back in time to 1980 to stop them. © Alain Herzog
To win, machines had to be able to automatically solve the famous game’s levels. In order to do so, they were only given access to the same information available to humans, thus forcing them to think as such. As a server transmitted screenshots displaying the game’s status updates it was then up to the machines to decide which strategy to use and which action to take.
Since the contest allows alterations and improvements between rounds, Li and the team in Switzerland managed to keep optimizing and qualify for the final round and then a victory.
In this competition, the goal of its participants is to create a "perfect" intelligence able to beat any person at analyzing the game by using the same tools available to people on their smartphones. "What we're trying to do here is to understand and define intelligence in order to emulate it" said Li. The knowledge gained in the development of this program could then be applied to many areas of artificial intelligence.
A model that has proven its worth...
In the case of Angry Birds, the "Beau Rivage" team used the principle of "exploitation vs. exploration." The strategy consists in identifying which tactics to use depending on the level the player is at.
Firstly, the researchers determined a way of defeating every type of level the player may encounter. Then, they created an algorithm responsible for selecting the strategy most likely to work based on previous attempts. Therefore, the software’s only limitation is that it requires making some attempts on each level before solving it, just like humans.
"Our algorithm was custom-made for this competition, which is why we were also able to overcome the more complicated levels, while other teams did better on the simpler ones," said Jason Li.
... well, almost...
Despite the win against other machines, they have not managed to create AI able to beat any human in this game. Their score in the "man vs. machine" competition held at the same time was not enough to defeat an experienced human player’s ten fingers.
Source: Ecole Polytechnique Fédérale de Lausanne