Twenty Questions by Text: the Math of Narrowing It Down, and the Best First Questions

Updated: Nov 2
Twenty Questions looks like a game of luck and turns out to be a game of arithmetic. This post covers how Games Textapp plays it, where the game came from, why twenty yes-or-no answers are far more than you need, and the opening questions that do the most work.
How the game plays by text
Ask for Twenty Questions and the app thinks of something and tells you the category: an animal, a food, a thing, a place, a job or a sport. You ask yes-or-no questions, such as "is it bigger than a cat?", and each one gets a yes, a no or a sometimes. A question that cannot be answered yes or no, like "what color is it?", does not count against you; the app asks you to rephrase. Name the secret within twenty questions to win, or say give up to see what it was.
Games Textapp is an AI. The answers to your questions come from a language model that knows the secret, so on a borderline question an answer can occasionally be debatable. Whether an avocado counts as a fruit, or a tortoise as a pet, depends on who you ask. When an answer surprises you, ask a slightly different question to confirm it.
Where the game comes from
The game is older than most people assume. Wikipedia's article on twenty questions dates it to at least the eighteenth century, citing a 1786 letter by Hannah More describing it at a London dinner party, and notes that the common "animal, vegetable or mineral" opening borrows from Linnaean classification.
Charles Dickens put a version of it in A Christmas Carol, published in 1843. At Fred's party the guests play a game called Yes and No, and the Project Gutenberg text records how they close in: an animal, a live animal, a disagreeable and savage animal that growled and grunted, lived in London and walked about the streets, and was not a horse, a cow, a tiger, a dog, a pig, a cat or a bear. The answer was Uncle Scrooge.
Radio made it a household game. The same Wikipedia article says the American show Twenty Questions first aired on the Mutual Broadcasting System on 2 February 1946, and the BBC version ran from 1947 to 1976.
The math of narrowing it down
A yes-or-no question has two possible answers, and the best one splits the remaining possibilities in half. Claude Shannon gave that unit its name: according to Wikipedia's article on the bit, he first used the word in his 1948 paper A Mathematical Theory of Communication, crediting John Tukey's contraction of "binary digit". One bit is the information in a choice between two equally likely outcomes.
Twenty perfect halvings multiply up fast. As the twenty questions article puts it, twenty yes-or-no answers can tell apart 2 to the 20th power, or 1,048,576, objects. A skilled player with perfect questions could find one word in a list of a million.
The 20Q electronic game put that idea in a box. Wikipedia's 20Q article says Robin Burgener invented it in 1988, that it uses an artificial neural network to choose its questions and guesses, learning from players' answers, and that Radica made it a handheld toy in 2003.
The numbers for this game
Games Textapp picks its secret from fixed word lists, so the field can be counted. I counted the words in each category with a short Python script and took the base-2 logarithm, which is the number of perfect questions needed in theory.
Animal: 38 words, 5.25 bits, so 6 perfect questions.
Food: 38 words, 5.25 bits, 6 questions.
Thing: 38 words, 5.25 bits, 6 questions.
Place: 29 words, 4.86 bits, 5 questions.
Job: 27 words, 4.75 bits, 5 questions.
Sport: 27 words, 4.75 bits, 5 questions.
Across all six lists there are 197 words, about 7.6 bits, but announcing the category hands you about 2.6 of those for free. That leaves you five or six bits to find with twenty questions, a margin of roughly fourteen.
The margin disappears if you guess early. Asking "is it a lobster?" against 38 animals is right one time in 38 and earns about 0.18 bits on average. Asking "is it a mammal?" splits the same list 23 to 15 by my count and earns about 0.97 bits, more than five times as much. Single guesses are for the end, when two or three candidates remain.
The best first questions
Each suggestion below is aimed at a near-even split of this game's own lists, by my count.
Animal: start with "is it a mammal?" (23 of 38). On a no, "is it a bird?" splits the rest 8 to 7. On a yes, "does it live in water?" or "is it bigger than a person?" keep halving.
Food: "is it sweet?" catches roughly 14 of 38, then "is it a fruit?" or "is it baked?" Expect a sometimes on items like pumpkin.
Thing: "can you hold it in one hand?" catches roughly 15 of 38. Follow with "does it make sound?", which isolates the instruments and the whistle.
Place: "was it built by people?" leaves 9 natural places (volcano, mountain, island and the like) on the no side, about 0.89 bits. On a yes, "is it a building?" is the next split.
Job: "do they mostly work indoors?" splits the list, with a few debatable cases like the electrician, then "do they work with patients?" or "do they wear a uniform?"
Sport: "is it played with a ball?" splits about 11 to 16, close to a full bit. On a no, "does it happen on water or snow?" picks out seven of the rest.
Keep each question about one property, avoid "or" questions that can be half true, and save the guessing for the last few.
Try it by text
Text Hi to (725) 252-4524 and ask for Twenty Questions. It names a category, you ask yes-or-no questions, and you can give up any time to see the answer. No app, no account and nothing to download; it works on any phone that can text. Your first 30 messages are free, then one $9.99 a month subscription covers every Textapp. Text STOP at any time to end messages. Message and data rates may apply. More at textapp.co/apps/games.



Comments