Games theory: online play can help researchers tackle tough computational problems

Science News,  March 17, 2007  by Ivars Peterson

• E-mail
• Print
• Link

I'm online wrapped up on the ESP Game, and I'm finding it hard to stop. As each round ends, I'm eager to try again to rack up points. The game randomly pairs players who have logged on to the game's Web site (www.espgame.org). Both players see the same image, selected from a large database, but they can't communicate directly. Each player types in words that describe the image. When the words match, both players earn points and move to the next image. Each round lasts 150 seconds and displays up to 15 images. I keep hoping that my invisible, anonymous partner's thoughts are in sync with mine--all the better to rise on the list of top players.

I'm having fun, but there's more to this game than meets the eye. To its inventor, computer scientist Luis von Ahn of Carnegie Mellon University in Pittsburgh and his colleagues, the game provides an innovative way to label images with descriptive terms that make them easier to find online.

Most of the billions of images on the Web have incomplete captions or no labels at all, von Alan says. Accurate labels would improve the relevance of image search results and make the information in images accessible to blind users. However, computers aren't good at looking at images and determining what's in them, and it's boring for a person to label images.

"The ESP Game turns the tedious task of entering words that describe an image into something that's fun," von Ahn says.

Moreover, the game is addictive, he admits. Since it debuted in late 2003, more than 100,000 people have registered to play. Some players spend more than 40 hours a week accumulating points at the site.

Last fall, Google licensed the game and created its own version, called Google Image Labeler (images.google.com/imagelabeler/). "Image-search quality remains a top priority for Google," says a company spokesperson.

The ESP Game is just the beginning of turning playtime to profit. Von Ahn is working on several new games to solve other problems, such as locating objects in images, filtering content, translating languages, accurately summarizing text passages, and developing common sense.

"Computers are really good at solving certain kinds of problems," says Ben Bederson of the Human-Computer Interaction Lab at the University of Maryland at College Park. "This offers the opportunity to solve problems that computers just can't do."

"People around the world spend billions of hours playing computer games," von Ahn says. "We can channel all this time and energy into useful work to solve large-scale computational problems and collect the data necessary to make computers more intelligent."

PICTURE PUZZLES Von Ahn first thought of harnessing human brainpower for computational purposes when, as a graduate student, he was working on a security scheme to help the Internet company Yahoo! solve a problem. Yahoo! permits people to sign up for free e-mail accounts, memberships in groups, and other services. However, people can take advantage of the system by using computer programs called bots to sign up hundreds of accounts automatically and then use the accounts to distribute the uninvited mass mailings known as spam.

Working with Carnegie Mellon's Manuel Blum and others, von Ahn looked for a task that people could do easily but that computers would find difficult.

Suppose, for example, that a computer-generated image contains seven different words, randomly selected from a dictionary and displayed so that they overlap and appear against a complex, colored background. A person can almost always identify at least three of the words. A computer program would typically recognize none of them.

Blum coined the word captcha to describe such tasks. The word stands for "completely automated Turing test to tell computers and humans apart." Traditionally, a Turing test is one in which a person asks questions of two hidden respondents and, on the basis of the answers, guesses which of them is a person and which is a computer. In the case of a captcha, a computer generates the test and judges responses to it, but, if given the test, another computer can't pass it.

Many online companies now use captchas to control registration, confirm transactions, check voting in online polls, manage the sale of concert tickets, and other tasks.

While thinking about things that people can do but computers can't, yon Ahn realized that he could take advantage of human capabilities to solve problems such as image labeling. "I toyed around with a lot of possibilities until the ESP Game came about," he says.

It took months to go from idea to working prototype to final version, as von Ahn and his colleagues incorporated various features to make the game more useful and more fun. For example, some images have lists of one or more taboo words, which players can't use. This encourages players to go beyond the most obvious descriptive terms.

"Depending on the image, we can easily end up with 30 words, on average," von Ahn says. He also collects data on the frequency with which players type in different words--information that may be helpful for improving image searches. He expects those data to be valuable also to sociologists and other researchers.