Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #1  
Old 11-14-2005, 02:40 AM
odawg09090 odawg09090 is offline
Junior Member
 
Join Date: Jan 2005
Posts: 28
Default Guess WHO game. Dominated by a little girl!

I recently played the child's game of Guess Who against a girl. The objective is simple, there are 24 characters defined by varying characteristics. Each player picks a character card at random and then you alternate asking questions to try to find out who the other person is ('Does your person have red hair?') etc. Being a computer scientist, I used a binary search whereby I asked questions that eliminated half of the remaining possible characters at a time. This gurantees guessing the answer in 6 questions, in the worst case.
Using this method, I lost the first 7 straight games because she would ask questions such as 'Does your character have glasses?'
Assuming she doesn't include her character, only 5/23 possible characters wear galsses. If I did have glasses, then after the first question her pool is down to 5 while mine is at 12.
If she was wrong about the glasses, she would follow up with an equally unlikely question. Say it was a 4/17.
Anyway. After losing to this seemingly luck-based strategy 7 straight tmes I had to ask myself if it didn't have some mathematical validity. I hope it's not inappropriate to ask how I would go about solving this game. What is the best strategy to guess their character faster than they can guess yours? Is it different if you have to go 2nd and start out a question behind? Like I said, my background isn't in game theory or probability. Any pointers, and especially the solution, would be greatly appreciated.
Reply With Quote
  #2  
Old 11-14-2005, 02:45 AM
Aaron_ Aaron_ is offline
Junior Member
 
Join Date: May 2005
Posts: 1
Default Re: Guess WHO game. Dominated by a little girl!

This is by far the funniest post I've read all month.

I'm done now... carry on...

Edit: How old was this little girl?
Reply With Quote
  #3  
Old 11-14-2005, 03:25 AM
Guest
 
Posts: n/a
Default Re: Guess WHO game. Dominated by a little girl!

[ QUOTE ]
This is by far the funniest post I've read all month.

I'm done now... carry on...

Edit: How old was this little girl?

[/ QUOTE ]

I'm wondering how old OP is! And why he's playing games with little girls?

[img]/images/graemlins/confused.gif[/img]
Reply With Quote
  #4  
Old 11-14-2005, 04:27 AM
J Chap J Chap is offline
Member
 
Join Date: Jun 2005
Location: Durham, NC
Posts: 77
Default Re: Guess WHO game. Dominated by a little girl!

this post is brilliantly funny.

your question seems to get at the root of the difference between heuristics and algorithms. (something tells me you know what I'm about to explain, but I'll do it, anyway, for the schn00bs.) Consider the task of locating the ketchup in the grocery store. a heuristic approach is like searching in the condiments aisle, then maybe over by the buns. an algorithmic approach is like starting in the front-left corner of the store, and searching up-and-down each aisle in a completely systematic way. The obvious differences are that heuristics can be faster, *IF YOU HAVE A LOGICAL BASIS FOR YOUR SHORTCUT*, but heuristics are gauranteed to work, at the cost of increased time and labor.

In the case of Guess Who, I can't see how this girl would have had any reasonable way of knowing which pot-of-gold questions to go for. (Hmmm..unless people tend to gravitate towards characters that look like them. Do you wear glasses? Would be an interesting study.) Assuming she hasn't been meticulously logging and pouring over data on your character-choosing patterns, I would say that your approach, in the long run, is +EV. She had some lucky guesses. To be safe, though, I would not pay attention to who you pick. Make sure you randomize your draws, just in case she has some amazing subconscious intuition for who you would pick. For instance, I realized that my brother seemed to choose Franklin like 74% of the time.

I'll bet that the girl who dominated you would be a good NLHE player, since she likes to go for the gold. It's a much more aggressive style of play, whereas yours is more passive and sure-fire. Out of curiosity, do you play NLHE or HE?

Anyway, those are my thoughts on the issue. I'd say go with the binary as long as you can, and post again when the statistics are like 3 SDs out of the ordinary.

BTW, what are you asking that's binary?
Reply With Quote
  #5  
Old 11-14-2005, 05:08 AM
SumZero SumZero is offline
Member
 
Join Date: Jul 2004
Posts: 73
Default Re: Guess WHO game. Dominated by a little girl!

I think there is a time to go for those gold mine (or as I like to call them, longball) type questions, but generally only after your opponent hits their goldmine question. That is binary search is the best to do if you can. But if you opponent does a non-optimal search much of the time you can stick with binary search and win. Think of picking numbers between 1-100 where you can ask "is it higher/lower than X" OR you can ask "is it X?". If you start out and say "is it higher than 50" and get yes. Then your opponent says "is it less than 20?" and you have to say yes. Now your opponent has only 19 numbers left to pick from while you have 49. And because each time you pick your midpoint question you aren't also winning if they get the midpoint it may be time for you to launch a "is it less than 61" or "is it more than 90" type question in order to try to out longball the longball strategy. But 80% of the time their longball will fail and you are way ahead and can stick with your binary search. And at some point when they get really close to the number when they are ahead of you it pays to just start guessing is it x? rather than trying to narrow your range. In esscence because all you are doing is trying to beat them or else you lose. You don't get credit for being close to guessing the right answer if you lose.
Reply With Quote
  #6  
Old 11-14-2005, 05:27 AM
Aaron_ Aaron_ is offline
Junior Member
 
Join Date: May 2005
Posts: 1
Default Re: Guess WHO game. Dominated by a little girl!

[ QUOTE ]
[ QUOTE ]
This is by far the funniest post I've read all month.

I'm done now... carry on...

Edit: How old was this little girl?

[/ QUOTE ]

I'm wondering how old OP is! And why he's playing games with little girls?

[img]/images/graemlins/confused.gif[/img]

[/ QUOTE ]

From the very first two sentences, I pictured an innocent 7-year-old girl in pigtails, and a 20-something masters student who was baby sitting for a friend on the weekends to make some extra cash.

[ QUOTE ]
Using this method, I lost the first 7 straight games because she would ask questions such as 'Does your character have glasses?'

[/ QUOTE ]

I almost fell off my chair. I'd pay to hear the full story behind this post.
Reply With Quote
  #7  
Old 11-14-2005, 08:27 AM
BOTW BOTW is offline
Junior Member
 
Join Date: Sep 2002
Posts: 6
Default Re: Guess WHO game. Dominated by a little girl!

If you were to provide the classes of items, I'm sure you could set up a good guessing strategy.

It looks like her strategy is better than yours, but it depends on how things are divided up and the sizes of the sets. If she goes through and guesses the smallest set, each of the 24 names, she gets at max 6 guesses before your win, so she only wins 25% of the time.

However, assume you divide in half and she can divide in thirds (until there are only a few items left or she sees she needs a new strategy because you are about to win).

If you haven't already won, she wins (or ties) 1/3 of the time at every step along the way; 2/3 of the time she moves on to the bigger remaining set.

That is, in the first step, she has either 8 items to choose from (for a win/tie) or is left with 16 (you have 12).

In the second step from 16 items, 1/3 of the time she has 6 items (tied with you), or falls behind with 10. (So, 1/3 + 2/9 = 5/9 times she is winning or tied with you now.)

So, how often does she get behind in the first two steps? 2/3 * 2/3 = 4/9. It appears that she gets behind (2/3)^n times in n steps, or the more steps the binary search takes, the more likely she is tied or winning.



Looking at the guessing numbers problem (and rounding), binary guessing of 50, then 25 or 75 etc. looks like it will take a max of seven steps.

She guesses 66 (guess one). 1/3 of the time she has 33 numbers left, 2/3 66 left.

If it is 33, then she at least ties, (binary is at 50).

If it is 66, then it will be 22 (at least ties) or 44 (guess two) (binary is at 25).

If it is 44, then it will be 14 (at least ties) or 30 (guess three) (binary is at 13).

If it is 30, then it will be 10 or 20 (guess four) (binary is at 7).

If it is 20, then it will be 7 or 14 (guess five) (binary is at 4).

If is is 14, then it will be 4 or 10 (guess six) (binary is at 2).

If it is 10, then it will be 3 or 7 (guess seven) (binary is at 1 and done).

So, she falls behind at guess four in the worst case. How often does she fall behind binary guessing? 2/3 * 2/3 * 2/3 * 2/3 = 16/81 ==> guessing in thirds is tied or ahead the majority of the time. (Or I'm too tired to think straight, someone correct me.)
Reply With Quote
  #8  
Old 11-14-2005, 11:41 AM
BOTW BOTW is offline
Junior Member
 
Join Date: Sep 2002
Posts: 6
Default Re: Guess WHO game. Dominated by a little girl!

The more I thought about this the more I'm not sure what I was talking about, so just ignore math attempts in the previous post and look at the pretty pictures in this one.

Your decison tree to get the guy could look like this:


And hers like this:


If it is guy 1 or 3, she will never win, but she is doing well.

If you use a better tree:


You'll do better. She'll still get those quick wins in that kill your spirit, but you'll grind out victory.
Reply With Quote
  #9  
Old 11-14-2005, 12:26 PM
bobman0330 bobman0330 is offline
Member
 
Join Date: Aug 2004
Posts: 52
Default Re: Guess WHO game. Dominated by a little girl!

Guess Who is rigged.
Reply With Quote
  #10  
Old 11-14-2005, 02:42 PM
alThor alThor is offline
Junior Member
 
Join Date: Mar 2004
Posts: 6
Default Re: Guess WHO game. Dominated by a little girl!

This is an interesting question. Binary search minimizes average search time, but in a 2-player game like this, one should be more concerned with median type statistics than EV type stats. It is evident that the players should not follow a binary search always.

Consider a version of this game where you both have to guess a random integer 1,2,3,4. (To simplify, suppose your integers are independent, so that it is possible that you both have to guess the same integer.)

If player one uses a binary search, he first asks "Higher or lower than 2.5?" Then he will guess specific integers after that, and will find the right integer in either two or three guesses, with 50-50 probability.

If player two plkays this strategy, he will also get the right answer in two or three guesses, with 50-50 probability. But since he moves second, he wins with only 25% probability.

So suppose instead player 2 simply guesses an integer right away! That already gives him a 25% chance of winning if player 1 uses binary. But in addition, if he's wrong and player 1 fails to get the answer on guess #2, player 2 has an additional 33% shot at winning on his second guess, for an overall probability of 25% + (.75)(.5)(33%) = 3/8.

The optimal strategy in this game will be complicated by the fact that, with more integers, when an opponent makes an aggressive move, your response is dependent on whether he succeeded in narrowing the field a lot.

alThor
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 01:23 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.