Students game the system, train computer to play Angry Birds

Angry Birds sounds simple: Just slingshot a digital bird at a pile of evil pigs. You could teach a child to play.

But could you teach a computer?

“Well, I didn’t think we could when I heard about it,” says Anjali Narayan-Chen, a UW–Madison computer sciences student. “But we learned how.”

So did the computer. Narayan-Chen and classmate Liqi Xu spent the summer programming machine learning software to take an autonomous run at the popular video game.

Their work paid off in August, when the duo (with the help of computer sciences professor Jude Shavlik) turned their software loose on dozens of never-before-seen levels of the Angry Birds game and finished third in an international computing competition.

“We used supervised machine learning, which is feeding the computer a lot of examples, and telling the computer which ones are good and which ones are bad,” says Narayan-Chen, an undergraduate majoring in computer sciences and engineering. “We collected a lot of data by playing the game over and over again, and categorized the shots as good or bad.”

They (that is, about a dozen computers working 24 hours a day) played 724,993 games comprising 3,986,260 birds heaved at pigs.

After eliminating a deep pool of ambiguous outcomes, Narayan-Chen and Xu fed their software 224,916 “good” shots that led to completed levels of the game and 168,549 “bad” shots that led to failures.

On each level, the software zooms out, takes a picture of the screen, and overlays the image with a grid.

“The software decides what each cell in the grid contains, and — based on what it sees and what it knows from all those good and bad shots — it chooses a shot to make,” says Narayan-Chen, who spent the summer doing machine learning work through an undergraduate research fellowship.

While human players make subtle, manual adjustments to the power and trajectory of the game’s bird-chucking slingshot, adding that level of sophistication to software was a trick the students wanted to avoid.

“We still aim at a bunch of things — mostly the pigs,” Narayan-Chen says. “But when we aim at each of those things, we consider only two ways to get there: a high shot or a low shot. It’s easier for us because we can pull back the slingshot as far as possible.”

The software relies on its deep library of good targets for projectile birds versus bad targets to overcome a lack of nuance in how the birds arrive at the intended bull’s-eye.

“A lot of data and simple ideas can be better than a little data and complex ideas,” Shavlik says.

The strategy proved sound. At the International Joint Conference on Artificial Intelligence in Beijing — with Xu attending the conference in person in her native China, and Narayan-Chen “attending” via Skype on an iPad held by her mother (who happened to be in Beijing) — Team Wisconsin took the $500 prize for third place.

They were the only competitors from the United States, and actually did best among all the Birds-playing software projects against even tougher competition: human beings.

“There were a lot of people who signed up to play against a computer,” Narayan-Chen says, “and they were still way better than our software.”

For now, that is. The programing duo is considering a second run at the competition in 2014.

“It’s an opportunity you don’t usually get if you’re an undergraduate to do research, to write a paper that would be peer-reviewed, and to do talks at the conference and for other researchers,” Narayan-Chen says.

And an opportunity to use programing tools applied to real-world decision-making computers.

“The machine doesn’t know it’s playing a game,” Shavlik says. “The algorithms and concepts Anjali and Liqi are using are in a lot of adaptive software. I use some of the same algorithms in my work to identify cancer tumors.”