The Game Show Forum

The Game Show Forum => The Big Board => Topic started by: rjaguar3 on August 11, 2008, 04:51:05 PM

Title: Where in the World Is Carmen Sandiego? analyzed
Post by: rjaguar3 on August 11, 2008, 04:51:05 PM

Since I had nothing better to do, I created an Excel spreadsheet to compute the probabilities of each player winning the 2nd round ("pick-a-location").  I assumed optimal strategy by both players (perfect memory, "using some strategy" when picking a key item in the wrong order, and selecting so that known key items will fall in the right place in the contestant's turn), and that neither player could effectively pass their turn.  The data are analyzed on the basis of the number of distractor locations remaining and number of key items remaining, and the probabilities in the table correspond to the probability that the player whose turn it is will eventually win:

  0key 1key 2key 3key
00 100% 100% 050% 050%
01 100% 050% 050% 050%
02 100% 067% 050% 050%
03 100% 050% 050% 050%
04 100% 060% 050% 050%
05 100% 050% 050% 050%
06 100% 057% 050% 050%
07 100% 050% 050% 050%
08 100% 056% 050% 050%
09 100% 050% 050% 050%
10 100% 055% 050% 050%
11 100% 050% 050% 050%
12 100% 054% 050% 050%

Note that when more than one key item is remaining, each player has an equal chance of winning.  For two key items, this is because the first key player is just as likely to find the prior key item in order (and thus will have the turn at the 1 key item level) as to find the wrong key item (which would give the 2nd player that opportunity after the 1st player "uses some strategy").  For three key items, the 50-50 chance results from the fact that the 2 key item chance of winning is always 50%.  This means that both players, when using optimal strategy, have an equal chance to win the round.

If loot-warrant-crook do not have to be found in the right order, the situation changes:

  0key 1key 2key 3key
00 100% 100% 100% 100%
01 100% 050% 033% 025%
02 100% 067% 067% 070%
03 100% 050% 040% 035%
04 100% 060% 060% 063%
05 100% 050% 043% 039%
06 100% 057% 057% 060%
07 100% 050% 044% 042%
08 100% 056% 056% 058%
09 100% 050% 045% 043%
10 100% 055% 055% 056%
11 100% 050% 046% 044%
12 100% 054% 054% 055%

Here the first player has the better chance of winning (about 11 times in 20).  But, let's revisit the assumption that the players cannot effectively pass.  If player 1 uncovers a footprint on the first turn, then player 2's chance of winning is less than 50%.  By picking the same location, however, he throws the ball back into player 1's court, and enjoys a 56% chance of winning if player 1 breaks the stalemate.  Similar results hold when there are an odd number of distractor locations left.  Thus, with optimal strategy and effective passing allowed, the no-order Carmen Sandiego game never terminates.

Title: Where in the World Is Carmen Sandiego? analyzed
Post by: TLEberle on August 12, 2008, 09:39:19 PM

[quote name=\'rjaguar3\' post=\'193808\' date=\'Aug 11 2008, 01:51 PM\']Thus, with optimal strategy and effective passing allowed, the no-order Carmen Sandiego game never terminates.[/quote]Well, the first player should have an advantage, since he had more points coming out of round one, right? (unless it was tied). Now, I was never keen on round two anyway, since it seems like nothing more than dumb luck with a soupçon of memory thrown in (and even that was just in remembering what's been visited), but there are a few things I can't wrap my head around.

How can you tell what the chances are for either person? They have a 1 in N chance of finding a relevant bit of information, and if they don't, N keep shrinking until someone wins. The only advantage seems like it would go to the player who has the first pick per cycle.

And in the format where you were allowed to violate police code by arresting the crook without evidence or due process, why would the second player stalemate? In order to win, you have to play the game, and that entails looking at new information. Just picking the same already chosen landmark seems like it would be self-defeating for either player.

Unless there's something that I missed in the original, then I apologize.

Title: Where in the World Is Carmen Sandiego? analyzed
Post by: rjaguar3 on August 13, 2008, 01:30:53 AM

[quote name=\'TLEberle\' post=\'193872\' date=\'Aug 12 2008, 08:39 PM\']
[quote name=\'rjaguar3\' post=\'193808\' date=\'Aug 11 2008, 01:51 PM\']Thus, with optimal strategy and effective passing allowed, the no-order Carmen Sandiego game never terminates.[/quote]Well, the first player should have an advantage, since he had more points coming out of round one, right? (unless it was tied). Now, I was never keen on round two anyway, since it seems like nothing more than dumb luck with a soupçon of memory thrown in (and even that was just in remembering what's been visited), but there are a few things I can't wrap my head around.

How can you tell what the chances are for either person? They have a 1 in N chance of finding a relevant bit of information, and if they don't, N keep shrinking until someone wins. The only advantage seems like it would go to the player who has the first pick per cycle.
[/quote]

You can basically average over all possibilities.  The recursion works something like this, if there are n key items to be found and m distractors remaining, and P(n,m) is the probability that the player whose turn it is will eventually win, then P(n,m) satisfies this recursion (when order matters):

P(0, m) = 1 [if all the key items have been found, it's just a matter of picking them in order]
P(n, m) = (1/(n+m))*P(n-1,m) [you found the first key item that you needed]
             + ((n-1)/(n+m))*(1-P(n-1,m)) [you found a key item, but it was out of order, so you "use some strategy" and allow the second player to get first crack at the new position]
             + (m/(n+m))*P(1-P(n,m-1)) [when m is not 0] [you found a distractor, so it's now the opponent's turn to play, and he has one less distractor to worry about]

When order matters, the recursion is similar [I will use Q(n,m) to denote the probability for the unordered game]
Q(0, m) = 1 [if all the key items have been found, it's just a matter of picking them]
Q(n, m) = (n/(n+m))*Q(n-1,m) [you found a key item, and it's still your turn in the new position]
             + (m/(n+m))*Q(1-Q(n,m-1)) [when m is not 0] [you found a distractor, so it's now the opponent's turn to play, and he has one less distractor to worry about]

You saw my handwaving argument above, so I'll offer a formal proof by induction that the ordered game amounts to no more than a coin-flip when there are at least two key items left.  (Feel free to skip over this if you're really not that interested.)

Quote

Suppose there are two key items.  I will prove that P(2,m)=0.5 by induction.  First, let m=0.  Then P(2,0)=(1/2)*P(1,0)+(1/2)*(1-P(1,0))=0.5P(1,0)+0.5-0.5P(1,0)=0.5.  Now assume that P(2,m)=0.5 for m=k.  Then P(2,k+1)=(1/(3+k))*P(1,k+1)+(1/(3+k))*(1-P(1,k+1))+((1+k)/(3+k))*(1-P(2,k))=(1/(3+k))*P(1,k+1)+1/(3+k)-(1/(3+k))*P(1,k+1)+((k+1)/(k+3))*0.5=1/(3+k) + (0.5k+0.5)/(3+k)=(1.5+0.5k)/(3+k)=0.5.  So P(2,m)=0.5

To show that P(n,m)=0.5 when n>=2, I will now use induction on n.  We have already proven the n=2 case above.  Let P(n,m)=0.5 for all m when n=r.  Now I will induct on m.  When m=0, note that P(r+1,0)=(1/(r+1))*P(r,0)+(r/(r+1))*(1-P(r,0))=(1/(r+1))*0.5+(r/(r+1))*0.5=((r+1)/(r+1))*0.5=0.5.  Now, let P(r+1,m)=0.5 for m=k.  Then P(r+1,m+1)=(1/(r+m+2))*P(r,m+1)+(r/(r+m+2))*(1-P(r,m+1))+((m+1)/(r+m+2))*(1-P(r+1,m))=(1/(r+m+2))*0.5+(r/(r+m+2))*0.5+((m+1)/(r+m+2))*0.5=((r+m+2)/(r+m+2))*0.5=0.5.  So the induction is complete, and P(n,m)=0.5 when n >= 2.  In particular, since 3 >= 2, then P(3,12)=0.5, which means that the original Carmen Sandiego game, under optimal strategy, is tantamount to a coin flip.

Quote

And in the format where you were allowed to violate police code by arresting the crook without evidence or due process, why would the second player stalemate? In order to win, you have to play the game, and that entails looking at new information. Just picking the same already chosen landmark seems like it would be self-defeating for either player.

Let's take an extreme case.  Suppose that there are just four locations that haven't been picked, and the three key items have yet to be found.  If you go first, you have to uncover all three key items without a miss.  Any mistake, and I will now know where the three key items are, and will win on my turn.  You will only uncover the three key items without a miss (3/4)*(2/3)*(1/2)=1/4 of the time, so, if you are the first to move from the impasse, I will win 75% of the time.

On the other hand, if you make the legal move of picking one of the 11 locations that we've already seen, you pass the turn to me.  If I pick from the unseen locations first, you will now win with 75% probability.  So my best move is to do the same thing and force the turn back to you.

Here, I must admit that the mathematical game differs from the game show.  If the players were to try such a strategy on the game show, the producers would probably stop tape and have both contestants forfeit winnings.  In that case, if both players knew the strategy, then it would become a game of chicken, rather than a stalemate.  However, in the mathematical game, there are no such consequences.

(I would also like to point out that 14-year-olds would probably never be able to figure out such a strategy, so that's kind of moot)

Quote

Unless there's something that I missed in the original, then I apologize.

You didn't miss anything.  It's okay.  Intuition sometimes leads even Math PhD's astray. (http://\"http://en.wikipedia.org/wiki/Monty_Hall_problem\")