Does this person have ginger hair? Is this person a boy? Is she wearing a hat? Is your person Anita?
Maybe everyone has played Guess Who?: the board game where you try to guess which character your opponent has before they find out yours. For those who have never played Guess Who?, the game goes as follows: each player picks a card at random, on which will be drawn the face of a character. In turns, the two players ask each other yes/no questions to try and guess who their opponent has picked. A board with all the images of the characters initially standing up helps the player keep track of which ones have been eliminated along the way.
To make it a bit more interesting, I usually play it with a twist: the first person who picks a card from the pile has to memorise it and put it back, so that when the second person picks a random card, there is a slight chance that both players will end up with the same character.
Valid questions are based on the looks of the character, should be easy to answer at first glance and should not be subjective, so questions like Does your character look like an ex-convict? do not apply. There are only 22 valid questions that one can ask and, for simplification, we’ll refer to a question by the positive attribute it represents, so ‘black hair’ represents the question Does your character has black hair?, and so on.
The order in which we ask the questions clearly matters. If for example, we know that the opponent has a female character, then there is no point in asking ‘facial hair’, ‘moustache’ or ‘bald’, since we already know the answer to those! Guess Who? is a game of decisions: what should we ask next?
Now, what is the best way to play Guess Who? or, in other words, what is the best order in which to ask the 22 questions? The best way to obtain the optimal strategy for playing Guess Who? is through decision theory: a tool that helps us structure the problem and then pick, amongst the many options (in this case, the possible 22 questions that we might ask) the best one. Since we don’t know what our opponent’s character is, we have to make a choice under uncertainty, and so we assume that every card is equally likely to have been picked.
Let’s suppose now that we begin with ‘earrings’. If the answer is yes, then, since only two characters have earrings, we would be only one question away from finishing the game. However, if the answer is no, we are almost as far as we were before since we now would have 22 characters left. Thus, a good way to measure if asking a question is good or bad is by focusing on the expected number of players left after that question is answered, with the best questions those that minimise the expected number of players left behind. If we focus on the expected number of characters left behind after asking a particular question, like ‘earrings’ we get
$$\mathbb{E}[\text{earrings}] = \binom{\text{ characters} } {\text{w/earrings}} \times \mathbb{P}[\text{earrings}] + \binom{ \text{characters} } {\text{w/o earrings}}\times\mathbb{P}[\text{ no earrings}] $$
giving us
$$\mathbb{E}[\text{earrings}] = 2 \times \frac{2}{24} + 22 \times \frac{ 22}{24} = 20.3$$
Therefore, after asking ‘earrings’ we expect to have a bit more than 20 people left. If we just hope that the character our opponent has is either Anne or Maria (the two with earrings), then, in the terminology of decision theory, we are playing a naive or optimistic way: we are hoping that from the 24 possible characters, the opponent has the one that is the most convenient to us. It is a strategy almost as bad as starting the game by asking ‘Is your character Richard?’, just because we were feeling lucky. We could also play the pessimistic strategy, which assumes that the opponent has the most difficult card to guess, but neither of these are good strategies.
A better strategy is the one that minimises the expected number of players left behind after the question is asked. If we focus on the expected number of cards left after asking the first question, we see the following:
The question that minimises the number of players in the first round is the one closest to 24/2 = 12, which is ‘big mouth’. By asking ‘big mouth’ the expected number of players left is only 12.3 compared with the 20.3 had we asked ‘earrings’.
Should we carry on, just minimising the expected number of players after each question? Well, actually, no. Things are a bit more complicated. Most of the questions are slightly correlated with the others, so it frequently happens that by asking the question that seems to be the best, we are left behind only with terrible options. This type of strategy is known, in decision theory, as greedy, since every single turn we try to get the best result, disregarding our future options. This is probably how most people play Guess Who? since it is difficult to see two or three steps ahead. However, a greedy strategy is not optimal.
When we play Guess Who?, we decide what to ask next based on the cards left on our board. Now, what if we could analyse every possible question that we ask, with every possible answer from our opponent? OK, that might take a lot of time since the options and the branches grow really quickly. For example, by the third question, we already have more than 70,000 different scenarios to analyse!
The usual way in which this type of problem is represented is by a tree, in which we have an initial node, and then, every possible decision we may make (the questions we might ask) creates a branch of the tree; every uncertain event (the yes or no answer from the opponent) also divides the branches of the tree; and a branch ends when we know the actual answer (we have guessed the opponent’s card). We can then assign the cost of each branch (the number of questions that we needed to ask to figure out the opponent’s player).
Tree representation of Guess Who?
Having the cost for each branch and its probability of occurring allows us to compute the expected number of questions we have to ask if, for example, we begin by asking ‘big mouth’ or ‘earrings’. If we begin with ‘big mouth’ we expect to ask roughly 4.8 questions, but if we begin with ‘earrings’ we expect 5.7 questions, so we should better start with ‘big mouth’. This way of playing the game, in decision theory, is called the Bayes Action and in our context, is the best way to play the game. The best first question to ask is ‘big mouth’ and then, to ask ‘black hair’ if the answer is yes and ‘curly hair’ if the answer is no, and so on.
The best strategy for playing Guess Who? From left to right we ask a question and depending on the answer we then ask the question on the right. The number in the last column is the number of questions needed for each character to be guessed.
Does this mean that we will always win when playing the optimal strategy? No. If we play the optimal strategy and the opponent plays a naive strategy, then he or she will defeat us 8% of the time. If we play the optimal strategy and the opponent plays a greedy strategy, then he or she expects to win 29% of the time.
You can play the game online here! …but unfortunately, they used different characters, so the strategy above does not work here… 🙁
And now that Guess Who? has been cracked…
Now that you have mastered the basic Guess Who?, you can try Guess Who?². This is a much more exciting and complicated game, which is based on the regular Guess Who? but with a twist. Each player picks two cards instead of one and the same proceeds like the normal Guess Who?, except that now the questions are something like are both of your persons males? or is exactly one of your persons bold? and at least one of your characters wears glasses?. The first player that guess both characters wins the much more complicated and exciting Guess Who?².
More from Chalkdust
Closing the first Black Mathematician Month
Reflecting on what we've learnt over the past few weeks.
In conversation with Vernon Morris
The co-author of a recent paper on diversity in professional STEM societies talks about access to science.
In conversation with Talitha Washington
Meet Talitha Washington, an activist, mathematician, and professor
In conversation with Jonathan Farley
We spoke with Jonathan Farley about his research and experiences as a black mathematician.
In conversation with Tanniemola Liverpool
As part of Black Mathematician Month, we spoke to the Bristol University professor about access schemes and the importance of mentors.
In conversation with Olubunmi Abidemi Fadipe-Joseph
Meet Olubunmi Abidemi Fadipe-Joseph, an active promoter for women in mathematics from Nigeria