Students game the system, train computer to play Angry Birds

Sep 30, 2013 by Chris Barncard
Students game the system, train computer to play Angry Birds
Undergraduates Anjali Narayan-Chen (left) and Liqi Xu (right) created a computer program that can independently play the video game Angry Birds. Their program placed third in a recent international computing competition.

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 and computer engineering undergraduate. "But we learned how."

So did the computer. Narayan-Chen and classmate Liqi Xu spent the summer programing 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. "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."

Explore further: Oculus unveils new prototype VR headset

add to favorites email to friend print save as pdf

Related Stories

Angry Birds lands in Chrome Web browser

May 11, 2011

Rovio's "Angry Birds" is landing on Chrome in the first version of the addictively popular smartphone and tablet game tailored for play on a computer Web browser.

Recommended for you

Oculus unveils new prototype VR headset

Sep 20, 2014

Oculus has unveiled a new prototype of its virtual reality headset. However, the VR company still isn't ready to release a consumer edition.

Who drives Alibaba's Taobao traffic—buyers or sellers?

Sep 18, 2014

As Chinese e-commerce firm Alibaba prepares for what could be the biggest IPO in history, University of Michigan professor Puneet Manchanda dug into its Taobao website data to help solve a lingering chicken-and-egg question.

Computerized emotion detector

Sep 16, 2014

Face recognition software measures various parameters in a mug shot, such as the distance between the person's eyes, the height from lip to top of their nose and various other metrics and then compares it with photos of people ...

User comments : 0