Guess Who?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Magitek
Posts: 28
Joined: Fri Aug 24, 2007 5:54 am UTC

Guess Who?

Postby Magitek » Tue Jan 08, 2008 11:31 am UTC

So I saw this article on digg that linked to a video that used race as the attribute for a question for the Guess Who board game, and was amazed to see that question narrowed down the choices to one person. That got me thinking, is there an optimal strategy for Guess Who? What kind of questions would be most effective statistically? Any ideas?

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Guess Who?

Postby Robin S » Tue Jan 08, 2008 11:46 am UTC

Obviously, that depends on the group of people you're guessing from.
This is a placeholder until I think of something more creative to put here.

User avatar
Nexus_1101
Posts: 196
Joined: Mon Nov 05, 2007 2:59 pm UTC
Location: Brighton, England, UK
Contact:

Re: Guess Who?

Postby Nexus_1101 » Tue Jan 08, 2008 11:54 am UTC

proberbly the best stratergie would be to look at what fetures the majority of the remaining people have and ask if the other has that. then if they dont you may have just ruled out a large majority of you cards
HOSTING -> Heroquest
:idea: CHAOS BONUS :idea:

Code: Select all

IF (NOTFORUMGAME()) {
    postcount.add(1);
}

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Guess Who?

Postby jestingrabbit » Tue Jan 08, 2008 11:56 am UTC

Got an image of all the 'people' involved?

@Nexus: Goddamn that was hard to read... spellcheck?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Guess Who?

Postby Robin S » Tue Jan 08, 2008 12:08 pm UTC

In general, you're looking for questions which divide the group of remaining people in the ratio 1:x, where x minimizes either the mean or median number of guesses required to narrow it down to one person. I haven't done the maths, but I'm pretty sure x will prove to be as close as possible to 1 (this is effectively a binary search). On the other hand, what Nexus suggested would indicate that x was as close as possible to 0.
This is a placeholder until I think of something more creative to put here.

User avatar
scowdich
The Hedgehog
Posts: 771
Joined: Tue May 22, 2007 4:55 am UTC
Location: University of Illinois (Urbana-Champaign)
Contact:

Re: Guess Who?

Postby scowdich » Tue Jan 08, 2008 10:56 pm UTC

It is true that there is only one black person among the (thirty?) cards in Guess Who, but that means asking "Is your person black?" has a 1-in-30 chance of ending the game, and a 29-in-30 chance of putting you "behind" the other player, who will probably ask more useful questions, starting with gender, then moving on to things like glasses, facial hair, and hair color.

ErrantBit
Posts: 178
Joined: Sun Dec 09, 2007 1:53 am UTC

Re: Guess Who?

Postby ErrantBit » Tue Jan 08, 2008 11:55 pm UTC

As long as you can impose some order on the set of people you can just do a binary search. For any real set of people any of height, weight, age, length of index finger, etc. will probably work fine. For guess who you might have to get a bit more creative, but at the very least you could create a combination of properties that covered half of the people (and you don't care how homogeneous they are if you are willing to do the same thing on all subsequent turns).

If you are racing someone that isn't quite the case, since you care neither about worst case nor average time and only about the probability that you beat them. If you are both playing optimally you will both use a binary search but if one player deviates the other player might be able to capitalize by playing an otherwise suboptimal strategy. I don't know how hard that would be to figure out.

User avatar
BoomFrog
Posts: 1069
Joined: Mon Jan 15, 2007 5:59 am UTC
Location: Seattle

Re: Guess Who?

Postby BoomFrog » Wed Jan 09, 2008 6:14 am UTC

ErrantBit wrote:As long as you can impose some order on the set of people you can just do a binary search. For any real set of people any of height, weight, age, length of index finger, etc. will probably work fine. For guess who you might have to get a bit more creative, but at the very least you could create a combination of properties that covered half of the people (and you don't care how homogeneous they are if you are willing to do the same thing on all subsequent turns).

If you are racing someone that isn't quite the case, since you care neither about worst case nor average time and only about the probability that you beat them. If you are both playing optimally you will both use a binary search but if one player deviates the other player might be able to capitalize by playing an otherwise suboptimal strategy. I don't know how hard that would be to figure out.


If you do a pure binary search then you are garunteed to win in X turns, +/-1 turn for rounding. I haven't done the math but my gut tells me that if I know you are doing a purly binary search I can make a "gamble" each turn that will get me ahead if I win. And if I lose I can take a bigger gamble the next turn. I think that type of stratagy would give me a better then 50% chance of winning.
"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes." - Cronos

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Guess Who?

Postby phlip » Wed Jan 09, 2008 8:27 am UTC

Any strategy in Guess Who? will assign a prefix-free binary code to the different people, for whether they'd get a "yes" or a "no" for each question (along with a set of questions for each node in the decision tree... if you've gotten a "yes" followed by a "no", you want to ask a question that would be a "yes" for everyone whose code starts 101, and a "no" for everyone whose code starts 100). We want to build a Huffman coding for the people, so that the expected number of questions for each potential final answer is minimised... when all the people have the same probability of being the target, this happens when all the codes are the same length... and the questions essentially amount to a binary search.

My gut says you can't improve your strategy by making it dependent on what your opponent does... you're essentially playing two independent games, and it's just a race to see who'll finish first... you can't get any information about your guy from what your opponent does. Unless of course you know your opponent's strategy, and it takes into account your target guy (since your opponent knows who your target is)... then you might be able to get some clues from that... this is, however, unlikely.

My simple hackish Guess Who? strategy (which I devised many years after the last time I ever played Guess Who...):
List all the people in alphabetical order. Every turn, find the median, and ask "Is he/she after <whoever> alphabetically?"...
ErrantBit brought up this idea, but he didn't mention names, which are the easiest thing to sort them by.

[edit]
However, this is the mean time it'd take you to win. If your opponent is doing a binary search thing, and you know he's going to win in lg(n) questions, you merely need your median time to be better than that to have a good chance of winning, not necessarily your mean... hmm...
That suggests that a strategy that makes the majority of potential answers slightly shorter, even at the cost of making the remaining minority take significantly longer, is a better solution. And it might make sense to have the exact size of that majority, and how much shorter, to be variable, depending on how many potential suspects your opponent has left at the time (and thus how long it will probably be until they win).

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

ErrantBit
Posts: 178
Joined: Sun Dec 09, 2007 1:53 am UTC

Re: Guess Who?

Postby ErrantBit » Wed Jan 09, 2008 4:30 pm UTC

In general, to get a better median than a binary search you have to win in strictly less than log N (base 2) moves for strictly more than half of the suspects. But in log N - 1 = log (N / 2) moves there are only N / 2 distinct outcomes (one of which must indicate that you have to continue guessing), so this is certainly impossible--you can't even do as well as a binary search. So if the number of players is a power of 2 no strategy can beat binary search if the first player plays it. The best strategy for the other player is to do a binary search on one half of the suspects, with all of the other suspects "above" that group--they win if the answer is within that group and not the highest (since they cannot tell the highest from the rest of the suspects), and lose otherwise. So they can win with probability 1/2 - 1/N. I think any strategy that isn't binary search for the first player has a median strictly greater than log N, so that if the first player doesn't binary search the second player can win by binary searching.

If the number of suspects isn't a power of 2 it gets significantly more complicated.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Guess Who?

Postby Macbi » Wed Jan 09, 2008 5:35 pm UTC

phlip wrote:
My gut says you can't improve your strategy by making it dependent on what your opponent does... you're essentially playing two independent games, and it's just a race to see who'll finish first... you can't get any information about your guy from what your opponent does. Unless of course you know your opponent's strategy, and it takes into account your target guy (since your opponent knows who your target is)... then you might be able to get some clues from that... this is, however, unlikely.

Consider the situation where they have two people and you have lots (>3). Since they will win next turn, dividing your pool in half is a losing strategy. Instead the optimum strategy is to take a random guess at one person.

Moral: Your best case scenario must remain better than their worst case.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Guess Who?

Postby Nitrodon » Wed Jan 09, 2008 8:09 pm UTC

On each turn, you can make a decision based on the number of possibilities you and your opponent have left. The probabilities of winning from the (1,n) and (n,1) cases are obvious, and from there you can (iteratively or recursively) find optimal moves and winning probabilities for every combination.

Mr Cool
Posts: 7
Joined: Tue Sep 11, 2007 4:41 am UTC

Re: Guess Who?

Postby Mr Cool » Thu Jan 10, 2008 9:28 pm UTC

I'm just thinknig, and isn't there no possible strategy. The chance's would negate all the effects, ie. Say three people have ginger hair, and you ask them if they have ginger hair, that's a 10% chance you've knocked it down to 3 people, and a 90% chance that you haven't. So no matter what you do, the chance would equal out to be 50% no matter what. (90 + 10 / 2)

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Guess Who?

Postby skeptical scientist » Fri Jan 11, 2008 4:09 am UTC

Mr Cool wrote:I'm just thinknig, and isn't there no possible strategy. The chance's would negate all the effects, ie. Say three people have ginger hair, and you ask them if they have ginger hair, that's a 10% chance you've knocked it down to 3 people, and a 90% chance that you haven't. So no matter what you do, the chance would equal out to be 50% no matter what. (90 + 10 / 2)

All you've proven is that your expected size of remaining group is 50% of the previous size at each step. This certainly doesn't imply that there are no strategies.

For example, suppose the starting group size is 4 people. Then a strategy which splits the group in half at step 1 always wins in 2 guesses, whereas a strategy which splits the group into subgroups of size 1 and 3 at step 1 has a 25% chance of winning in one guess, a 25% chance of winning in two guesses, and a 50% chance of winning in three guesses, and therefore loses to the first strategy in an average game. So strategies are possible, and some are better than others.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Lexxicon
Posts: 2
Joined: Sun Jul 26, 2009 4:10 am UTC

Re: Guess Who?

Postby Lexxicon » Sun Jul 26, 2009 4:42 am UTC

But has anyone documented the raw datum?
How many of each sex?
How many with dark hair vs light hair vs no hair?
How many have facial hair vs not?
How many have blue eyes vs other colour?
Without this, a decision tree could not be made. You will note I stated light and dark rather that white, yellow, brown and blue as it more equally balances the two sides of the binary search. This is the way I believe the fastest path would be found. i.e. determine the sequence of question that roughly divides each resultant group by two (or as close as possible to this number). This on average should provide the best statistical probability of the least number of turns required to reach the target. i.e. In the cheap version of the game there are only 15 possibilities so a strategy of binary search should provide an answer thus :-
Turn 1, 15/2 leaves (7 or 8)
Turn 2, 7 or 8/2 leaves (3 or 4)
Turn 3, 3 or 4/2 leaves (1 or 2)
Turn 4, 1 or 2/2 => Found or 1.
Turn 5 Found.

Is there a better pattern that gives a better return? 1/3 groups instead of 1/2 groups
e.g. Turn 1, 15/3 break into 5 and 10
Turn 2, (3 and 2)/3 or (3 and 7)/3
Turn 3, (1 and 2)/3 or ((1 and 2)/3 or (2 and 5)/3)
Turn 4, Found or (1 and 1) or ((Found and 2)/3 or (2 and 2)/3)
Turn 5 Found or found and 1 or found and 1
Turn 6 Found.
So in this instance the 'Found's occur sooner and total turns possible finish earlier for the binary than the trinary model. But is there a better model in the case of 15 possibles? Is the game standardised or does it occur in multiple variants? Are there better questions that can be asked to narrow the choices in a binary fashion other than alphabetic names (assuming a random distribution of names produces a binary result)...

EricSeverson
Posts: 13
Joined: Sun May 31, 2009 9:27 pm UTC

Re: Guess Who?

Postby EricSeverson » Mon Jul 27, 2009 6:10 am UTC

I play Guess Who with the added rule that you can never repeat the same question twice, even from game to game. So this forces you pretty quickly to get creative and look for obscure differences between the characters, which makes the game a lot more interesting than it would be otherwise.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Guess Who?

Postby Qaanol » Mon Jul 27, 2009 5:33 pm UTC

Eric: That rule sounds like a lot of fun.

The game is played with a pool of 30 possibilities, right? If both players use a pure binary search to the end, the player who goes first will win 844/900 ≈ 93.8% of the time.

How about a binary search with caveats for last-second stabs in the dark?

If ever you get down to 3 possibilities while your opponent has fewer than 6, you ask a question that will cut your number of options to 1 or 2. If you get 1 of course you win. If you get 2, you immediately (and randomly) pick one and declare it your answer. If you get down to 4 possibilities while your opponent has fewer than 4, you ask a question that cuts your number of options to 2, and you randomly pick one to declare.

If your opponent does a pure binary search without any caveats, you'll win 768/900 ≈ 85.3% of the time by going first, and 448/900 ≈ 49.8% of the time by going second. Clearly this "with-stabs" strategy has an expectation to win 1216/1800 ≈ 67.6% of the time against the "without-stabs" strategy. (Of course, if you *knew* your opponent wouldn't stab, you also wouldn't stab when you went first, but would when you went second, and you'd win 1292/1800 ≈ 71.8% of the time overall.)

If both players use the with-stabs version, you'll win 480/900 ≈ 53.3% of the time by going first.

So, since we're in "Logic Puzzles"…

Why, when you have 3 options, should you only stab if your opponent has fewer than 6?
When you have 4, why only stab when your opponent has fewer than 4?
If you were playing with a pool size that could give you 5 options, when should you stab with 5?
Higher numbers?
wee free kings

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: Guess Who?

Postby HonoreDB » Thu Aug 06, 2009 12:45 am UTC

I think I have a simple, general solution.

Spoiler:
No matter what strategies are employed, in whatever combination, Player 1's expected number of turns is one fewer than Player 2's. The only thing that can cause Player 2 to win is luck. Therefore, Player 1 wants to decrease the variance as much as possible, while Player 2 wants to increase the variance as much as possible. So, optimally, Player 1 plays a binary search (or as close as the allowed questions permit) while Player 2 guesses a single person each turn.

Lexxicon
Posts: 2
Joined: Sun Jul 26, 2009 4:10 am UTC

Re: Guess Who?

Postby Lexxicon » Thu Aug 06, 2009 1:14 am UTC

We simply have a rule that if the second turn person guesses the correct person after the first has then it is a draw. :D i.e. no 1st person advantage as same number of turns to guess correctly.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: Guess Who?

Postby HonoreDB » Thu Aug 06, 2009 1:33 am UTC

Good idea. In that case whoever's "winning" wants minimum variance, and the other player wants to maximize variance. As long as both players do a binary search, neither player is winning, and if you change that situation your opponent gets to adjust before you do so it benefits the opponent more. So I think in that case both players do a binary search until they get unequal halves of an odd number.

Generic Goon
Posts: 18
Joined: Sun Jan 27, 2008 5:20 pm UTC

Re: Guess Who?

Postby Generic Goon » Fri Aug 07, 2009 4:36 pm UTC

Is there a requirement that all questions be answerable with yes or no? If not, you should be able to get it down to 1/3 each time by asking something that is unanswerable given certain conditions. For example,

"Is the person blond, OR is it a man AND the answer to this question is no"

Blond Man/Woman: Yes
Non-Blond Woman: No
Non-Blond Man: No Correct Answer

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Guess Who?

Postby Macbi » Fri Aug 07, 2009 5:36 pm UTC

Generic Goon wrote:Is there a requirement that all questions be answerable with yes or no?

Sadly, yes.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Guess Who?

Postby Qaanol » Mon Aug 10, 2009 8:46 pm UTC

HonoreDB wrote:Good idea. In that case whoever's "winning" wants minimum variance, and the other player wants to maximize variance. As long as both players do a binary search, neither player is winning, and if you change that situation your opponent gets to adjust before you do so it benefits the opponent more. So I think in that case both players do a binary search until they get unequal halves of an odd number.

Even then, binary for both works, because the difference between the number of options remaining for the two players will never exceed 1 after an equal number of turns. (Why?)

The optimal strategy is to go binary search until (if) after one question gets you to have 2 options left, if your opponent has fewer than 4 options then you immediately make a "final guess" / "accusation".

Pragmatic aside:
All of the above is assuming that your goal is to maximize your chances to win the game. However, in a lot of real-life occurrences of playing Guess Who?, you can often increase enjoyment of the game for both players and any spectators by employing a suboptimal strategy which introduces greater drama and allows your opponent to win most of the time.
wee free kings


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 12 guests