{"id":160,"date":"2020-02-26T15:01:06","date_gmt":"2020-02-26T15:01:06","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/edward-mellor\/?p=160"},"modified":"2020-03-31T11:32:33","modified_gmt":"2020-03-31T11:32:33","slug":"optimal-strategy-for-guess-who","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/edward-mellor\/2020\/02\/26\/optimal-strategy-for-guess-who\/","title":{"rendered":"Optimal strategy for ‘Guess Who?’?"},"content":{"rendered":"\n

As I was growing up, one of my favourite games was Guess Who?. This two player game was originally created by Theora Design<\/a> but is now owned by Hasbro<\/a>.  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\u2019s character. <\/p>\n\n\n\n

Alex<\/td>Alfred<\/td>Anita<\/td>Anne<\/td>Bernard<\/td>Bill<\/td>Charles<\/td>Claire<\/td><\/tr>
David<\/td>Eric<\/td>Frank<\/td>George<\/td>Herman<\/td>Joe<\/td>Maria<\/td>Max<\/td><\/tr>
Paul<\/td>Peter<\/td>Philip<\/td>Richard<\/td>Robert<\/td>Sam<\/td>Susan<\/td>Tom<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

The player who eliminates all but one of the possible candidates\nin the least amount of moves is the winner. If both players correctly identify\ntheir opposition\u2019s character in the same amount of moves it\u2019s a draw.<\/p>\n\n\n\n

I recently saw a video by Mark Rober<\/a> 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.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

There is an unlimited amount of questions that could be asked but\nmany of these are equivalent.  For\nexample, the answer to \u201cIs your person male?\u201d, \u201cIs your person female?\u201d and \u201cis\nyour person called Anita, Anne, Claire, Maria or Susan?\u201d will all rule out the\nsame candidates. <\/p>\n\n\n\n

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. <\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Thus in our first turn we effectively have (23-1)\/2=11 choices for\nwhat to do. <\/p>\n\n\n\n

The best choice becomes clear if we consider the extreme cases. If\nm=1 we could get the correct solution straight away but this will only happen 1\nin every 23 tries. The rest of the time we will only rule out one candidate. If\nwe proceed to guess one candidate each time it will take us on average 11.5\nguesses. On the other hand if we take m to be as big as possible we will rule\nout at least 11 candidates so it will take at most 5 guesses.<\/p>\n\n\n\n

This idea is explained in more detail in the following video by Mark Rober:<\/p>\n\n\n\n

\n