Game "Guess who" with two cards

Question

I was playing "Guess who" with my sons and a friend, and she told me that she used to play with two cards to get a "not so simple game".
The questions have to be formulated in this way: "Are any of your characters female?", "Do any of your characters use hat?". This way, if the answer is NO, you get useful information and you can flip down the corresponding characters on your board, but if the answer is YES you cannot flip down any of the tiles on your board, so your question was not so informative. Compound questions as "Are any of your characters bald and wear glasses?" are not allowed.

I got intrigued by this variation of the game, and I have arrived to two conclusions:

• There may exists situations of non-existence of solution. For example, imagine an extremely reduced version where there are only 4 nearly identical characters where Character A and Character B are blonde, while Character C and D are brunette. At the same time Characters A and C use glasses, while B and C don't. They 4 cannot be distinguished by any other characteristic. If your opponent has characters B and C, for example, you cannot separate them with this kind of questions.

• The best strategy is, probably, to ask "peripheral" questions. That is, questions that do not divide the sample in two. Contrary to the winning strategy for the normal version, I think, but I am not sure, that it is better to ask for "rare features", to have more chances to get useful information. But I don't have a way to prove it.

Do you know if is there any serious approach to this problem in the literature? What do you think is the best algorithm to approach the solution (even if it cannot be reached, it should be possible to find the "enveloping set" of the solution).

Answer 1

Joining the different approaches of the answers and comments I have arrived to a satisfying answer. As Ross Millikan said, you have to focus in the universe of pairs, instead of individuals.

Then, taking the idea of vvg of comparing with Mastermind, you can codify every pair like a Mastermind sequence, not binary, but "trinary". For example, the pair (Tom, Susan), where Tom is a blonde man with no glasses and Susan a blonde woman with no glasses, can be codified with the sequence: $$ (1,2,0,...,...,...) $$

The first entry is a value for the feature "number of men in the pair", the following is the value of the feature "number of blonde people in the pair", the third one is "number of people wearing glasses", and so on. Every pair is codified with a sequence.

To play the game in an optimal way, I would write all the possible sequences, and then I would eliminate those not corresponding to a real pair (for example, maybe there is no pairs consisting of 2 bald men, both with glasses, both with green eyes).

By the way, if two pairs correspond to the same sequence-code, the game doesn't have solution. But we can find the "enveloping set".

Looking at the list of remaining allowed codes is easy to figure out what the next question should be: you can examine every column and see what question let you eliminate more codes. For example, if you have something like this:

the question "is either of them a man?" split your codes in 3/1, so can be a bit of a risk. But the question "has either of them green eyes?" split your space in halves, and lead to the solution as in the usual game.

Nevertheless, there are more complications. For example, there are characteristics which can imply others, like being bald an being blonde. And moreover, you have to be aware of 24*23 pairs-codes, which I think is impossible to do it by heart (at least for me) without the aid of a spreadsheat.

It is still very surprising to me that a so simple game as "Guess who" gets so complicated with this slight modification.

Answer 2

One possible algorithm to approach the solution to the "not so simple game" of Guess Who is to first identify the characteristics that are shared by all of the characters on the opponent's board. For example, if all of the characters on the opponent's board are female, the first question could be "Are all of your characters female?" If the answer is yes, then the player can eliminate all of the male characters on their own board.

Once the shared characteristics have been identified, the player can then ask questions about specific characteristics that are not shared by all of the characters on the opponent's board. For example, if some of the characters on the opponent's board are female and some are male, the player can ask "Do any of your characters use a hat?" If the answer is yes, then the player can eliminate all of the characters on their own board that do not use a hat.

By asking questions in this way, the player can gradually narrow down the possible characters on the opponent's board and increase the chances of guessing the correct character. The player can also keep track of the answers to previous questions to avoid asking redundant questions and to increase the efficiency of the algorithm.

It is not always possible to reach a solution to the "not so simple game" of Guess Who, but the algorithm described above can help the player to find the "enveloping set" of the solution, which is the set of characters that are still possible on the opponent's board after each question is asked. By continually updating and refining the enveloping set, the player can increase their chances of guessing the correct character.

Additionally, the player can also use strategic reasoning and probability to make educated guesses about the opponent's character. For example, if the player knows that the opponent's character is male and uses a hat, the player can eliminate all of the female characters on their own board and then make a guess about the remaining male characters that use a hat.

Overall, the key to winning the "not so simple game" of Guess Who is to ask informative questions that eliminate as many possible characters on the opponent's board as possible, while also using strategic reasoning and probability to make educated guesses about the opponent's character.

Answer 3

This is a Master Mind game variant. Knuth's algorithm [1] should work here as well. The difference is when the cards are dealt between the two players, assuming player A is the codemaker and player B is the codebreaker (roles defined in the Master Mind game), player B can use the cards (s)he is dealt to already eliminate some of the choices.

Then they make guesses using Knuth's algorithm.

Think of each feature as a bit in a binary string. Then the collection of features encodes into a number or symbol. The game then is about guessing the opponent's number/symbol sequence (if multiple cards are held). The classic mastermind game has $4$ symbols that could be $1,2,3,4,5$ or $6$. So, approximately $3$ bits of information per symbol since $6 < 2^3$. That is equivalent to 3 features for the characters. Knuth's algorithm gives you the answers in 5 guesses or less for the classic Master Mind algorithm.

There is also a generalization [2] of the Master Mind algorithm for greater number of features and symbol string length.

References

[1]: Knuth's Master Mind algorithm. https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf

[2]: Gerold Jäger and Marcin Peczarski. 2009. The number of pessimistic guesses in Generalized Mastermind. Inf. Process. Lett. 109, 12 (May, 2009), 635–641. https://doi.org/10.1016/j.ipl.2009.02.016

Answer 4

(not a full answer, but too complicated to be a comment)

Your proposed situation does have a solution. I think this is the simplest solution to understand (but not the best):

1. Is either of your characters blonde? YES
2. Is either of your characters brunette? YES (now you know that they have either A or B, and also either C or D)
3. Does either of your characters wear glasses? YES
4. Does either of your characters not wear glasses? YES (now you know that their characters are either AD or BC)
5. Is either of your characters a blonde who wears glasses? NO (now you know that they have exactly BC)

You can't flip down any characters until question 5, but you're still gaining information with each question. If you think of the game as being like single-character Guess Who on the pairs $\{AB, AC, AD, BC, BD, CD\}$, then each question allows you to eliminate one of those pairs. A better solution would be to start with question 5. This immediately separates your space of possibilities into the 3-element sets $\{AB, AC, AD\}$ and $\{BC, BD, CD\}$, allowing you to solve the game in 2 more questions.

In general, if the 1-character game is solvable, then the 2-character game will be as well. For example, you can just keep asking questions of the form "is either of your characters [a combination of properties that is only true of a single character]" until you've worked everything out. (This is a terrible algorithm that will cause you to lose any actual game, but it is guaranteed to terminate in a finite number of steps. Note that we are guaranteed that some combination of properties like this exists, or the 1-character game would be unsolvable.)