As I was growing up, one of my favourite games was Guess Who?. This two player game was originally created by Theora Design but is now owned by Hasbro. Each player is allocated one of 24 possible characters from the table of names below. The players then take turns to ask yes/no questions to guess the other person’s character.
| Alex | Alfred | Anita | Anne | Bernard | Bill | Charles | Claire |
| David | Eric | Frank | George | Herman | Joe | Maria | Max |
| Paul | Peter | Philip | Richard | Robert | Sam | Susan | Tom |
The player who eliminates all but one of the possible candidates in the least amount of moves is the winner. If both players correctly identify their opposition’s character in the same amount of moves it’s a draw.
I recently saw a video by Mark Rober online claiming to have a best Guess Who? strategy and so being a mathematician I wanted to check the numbers. In this blog we will consider what constitutes a good question and whether Rober really does have an optimal strategy.
There is an unlimited amount of questions that could be asked but many of these are equivalent. For example, the answer to “Is your person male?”, “Is your person female?” and “is your person called Anita, Anne, Claire, Maria or Susan?” will all rule out the same candidates.
Any question will split the remaining candidates into two groups. Since each candidate that has yet to be ruled out is equally likely, we can consider any two questions equivalent if the smaller of the groups they each identify contain the same number of candidates.
Suppose we have n candidates remaining. Since we are asking a question, we must have that n is greater than 1 and since we can automatically rule out our own character we also know that n can be at most 23.
We can now define a question by the size of the smaller of the two groups that it splits the candidates into. We will call this number m. If m=0 the question is giving us no new information and therefore does not help us. We will therefore assume m is at least 1. Since m is the size of the smaller group it is at most n/2 or (n-1)/2 if n is odd. Note that such a question will always exist since for any candidate we can ask if their character name comes before them alphabetically.
Thus in our first turn we effectively have (23-1)/2=11 choices for what to do.
The best choice becomes clear if we consider the extreme cases. If m=1 we could get the correct solution straight away but this will only happen 1 in every 23 tries. The rest of the time we will only rule out one candidate. If we proceed to guess one candidate each time it will take us on average 11.5 guesses. On the other hand if we take m to be as big as possible we will rule out at least 11 candidates so it will take at most 5 guesses.
This idea is explained in more detail in the following video by Mark Rober:
The strategy laid out in Rober’s video is therefore to always try to ask a question that divides the candidates into two groups that are as even as possible. (i.e. choose m to be as big as possible)
But is this always the best approach?
If our opponent guesses correctly first time our only chance to draw is to also make a guess.
Similarly if we suppose our opponent went first and their first question rules out all but two candidates, they are then guaranteed to win on their next question. With our current strategy it is impossible for us to win in two moves and so in this situation it might be better to play more aggressively by asking a question with a smaller m.
Our choice of move could also depend on how we weight draws verses wins. If we want to win outright then our only option is to make a guess. If we would rather win but are happy with a draw we need to make some calculations. Again we will only consider the two extreme cases:
Option 1: Make 2 random guesses
- This gives us a 1/23 chance to win and (22/23)(1/22)=1/23 chance to draw
Option 2: Divide the group as evenly as possible then make a guess
- This has zero of winning and (11/23)(1/11)+(12/23)(1/12) =2/23 chance to draw
Therefore, it is always better to make guesses in this situation. This highlights that although the Guess Who? strategy described by Rober is very good in most situations if we take the other players actions into account it is not optimal.