Machines haven’t surpassed humans just yet — at least, not when it comes to launching cartoon birds at pigs with a slingshot.
Millions of people have swiped and tapped their way through Angry Birds, the popular iPhone game, since its 2009 release. But while most players dig in to the game for a fun way to pass the time, local computer scientists are using it to test concepts that could be used for a wide range of applications, including medical diagnoses and treatment.
Using artificial intelligence, a research team from the University of Wisconsin-Madison created a computer-based player that could play Angry Birds on its own. Team Wisc’s AI player then competed at the Angry Birds Artificial Intelligence Competition in Beijing in August, taking third place out of 19 teams from around the world.
The player was developed by Jude Shavlik, a professor in computer sciences, and his students Anjali Narayan-Chen and Liqi Xu.
“What we had to do was write code to make our agent play the game intelligently and try to solve levels, and try to solve them well,” said Narayan-Chen, a junior in computer sciences and electrical and computer engineering. “It was a machine learning challenge for us.”
Angry Birds originally gained popularity as an app for Apple devices and has expanded to computers, video game consoles and launched a slew of retail products, becoming a pop culture icon thanks to its goofy premise. To play, players launch birds from a slingshot at pigs nestled on and around various structures, with the goal of crushing the pigs. Variables include the launch angle, the length of the slingshot pull, special features associated with the colors of the birds and the amount of time elapsed between shots.
Shavlik and Narayan-Chen say their method was simple. They took screenshots of the game periodically during play, taking note of where the objects on the screen were positioned when things occurred. Essentially, the screenshots were their data.
“We had only taken an intro class to AI, so the techniques are fairly simple,” Narayan-Chen said. “You don’t have a chance to go deep into complex algorithms. It’s really simple but really effective. Many other competitors used really complex algorithms.”
They chose the shot angles based on what they saw on the screen around the pigs. Eventually, they started to label the shots as “good” or “bad.” A good shot was one from a game in which all the pigs were destroyed. A bad shot was one that didn’t destroy a pig and resulted in a lost game.
They encountered a few surprises along the way.
Angry Bird aficionados might be interested to learn that that the outcome of each bird affects the outcome of the next.
The team also learned that making the same shot twice under the same conditions will not result in the same outcome. There’s an element of randomness to the game.
One of the most important things for the team to achieve was to actually teach the AI player how to play the game — not just how to memorize and ace specific levels. In other words, the player makes shot choices based on the surroundings of the pig, rather than the fact that it has played and defeated the level a certain way before. Mastering that served them well in the competition, where special levels were created to stump the competitors.
“That’s the most important lesson in machine learning, to make sure you test on different data than you trained on,” Shavlik said. “It’s easy to memorize data, but it’s hard to generalize and do well with future data.”
While the trio of scientists was measured and meticulous in its research, it was aggressive and unrelenting in the competitive arena.
The competition pitted 19 teams and one control agent against each other. The top eight teams, including the control, were allowed to advance to the quarterfinals. Team Wisc just made it through, with a seventh-place finish in the first round.
They knew exactly which bugs they needed to fix to bolster their player for the next round of competition. They were only allowed to make small changes, but as Shavlik said, the code is only as strong as its weakest link. Sure enough, once they fixed a small oversight in their code, Team Wisc beat three other teams to move on to the semifinals.
From there, the team found itself in an intense battle for third place — which it won.
The next day, the top three machines took on a set of human challengers and the humans were victorious.
“It’s kind of neat, having been in machine learning 30 years since I started on it as a grad student, (to see) the widespread use exponentially growing,” Shavlik said.
The Angry Birds competition is a more elaborate version of some of the games Shavlik uses in his classes to teach his students the real-world applications of machine learning. In the introductory class the two students took, students coded AI backgammon games and simulated scenarios in which players were infected with a fictitious disease with a variety of gruesome outcomes.
The games are just a means to an end, Shavlik said. They’re a “fun test bed” to get young scientists excited about general concepts.
Shavlik has done research that applies machine learning and data mining to breast cancer screenings. In both cases, Shavlik said, there are a set of features that describe examples. In Angry Birds, the features can predict whether the shot will be a good or bad one. In Shavlik’s research, the algorithms can predict whether a woman’s tumor is benign or malignant.
The concepts can also be used to create personalized book recommendations — like the ones you might receive after doing online shopping — or electronic medical records that predict how a patient will react to specific medications.
For Narayan-Chen, the research experience helped her decide to pursue graduate studies in computer science, and she said she’ll likely stay within the AI field.
Neither she nor Shavlik has grown tired of seeing those avian and porcine spheres soaring across their screens, but Narayan-Chen said she thinks she’ll let the machine play the game for her from now on. ￼