<\/p>\n
The gadget was about the same size as tourist\u00e2\u20ac\u2122s snow-globe, with a small LED display capable of displaying about 10-15 characters, and it plays 20 Questions. It tries to guess the things that you are thinking of, by asking a series of questions, which you can answer, Yes, No, Sometimes and Unknown.<\/p>\n
What a weird concept \u00e2\u20ac\u201c take a dull game designed to kill time on long trips, and take away the human interaction and ingenuity, and the result is this toy.<\/p>\n
It is called 20Q, and it is made by Radica Games<\/a>. [I am going to jump ahead to point out that the technology was licensed from the developer of a free web-version of the game<\/a>, which is more advanced, but it gives you a good idea of what I was up against.]<\/p>\n The family next to me on the plane were totally rapt by this game, explaining that despite the fact that they had been playing it frequently, it had never lost<\/em>!<\/p>\n Perhaps that is what ruined the enjoyment of the game for me \u00e2\u20ac\u201c it was over-hyped. I immediately took on the challenge to defeat it. It was apparently an American game, so what item would the American team have missed? My first item was a Marsupial Mouse.<\/p>\n Unsurprisingly, the game failed to pick the right animal. However, watching it fail taught me some more about the way the game worked.<\/p>\n [Note: In my second game, I chose a more conventional item – \u00e2\u20ac\u0153ear-phones\u00e2\u20ac\u009d and it guessed \u00e2\u20ac\u0153head-phones\u00e2\u20ac\u009d, which I counted as a successful match.]<\/p>\n The game was very slow. Initially, I thought this was an attempt to build suspense \u00e2\u20ac\u201c certainly the game did display random pre-set texts about how tricky\/easy this one was, or how it had to think deeply. However, I am wondering now if it was to cover for the limited processing power of a small toy.<\/p>\n It would always make a guess after the twentieth question. If it got it wrong, it would bend the rules, and ask five more questions, before giving up. (The web-site version is even more lenient on itself.)<\/p>\n The questions were not always \u00e2\u20ac\u0153orthogonal\u00e2\u20ac\u009d. For example, it asked me early on if my mouse was a vegetarian. In one of the five bonus questions it asked me if it was an herbivore.<\/p>\n The question about whether it weighed more than a pound of butter made me laugh too. \u00e2\u20ac\u0153No,\u00e2\u20ac\u009d I wanted say, \u00e2\u20ac\u0153It weighed less than a pound of butter, but more than a pound of feathers.\u00e2\u20ac\u009d<\/p>\n Despite this, the algorithm was powerful enough to give the impression of intelligence \u00e2\u20ac\u201c at least amongst my traveling companions. \u00e2\u20ac\u0153Oh, it\u00e2\u20ac\u2122s worked it out now!\u00e2\u20ac\u009d said the young man only halfway through a game, \u00e2\u20ac\u0153It\u00e2\u20ac\u2122s just toying with me.\u00e2\u20ac\u009d <\/p>\n The web-site version of the game has room for more buttons for answers, including \u00e2\u20ac\u0153Probably\u00e2\u20ac\u009d and \u00e2\u20ac\u0153Doubtful\u00e2\u20ac\u009d. I tried answering \u00e2\u20ac\u0153Unknown\u00e2\u20ac\u009d for each question, but it did not advance the question number, and just came up with different general questions. <\/p>\n So the real reason this incident has stayed with me is the question of how does it do it? If I had a team and wanted to build a toy like this, how would I go about it? I considered this puzzle without looking up the answers online \u00e2\u20ac\u201c that would be cheating!<\/p>\n I divided the problem into two parts:<\/p>\n I figured I knew the basics of the algorithm – I played with the source code of a similar game back in the old days, before Game Boys. The game would walk through a binary tree of Yes\/No questions. Each leaf represented an item. If the item was not correct, you were asked to enter what your item was, and a question to distinguish it from the guess the computer made, and the binary tree was extended for the next player. Due to hardware limitations, the game I played with only had a maximum of 256 items (i.e. 8 questions).<\/p>\n That is a very simple system. The web-based version (and by inference, the toy) is not using a system that simple. For example, if you repeat the same answers the second time around, you will be prompted with different questions. Similarly, it handles \u00e2\u20ac\u0153Unknown\u00e2\u20ac\u009d answers fairly gracefully.<\/p>\n So, while I don\u00e2\u20ac\u2122t fully understand the algorithm, it is within my mental grasp that after getting the team to work on the problem, we could have a good-enough algorithm after a few months of thinking and researching.<\/p>\n To me, the hard part is coming up with zillions of objects that people tend to guess and enough arbitrary, common but distinguishing, facts to generate the tree in the first place.<\/p>\n The sheer number of items is, in theory, approximately 325<\/sup>, or 8.47 × 1011<\/sup> (eight hundred and forty seven billion<\/em>). In reality that figure is unfeasibly large. Fortunately, we can rely on the lack of imagination of humans to ensure that they tend to pick the same sorts of objects as each other. How many do you really need? We are aiming to get the kind of figures that the 20Q web-site claims (98% success after 25 questions).<\/p>\n It\u00e2\u20ac\u2122s a good question, I don\u00e2\u20ac\u2122t know the answer. My estimates tend to drop the more I think about it. My initial guess was about five million, but now I think one-quarter million would probably do. It depends exactly how unimaginative people are.<\/p>\n So where do we get one-quarter million items and distinguishing facts about them?<\/p>\n My first idea was \u00e2\u20ac\u0153textbooks, and lots of them!\u00e2\u20ac\u009d – especially for the Animal and Vegetable questions, biological taxonomy would cover this quite well \u00e2\u20ac\u201c except your average member of the public may be confused by the questions about whether jellyfish are bilaterally symmetric. The idea must be to ask questions that people can easily answer.<\/p>\n My next idea was the Mongolian Hordes approach. Persuade a large number of people to play a prototype of the game, and to have them submit their ideas, until I had enough to cover 98% of guesses. That sounded expensive and time-consuming.<\/p>\n Then I remembered the CYC<\/a> project \u00e2\u20ac\u201c an attempt to create a giant database full of every-day facts about the world that any software will need to know in order to exhibit human-like intelligence. I looked it up and the OpenCyc project is still more about the way of storing general knowledge than the knowledge itself. There appear to be only 6000 \u00e2\u20ac\u0153objects\u00e2\u20ac\u009d in the basic package..<\/p>\n The mystery remains.<\/p>\n So I looked it up on the web to find the solution.<\/p>\n The algorithm for selecting elements is based on a neural network; the tree that it walks is not a pre-determined one, but generated on the fly. I didn\u00e2\u20ac\u2122t expect that!<\/p>\n The facts have been established via the Mongolian Hordes approach. <\/p>\n They have a different web-site<\/a> with a different version of the game. This version has more options for vague answers (Unknown, Irrelevant, Sometimes, Maybe, Probably, Doubtful, Usually, Depends, Rarely, Partly). Also, if it fails to guess an object, this version will prompt you to enter you item- submissions are then vetted by teams of moderators. I assume the moderators, or similarly trusted users, also come up with additional questions to add to the set.<\/p>\n Sometimes, it will ask a question where it is not sure of the answer, and use your answer to that question to update its database when it finds out the real answer. <\/p>\nBeating the Puzzle, on the Surface<\/h2>\n
Understanding the Game Play<\/h2>\n
Beating the Hidden Puzzle<\/h2>\n
\n
AI Algorithm<\/h3>\n
The Database<\/h3>\n
Research leads to results \u00e2\u20ac\u201c and spoilers<\/h2>\n