Games Theory

Online play can help researchers tackle tough computational problems

Ivars Peterson

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.

MATCH GAME. In the ESP Game, players come up with words that describe an image. A player gets points when his or her words match a partner's words. von Ahn

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 Ahn 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.

DOUBLE VISION. In this example of a captcha, people can still identify the words despite the distracting background, but computers typically can't. von Ahn

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.