Saturday, July 18, 2009

How Electronic “20 Questions” Games Work

By Chris Higgins
It was about five years ago when I first saw a 20Q ball. The tiny handheld device scrolled text across its meager one-line screen, inviting me to challenge it in a game of 20 Questions. I immediately thought of an object I figured it wouldn’t guess (”iPod”) and began to play the game. After a series of slightly odd questions — including “Does it bring joy to people?” — the little ball gave its guess: “MP3 player.” Wow. It was right.

So how does this 20Q device work? The short answer is “artificial intelligence.” The long answer involves lots of practice. In 1988, Canadian inventor Robin Burgener programmed a neural network (a specialized form of computer program) capable of playing 20 Questions, but without a library of knowledge about common objects. He proceeded to teach it twenty questions about the object “cat,” then handed the program (on floppy disk) to friends and encouraged them to play, recording their play sessions as it went. For 20Q, playing equals learning, as it develops “synaptic connections” whenever it receives answers to questions. It’s able to reinforce connections by playing games over and over with different people, gradually learning which answers are correct and which aren’t. (Thus it’s difficult to “poison” the system by purposely giving it wrong answers.) The program can then use these connections to pose clarifying questions, eventually arriving at an answer.

By 1995, Burgener had a good body of connections in his neural network. He put a version of the 20Q program on the web and encouraged web visitors to play with it (thus training it in the process). After the online version of 20Q had played one million games (amassing 10 million synaptic connections in the process), Burgener boiled down the 20Q system into a simplified 20Q-on-a-chip version. The hardware version was incapable of learning, but contained information about the 2,000 most popular objects chosen by users of the online program. As such, it embodied a shocking “intelligence” that toy makers later put into the 20Q balls, now available at toy stores everywhere for under $15. (Specialized versions are also available, including a Harry Potter unit, and later versions of the handheld game have more information built-in.)

Today (or at least as of late 2006, the last time its online FAQ seems to have been updated), the online version of 20Q guesses correctly about 80% of the time, and if you allow it 25 questions, it claims a 98% success rate. With over 60 million games played online, the neural net continues to learn — and this learning can be translated into future versions of the 20Q handheld games. In an interview with Kevin Kelly, Burgener said, “It is learning, but it is not increasing its success rate. What happens is that it is learning to play more kinds of people, people who don’t speak English easily, or who have never played 20 questions, or who come from different cultures, and to understand more difficult kinds of things.”

You can play 20Q Online for free, or pick up a handheld version at any reputable toy or game store. You can read a bit more about the game at Wikipedia or check out more on neural networks for a deeper understanding.

No comments: