# Known results for games like "twenty questions"?

Consider the following game: You are given a set $$S$$ and a fixed list $$q_1$$, $$q_2$$, ..., $$q_n$$ of yes or no questions about the elements of $$S$$. Your opponent chooses an element of $$S$$ without telling you which. You then ask a series of questions taken from the list and your opponent truthfully answers "yes" or "no" to each. Your choice of each question can depend on the answer to the previously asked question. Your goal is to deduce the secret element of $$S$$ your opponent has chosen in as few questions as possible.

For example, $$S$$ might be $$\\{\text{banana}, \text{orange}, \text{football}, \text{basketball}\\}$$ and the list of questions might be "Is it a fruit?", "Is it spherical?", "Is it an animal?". In this case you could deduce the secret by asking just the first two.

This is a simple enough problem that I suspect a lot has been said about it in the computer science literature. I'm beginner enough that I don't even know what keywords to search to read more. So here are some questions:

1. Does this problem go by a certain name? Or is easily it reducible to some other well-known named problem?

2. Are there results about the number of queries necessary in various cases, say where the questions take a certain form? (For example, binary search is a special case of this problem where the allowed questions are of the form, "Is the index of the sought after value less than $$i$$?" The result there would be that the worst case takes $$\log(|S|)$$ queries.)

3. I'm also interested in the variant of the problem where you have a set number of queries and the goal is to maximize the probability of guessing the secret after using up these queries. E.g. in the example above, with just one query you can narrow down the secret to two possibilities, giving you a 50% chance of guessing the right answer (assuming the secret is chosen uniformly at random). With two queries you can narrow it down entirely, so your probability of success is 100%.

• The trick is to ask questions that cut the possibilities into as close to half as possible. That way, no matter the answer, you'll eliminate half the possibilities each time. ¶ For instance, "Is is spherical?" would be a poor first question, as the division would be 1 and 3, and you might need to ask 2 more questions to get the final answer. Nov 17, 2022 at 3:57