Until
next week, 
Dateline: September 6, 1998
A month or so ago I came across an intriguing site housing an AI program that plays the game 20 Questions. In old radio and TV versions of this game (the 1950s' BBC-TV program What's My Line is an example) an individual is asked to think of some object or event but not to disclose it. A panel then can ask up to 20 questions to try to find out what object the individual has in mind. The first question is usually "Is it animal, vegetable, of mineral?", which instantly narrows down the search space considerably.
This is quintessential decision-tree reasoning. "If it's animal, walks on two legs, cannot fly, lays eggs, and its plumage graces the headgear of some generals and princes, then it's an ostrich." But this program does more than slavishly follow a decision tree--it also learns from human input.
Robin Burgener's 20 Questions replaces the panel of humans with
an AI program. I asked Robin if he would write a guest article describing
the program for the readers of this site at the Miningco, and Robin promptly
volunteered his spouse for the job. (He said she "took the job away from
him." Yeah, right. :) ) However it came about, it was definitely to the
good: Tanis has written a great article. Here it is.
| Experiment in AI asks you the questions
By Tanis Stoliar Okay, in twenty questions or less, what do you remember about those interminable road trips of your youth? Arguing with your siblings might be the number one answer, but it is likely that you played a few rounds of the game Twenty Questions with that same sibling on all of those trips. Now you can play Twenty Questions (20Q) on the Web against an AI foe. You think of something, and the program will try to guess the object you have in mind. This exercise in Artificial Intelligence is the work of Software Developer, Robin Burgener, and it has been "learning" for about ten years. Mr. Burgener, based in Ottawa, Canada, first developed the software in 1988, to satisfy his own curiosity about learning systems. "The programmatic solution seems fairly simple," he starts out to say. "Build a tree. If the program fails, ask for a question to differentiate the last object from the new object. But, if one player answers a question from a different perspective, the game will fail; player input is subject to human nature and cannot be 100 per cent correct every time." "The solution I have used," he said, "relies on a matrix of every object by every question; each element in the matrix indicates an answer for one object and one question." In very simple terms, the program determines the most probable objects and then looks at the questions to find the question that could eliminate the most objects. "But then it gets fuzzy," says Mr. Burgener. "The answers in the knowledgebase are weighted by certainty, and are, more often than not, unknown rather than known." The player can play a traditional game of 20Q, or can play a game by thinking of one of the objects the program suggests. Mr. Burgener notes that these suggested objects need "a bit of exercise" because more people are playing the game. Hundreds of people are now playing the game, adding dozens of new objects and questions to the program. This has had an effect on the program's number of successful guesses. HOW? By playing objects that are already in the knowledgebase, you can teach the program and it can gain more knowledge. The game may not guess what you are thinking, but you can also help it learn by answering additional questions. Objects and questions cannot be removed from the knowledgebase. For the competitive player, the game really has no point. The program is an experiment in AI and it needs to gain as much knowledge as possible to make it a better opponent; the more people who play, the more knowledge it gains. In a truly Canadian fashion, it's really not about winning or losing. "Philosophically," says Mr. Burgener, "a failure for the game is not really a failure, because the program learns from every game that is played." The program has evolved over the years. At first, the players (a few of Mr. Burgener's friends) would swap a diskette to play the game. Then, he re-wrote the program using the QNX operating system so that the game could be played over a network. After porting the game to a more up-to-date version of the QNX operating system, the program could support multiple players, and run over the Web. Since he launched this non-commercial experiment in AI on the Web, about 2000 players have played more than 3000 games. Before that, there had only been about 2000 games played by about ten players. The program is feeling a bit overwhelmed with all the new knowledge that it is gaining, but Mr. Burgener is excited about all the activity at the site. "Before I put it up on the Web and it was noticed by websites like Miningco.com, the program was pretty smart. Now, I think it has about the same intelligence as my 18-month-old daughter, but I'm the one feeling the frustration and the growing pains," said Mr. Burgener. A recent review by The Tech Museum of Innovation sums it up very nicely:
|
Techie
Snapshot of 20Q
The 20Q program is made up of three integral elements: the game engine, the application of user input to the knowledgebase, and the CGI/HTTP interface. The program is implemented by a sizeable program written in C. Fundamentally, the knowledgebase is a matrix of objects by questions. Every element in the matrix represents whether the answer is yes or no. It also represents the weighting of the answer to a question for an object; unknown answers have a weighting of zero. Every time a player answers a question, the URL of the answer contains three pieces of information: the current state of their game, the current question index, and their answer. To generate the next page, the game determines which objects are currently probable by comparing the current responses to the knowledgebase. If an element in the knowledgebase is unknown, the algorithm ignores that response for that object. The program then determines the number of yes and no answers for each question for the probable objects; this may include several unknown answers. The program then chooses the question that has the best ratio of yes-to-no answers (a 50/50 split would be ideal). The actual weightings are also worked into this calculation. Finally, the game compares the probability of the objects and the effectiveness of the question and decides whether to guess at an object or ask another question (this is aided by some prodding at the appropriate time). This information is used to generate a new page, with new links, to reflect the new state. At the end of a game, when the program knows the object, the program makes a pass over the knowledgebase and updates the answers for that object. If the knowledgebase doesn't have an answer, the value is set. However, if the answer that the player gave matches the answer in the knowledgebase, the weighting is incremented. If, on the other hand, the answer contradicts, the weighting is halved. That is the heart of the system. The only other things that need to be done are things like: if the program is stumped, it asks the user for the object they were thinking of and then checks to see if it already knows it. If the program was stumped, or had to ask a lot of questions, or guessed about too many objects, it will ask for a new question. Last, the program looks at objects that are similar to the target object and draws conclusions; the author calls this "spontaneous knowledge". This description makes Twenty Questions sound more like a database manager, and to a certain extent, that is part of the system. But from another perspective, every question is input into a 2D neural network, the objects are the output side. By performing a large number of simple calculations, the game is tolerant of missing knowledge and contradictory input. |
Until
next week,
NEXT WEEK: A review of Philip Marchand's biography of Marshall McLuhan. Yes, it's AI-related!
Help Wanted: Got questions or comments on this article or on any other AI-related subject under the sun? Post it in the AIBB!