Twenty questions is a weird game
aaronson.org
aaronson.org
The author quips that "twenty questions isn’t enough to guess almost anything", but I wonder if most people taking their first crack at the game (usually as children) pick something squarely in the 2^20 most popular things.
(My friend's dad was really good at picking words. I remember he stumped us for an entire restaurant visit with "the cub in the Chicago Cubs logo".)
• Choose some reasonable number of questions of the form "Is it ___"?. Let's say 256
• Come up with a list of objects, and for each one give it a 256-long bitvector encoding its answers to the questions
• Maintain a set (implemented as another bitvector) of the potential items. Figure out which question would divide the set in two most closely; ask that question.
I am the opposite of a hardware hacker or systems programmer, but it seems like this is algorithmically straightforward to implement with bit-twiddling.
Actually programming the logic once you know it is the easy bit, it's constructing the dataset of answers and questions in the first place.
This depends on the goal. One goal might be to answer all questions as quickly as possible, in which case partitioning the search space in two might be a good strategy. Another goal might be to have the best chance of guessing the item within 20 questions, in which case you will want to choose questions which maximise the % of the remaining search space you can uniqely identify with the remaining questions (perhaps weighted by popularity of that item).
It's a neural net, so very efficient on small devices.
> It’s cooperative because everyone is ultimately working toward a common goal: deducing the answer
I think this point gets pretty close to why these games are fun or interesting to begin with. I don't think it's necessarily because that they teach you about a person based on the object they choose or the guesses they make, but the fact that the game operates at all. In some sense it's like a puzzle, but unlike a puzzle doesn't just operate on its prima facie rules - because if you can't solve a puzzle then that's just too bad, but if 20 questions doesn't end then something is off. In seems that 20 questions is interesting because there are social conventions within which it operates and playing by those conventions seems to demonstrate a social and emotional understanding that power dynamics within the relationship will be cooperatively undermined.
I recently started to learn toki pona after seeing it discussed here, his "12 days of toki pona" series is really great.
Here it is in French in 1788, as "The Twelve Questions" but still beginning with the question animal, vegetable, or mineral: https://www.google.com/books/edition/Les_soir%C3%A9es_amusan...
Here it is in English in 1796, as "Game of Twenty": https://www.google.com/books/edition/The_Juvenile_Olio_Or_Me...
I haven't looked too hard for earlier examples in other sources. I see Sorel had a game called the Game of Questions in the 1600s, but it's pretty different: https://wobbupalooza.neocities.org/
The second was 20 Questions. The app provided prompts and a paddle to keep track of the guess count.
It was a nice little app because it made iPhone social.
We called the app iQ because the iProduct pattern was still in force and it was cool to camp the name space.
We sold a bunch of copies of this game, but not nearly as many as we later made on Baby Names, the first baby name app in the App Store.
It was the gold rush era, you could still come up with simple ideas and be the first to put it up on the App Store.
https://web.archive.org/web/20090101213438/http://neutrinosl...
I know there were already many tip calculators even back then, and they were maybe fine for tips in general like when you are at a restaurant, but I never saw one except for mine that worked well for the most important case: figuring out how much to tip the pizza delivery guy when you are paying in cash.
Say your pizza comes to $16.23. If you usually tip 15% a normal tip calculator tells you that is $2.43 and the total would be $18.66. But who the heck is going to try to pay exactly $18.66 when their are standing in the open door with their home's precious heat leaking into the cold winter night? Same with handing him $20 and waiting for him to count out $1.34 in change.
What most sane people are going to do is hand him $19 and say "keep the change", or hand him $20 and say "keep the change", or hand him $20 and say "give me $1 back".
With my calculator you would enter the $16.23 price, and the calculator would give you a table something like this:
Pay Tip
$17 4.7%
$18 10.9%
$19 17.1%
$20 23.2%
$21 29.4%
I searched around for a screenshot and found one with an images and a description of our tipping app, Tiptotaler.
It apparently got an A- rating from ilounge at the time, which is heartening still today. :) [1]
App functionality description:
> You can separately input food, drinks, and tax into three fields at the top of the screen, then note the number of drinkers and non-drinkers, set the tip amount, and then get totals for individual diners.
[1] https://www.ilounge.com/index.php/articles/comments/iphone-g...
I find this ironic, as the author treats it like a word game. I've always played that it has to be a "thing" by the typical sense of the word, e.g. an object. Sometimes with bounds, like something you saw today. The problem with "intangible things" is they are essentially imaginary, and therefore subject to the whimsy of the answerer, as they point out. Does an Air Guitar make noise? Is an Air Guitar a gesture, what about a form of dancing?
Objects don't have that problem but still can make for incredibly interesting games.
> Does an Air Guitar make noise?
"Maybe, but only in your mind" or "not directly by itself"
> Is an Air Guitar a gesture,
Yes.
> what about a form of dancing?
"Yeah, I guess it is'
> As John Green (or Georg Cantor) taught us, some infinities are bigger than others—and the number of things is a really big infinity
I don't think this statement is true, at least not in the context it's given. At most, we'd only be able to think of countably many things, which is the smallest infinity.
So if a set is infinite but a provably strict subset of another - would we not say that set/infinity is smaller?
I'm personally a fan of the Infinite Hotel Paradox as an introduction to the subject.
The name isn't unique either; by definition, ℵ₀ is equal to ℶ₀. This should be a clue that the term ℵ₀ is not actually meant to identify the number in question. Rather, what's going on is that there is a conceptual system of ℵ numbers, and another conceptual system of ℶ numbers, and the number at index 0 in each of those systems is the cardinality of the naturals.
I don't see why I have to reject aleph null just because I reject Bob.
That's the definition of ℶ₀. So of course they are equal.
"Two" is also just a name for the successor of 1. I could also call it "bob" and thus "two" would not be unique, but I don't see the point. The fact is that the cardinal of countable numbers is a mathematical concept which has a name, and can be manipulated. Which is what matters, and what the parent poster maybe did not understand.
There is no point, because 2 is well defined.
That is also true of the ℶ numbers, but it is not true of the ℵ numbers. That's why, in that case, it's necessary to have multiple names for the same number.
> The fact is that the cardinal of countable numbers is a mathematical concept which has a name, and can be manipulated.
No, that's not a fact, that's what I'm saying.
The cardinality of the naturals is a mathematical concept. It is referred to as "the cardinality of the naturals", or by many similar phrases.
But it is not referred to by the name ℵ₀. ℵ₀ is a name that refers to a different concept, the cardinality of the ordinal number ω. The two cardinalities are equal, but ℵ₀ specifically refers to one of them, conceptually, rather than the other.
ℶ₀ refers to a different concept again. That's the one that is meant to be manipulable.
Another sibling comment used the even/odd example, but that's not necessary to dispel this particular misconception. Consider the set of non-negative integers and the set of positive integers. That is, {0,1,2,3,...} and {1,2,3,4,...}. The latter is a strict subset of the former. Maybe I have just done mathematics for too long, but to me these are intuitively, "obviously" the same size. What would it even mean for one of them to be smaller? Which one is the same size as {-1,-2,-3,...}, if either of them? Even doing folk mathematics, if the size of the first is "infinity" then the size of the second is "infinity minus one which is still infinity".
For example, the natural numbers are a subset of the whole numbers, but there is a natural number that corresponds to every whole number. To see this, we can order the whole numbers like this: {0, -1, 1, -2, 2, -3, 3, ...}, and we can easily see that we can now assign one natural number to each of them (0 -> 0, -1 -> 1, 1 -> 2, -2 -> 3, ...). Since you'll never run out of naturals, you won't ever find a whole number that doesn't have a corresponding natural number.
Since assigning a natural number this way is equivalent to counting the elements of the other set (in this scheme, I could say that -2 is the 3rd whole number), this type of infinity is called "countable infinity". The natural numbers, the whole numbers, and the rational numbers are all countably infinite. In contrast, the irrational numbers and the real numbers are not. In fact, even the real interval [0, 1] is not countable, so this interval is considered to have more elements than N (the set of natural numbers).
Note that while there is only one countable infinity, there are many uncountable infinities - so not all uncountably infinite sets are considered as large. If you're curious about this area, the study of these concepts is done via "transfinite numbers" - particularly, the transfinite cardinal numbers (there are also transfinite ordinals).
You make "the ordinals" sort of using your idea, but that isn't really measurement of "size"; it's more like an assignment of ranks.
I don't think that's true. We can certainly think of certain numbers which we gave a name to and have defined it in some way. But there are a _lot_ of real numbers.
We could think about it this way: we can only describe (and therefore think of) numbers using a finite number of symbols out of a finite alphabet. That makes it only countable.
And then some uncomputable ones if we give them a name/concept.
It seems quite wild
Infinity is much bigger than any finite number. This includes even "all possible numbers reachable in all possible finite encodings of a number within a given size", as inconceivably large as that is. No matter how large that set is, somewhere, there is some maximum number that is the largest possible number you can specify under the conditions I've given here, and that number is 0% of the way along the number line, which means that 100% of all "computable numbers" are larger than than that number.
There are some uncomputable numbers that have been given names. We even have the first few digits of some of them. See for instance: https://en.wikipedia.org/wiki/Chaitin%27s_constant
You can't think of an arbitrary real number, in the sense of distinguishing it every other real number(including nearby reals an ε away from it), and with no other constraints besides being a real number.
What about potentially think of? Even that does not make sense because every possible description you can think of must be written with finitely many symbols in some language, and all such descriptions form a countable set.
Therefore, there are real numbers that could never be written down in English, even potentially. Of course, that partially also depends on the kind of axiom system that you are using. In effect, the standard axioms of mathematics state the existence of things that cannot be effectively specified, which some people actually are against, although such people form a minority.
The surprising thing is that we can effectively reason with large infinities and such objects make intuitive sense (the set of all functions from the natural numbers to the natural numbers is uncountable but a very natural sounding set), and yet it is impossible even in principle to write every one down, even with an unlimited amount of time.
Is a ghost?
A finish line?
Some players know the word but want to ask misleading questions but with out the other players noticing.
Its genuinely hard to find someone (real or fictional) who it can't find!
It can even guess things like "me" or "my little sister" correctly.
It's probably not like the answerer has access to more than, say, 1M things - I mean as things they can juggle in their mind and pick among.
Let's say recording artists: there are 100s of thousands of them globally. But a regular person will perhaps know/recall at best 100-1000 max distinct ones, even if they have heard 2x or 3x others. And they'd be the most likely another would know too.
Or let's take numbers: those can be constructed (you don't need to know a number ahead of time to think of it - I can think of 2345324532435245 but I didn't have that in mind as something I've encountered already, I just know that that would be a number, I just need to pile on digits to come up with one). So, yes, this would overflow the "set of items to pick". But "I'm thinking of the specific number X" is not commonly or ever part of the 20 answers game.
(Still, if the first N questions make it clear that it's a number that was picked, the next 20 - N ones could try to binary search it).
Or let's consider animals and insect: there are 20,000 types of beetles alone. But nobody will put an unknown "beetle type X" (say, "Sitophilus granarius") as the item they think. They'll either think of "beetle" in general, or at best some well known beetle type.
One insight is that if the other person doesn't even know of the thing you have in mind, or is not fun guessing it with questions (like a specific huge number), then it makes no sense to pick it, as part of the implicit game rules is for others to have a chance and everybody to have some fun (as opposed to "win at all costs").
On the back-end is a GPT-3 model answering the questions with: never, rarely, sometimes, always or usually.
One thing - instead of the 'is it an animal' intro, perhaps you could put 'ask your question here'.
The beginning could have been Scott Aaronson, and I expected it to continue with some incredibly deep insight on how anything in the universe cannot be described in a small number of bits, but anything humans can think of can, etc etc.
It didn't quite go there but a fun read regardless.
Quantum Mechanics Isn’t Weird, We’re Just Too Big by Phillip Ball
https://youtu.be/q1O11kP6x1k?t=2366
Short thesis : According to quantum mechanics, the universe doesn't make up its mind till you ask it to.
Or, in CS lingo, the universe is lazily evaluated.
Real World [runs on] Haskell.
When we play this game with famous real/fictional people, this happens all the time. Sometimes there is even a three-way ambiguity. The character to guess is: Barbie.
"Is she older than 50?"
"Yes" (the concept)
"Have I ever talked to her?"
"Yes" (the doll)
"Is she an athlete?"
"Yes" (the character)
* Going around the circle, each player names a person and a category into which that person belongs (e.g. "William Shatner, no more actors")
* Without taking notes, the next person continues and so forth.
* If a player believes another player is in violation of any of the categories, they may formally issue a challenge. If the challenge is valid, that player is eliminated, otherwise the challenger loses one of their (2) allowed challenges.
The show works great because all 3 players are comedians and old friends, so they love to get ridiculous and varied with it.
Categories might be "No more people whose name fits iambic pentameter" or "No more people who any of us had a crush on" or "No more people who have probably used a microwave before".
Persons might be "Noah" or, as you mention, "Barbie". Resolving a challenge like "Well, how old is Barbie, really?" are solved sometimes through discussion or sometimes through a player promising to abide what Wikipedia says before the third, uninvolved player, looks it up.
However ... no theory of (natural) language has been consistent with human judgement, so all these attempts to formalize semantics should be take with a large grain of salt. They are attempts, not even theories.
This depends on whether you’re a Legitimist or an Orleanist. And even then, the Orleanist claimant is only “balding”, looks to be around 4 or so on the Norwood scale.
I can't touch the Colossus of Rhodes as it no longer exists, but that doesn't make it tangible, so it need not exist right now. If someone genetically engineers a dragon in the future, does that retroactively make dragons tangible today?
Because most people think of something hard to guess as opposed to something they know a lot of facts about. Part of being good at 20 question is being good at handling wrong answers to your questions.
Production grade 20 question AIs do not just do a binary search because it is too easy for the human to make a mistake in answering and then the computer won't win. In order to improve the chances of winning, the AI must be robust against a small percentage of wrong answers being given to it.
It’s a game though, not an exercise in pure logical deduction.
Probably the question that leads to most "but you said!" situations.
Edit: don't know how the similar sibling comment didn't appear to me when I was writing this, since it's from 4 hours ago and I loaded the page less than one hour ago...
Being able to see something narrows down the universe of things quite considerably. This is about the tangible/intangible difference.
The number of questions is not limited.
I don't think that's true. If you choose a random number between 0 and 1 you'll need an infinite number of questions to guess the number.
How would you do that?
https://duckduckgo.com/?q=20+questions+electronic&iax=images...
e.g. Is it ((a thing you can hold) \/ (a mathematical construct you can't hold))?
I tried thinking a bit outside the box for other questions that would break down the search space - but none of them were any improvement on the binary search.