wu :: forums « wu :: forums - three-way pistol duel » Welcome, Guest. Please Login or Register. Jan 29th, 2022, 4:31am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, Icarus, Eigenray, towr, william wu, Grimbal, ThudnBlunder)    three-way pistol duel « Previous topic | Next topic »
 Pages: 1 2 3  ...  5 Reply Notify of replies Send Topic Print
 Author Topic: three-way pistol duel  (Read 61118 times)
klbarrus
Newbie

Posts: 29
 three-way pistol duel   « on: Jul 25th, 2002, 5:27pm » Quote Modify

Three-way Pistol Duel

You are A, 1/3 accuracy
B is 1/2 accurate
C is always accurate

x X y = x shoots at y

As A, you can either:
1) shoot at B
2) shoot at C
3) shoot at the ground (deliberately miss).

1) a X b
if you hit (1/3 of the time), you lose, and C fires next and takes you out
otherwise (2/3 of the time) b X c as C is B's biggest threat.  1/2 the time B takes out C, which leaves a X b to resolve.  1/2 the time B misses, C kills B, and you have 1/3 chance to take out C before he takes you out.

First, a X b (with C out of the picture) is
1/3 + 2/3 * 1/2 * 1/3 + 2/3 * 1/2 * 2/3 * 1/2 * 1/3 + ...
= 1/3 + (1/3)^n * 1/3
= 1/3 + 1/6 = 1/2

So a X b (with C there) is
2/3 * 1/2 * 1/2 + 2/3 * 1/2 * 1/3 = 10/36 chance of winning

2) a X c
if you hit C, B shoots are you, 1/2 the time you survive and it boils down to the a X b (C out of picture) calculated above.
if you miss C, B shoots at C, 1/2 the time hits and it boils down to a X b above.  1/2 the time B misses, C takes B out, and you have 1/3 chance to take C out.

So a X c is
1/3 * 1/2 * 1/2 + 2/3 * 1/2 * 1/2 + 2/3 * 1/2 * 1/3
= 1/12 + 1/6 + 1/9 = 13/36 chance of winning

This makes sense, relatively, as you best hope is to take out the most accurate shooter.

3) option 3, you skip your turn by firing into the ground.
b X c, 1/2 the time B hits and it becomes a X b calculated above.  The other 1/2, C takes out B and you have 1/3 chance to take out C.

So, A miss on purpose is
1/2 * 1/2 + 1/2 * 1/3 = 1/4 + 1/6 = 15/36 chance of winning.

So your best option, at 15/36 = 41.7% of winning, is to miss your first shot on purpose!!
 « Last Edit: Aug 28th, 2003, 6:23pm by Icarus » IP Logged
Andrew Ooi
Guest

 Re: three-way pistol duel   « Reply #1 on: Jul 29th, 2002, 8:17pm » Quote Modify Remove

You are not answering within the constraints of the problems: who do you shoot first?

The answer is the 100% one. Why?

If shoot the 50% first:
P(survive)=P(kill 50% & survive) + P(miss 50% & survive)
P(survive)=0 + P (miss 50% & survive)

[ 0 because you get killed next by 100% ]

If shoot the 100% one first:
P(survive)=P(kill 100% & survive) + P(miss 100% & survive)

Claim: P(miss 50% & survive) = P(miss 100% & survive) because in both instances there are 3 cyborgs standing and it's the 50%'s turn to shoot. (*)

So therefore you should shoot the 100% first.

(*) I am of course ignoring the possibility that the cyborgs might change their strategy depending on who you shoot at first.
 IP Logged
klbarrus
Newbie

Posts: 29
 Re: three-way pistol duel   « Reply #2 on: Jul 29th, 2002, 9:28pm » Quote Modify

Actually the question is careful to say "what should you shoot at in round 1 to maximize your chances".  The thing that maximizes your chances is to miss your first shot on purpose and let the other two take their shots.

As you noted, you do have a better chance of surviving by shooting at C (100% accurate), but you can do even better by skipping your turn.
 IP Logged
Chronos
Full Member

Gender:
Posts: 288
 Re: three-way pistol duel   « Reply #3 on: Aug 15th, 2002, 5:31pm » Quote Modify

Actually, depending on exact interpretation of the problem, you can do much better.  Am I right to assume that nobody else shoots until you, the least accurate shooter, has shot?

If that's the case, then your optimum strategy is to keep your gun in its holster forever.  Since you never finish your turn, nobody else ever starts a turn, nobody ever gets shot, and you can all go have a drink of transmission fluid down at the cyborg bar (that is what cyborgs drink down at the bar, isn't it?).
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #4 on: Aug 16th, 2002, 6:01am » Quote Modify

Nah, that's not the spirit of the problem.  You can assume you each have a minute or whatever during which you can take your shot.

Another interesting thought:  Surprisingly, the answer changes as you shift the three probabilities around.  What is the general strategy for X(x,y,z), ..., Z(x,y,z)?  I've actually never sat down to crank out the math -- I think it's probably not too hard, but somebody let me know if it is!

Best,
Eric
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
tim
Junior Member

Posts: 81
 Re: three-way pistol duel   « Reply #5 on: Aug 16th, 2002, 5:56pm » Quote Modify

This problem is more subtle than it looks.  All the solutions to date have been assuming that B and/or C will fire at another cyborg.

Is it in their interest to do so? Presumably their objective is also to "maximise their survival over time".

Let's consider "pure" strategies. That is, in any given situation the target of the shot is determined solely by the situation. Denote the situation by the surviving cyborgs, with the one to shoot listed first.

The cases CA and CB are clear: C should shoot at the other, and win with certainty.
Given that, AC and BC are equally clear: A or B must shoot C.

Let's draw up a matrix of expected survival based on pure strategies, with A's chances / B's chances:

B's strategy
Try Miss
A's  Try   .5 / .5   1 / 0
Miss   0 / 1    1 / 1

This is looking suspiciously like a Prisoner's Dilemma payoff matrix!

That was for the simplified problem where their strategies are purely based on the current situation. The full problem turns out very similar to the iterated Prisoner's Dilemma, with the corresponding good strategy "shoot only if shot at".

This means that if it were up to A and B alone, neither should shoot.

Adding C complicates the picture. If C shoots at B, A will have to shoot back, dropping C's chances of survival to 2/3. If all are following the same "shoot only if shot at" strategy, all three survive indefinitely.  This certainly "maximises survival over time".

Analysing their best strategies in case one deviates is making my head hurt, so I'll stop here
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #6 on: Aug 16th, 2002, 7:07pm » Quote Modify

Tim et al.,

First, I certainly agree that you have to determine B and C's strategy -- that is a big part of the problem, and an even bigger part of the generalized problem.

However, I interpret the goals slightly differently:  If you set the goals to being "to win" rather than "to survive", then the problem reverts to the interpretation everyone has been following.  The lower right hand quadrant of your prisoner's dilemma becomes 0/0, and everything is clear again.

Best,
Eric
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Jeremiah Smith
Full Member

Beep!

Posts: 172
 Re: three-way pistol duel   « Reply #7 on: Aug 16th, 2002, 10:45pm » Quote Modify

on Aug 16th, 2002, 7:07pm, Eric Yeh wrote:
 If you set the goals to being "to win" rather than "to survive", then the problem reverts to the interpretation everyone has been following.

Wait...isn't this a situation where "to win" equals "to survive"? The only way to win is to not get shot.
 IP Logged
tim
Junior Member

Posts: 81
 Re: three-way pistol duel   « Reply #8 on: Aug 17th, 2002, 2:32am » Quote Modify

jeremiahsmith: It is true that you must survive in order to win, but you need not win in order to survive. The problem merely asks for A to maximise survival.

Eric: Yes, if you change the conditions of the problem you do get the above solutions.

It may even have been intended to mean "greatest chance of winning". I thought I'd solved this one ages ago, and it was only when looking for problems I hadn't solved yet that I realised that the problem didn't actually say "win".

I like my interpretation better for three reasons:
1) It does actually say "survival"
2) I found the "win" problem too easy.
3) "Survival" is a far more interesting and intricate problem, particularly if you allow some chance of defection.
 IP Logged
Jeremiah Smith
Full Member

Beep!

Posts: 172
 Re: three-way pistol duel   « Reply #9 on: Aug 17th, 2002, 3:34am » Quote Modify

on Aug 17th, 2002, 2:32am, tim wrote:
 but you need not win in order to survive.

Isn't the whole point of a duel to be the last man/woman/cybernetic organism standing? The riddle even says that the duel keeps on going and going...at some point, two cyborgs are gonna be toast, and the last one standing will be the winner. (Unless he shoots himself.) Eventually, everyone who's not the winner will be dead. Winning == surviving.
 IP Logged
tim
Junior Member

Posts: 81
 Re: three-way pistol duel   « Reply #10 on: Aug 17th, 2002, 3:55am » Quote Modify

Quote:
 at some point, two cyborgs are gonna be toast, and the last one standing will be the winner.

Only if it is in the interests of one of the cyborgs to start shooting. It appears that it is not. None of them would want to shoot at each other, so none of them get shot.

Quote:
 The riddle even says that the duel keeps on going and going

Yes, and the goal is to "maximise survival over time". If it keeps going and going and going, then all the cyborgs have maximised their survival over time. That's a much better survival rate for all of them than if any of them start shooting to kill.

If you believe that one of them should shoot to kill: who should shoot first, at whom, and why does it maximise their survival?  Does it still hold if A has 90% chance to hit, B has 95%, and C has 100%?  Why or why not?
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #11 on: Aug 17th, 2002, 8:55am » Quote Modify

Jeremiah,

Tim's Reply #5 had the details on why winning != surviving, or you can read it in my last msg adjusting Tim's payoff square for a quantitative difference.

Jeremiah + Tim,

Regarding the wording and the word "survival", you know there is always a chance of mistranslation in copying the problem ot the board.  I suspect this was just a problem with a minor subtlety.

Tim,

Hmm, 1) I answered above. 2)+3):  I'm not acutally sure that the other method is tougher.  I agree that the problem is not terribly hard as stated, but in the other example it is clear that you simply do not shoot.  Even allowing for "defection", there is simply no reason to unless you add a payoff for winning beyond surviving.  As you've defined it thus far, the lower right square is clearly a Pareto optimal equilibirum point.

Best,
Eric
 « Last Edit: Aug 17th, 2002, 8:57am by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #12 on: Aug 17th, 2002, 9:24am » Quote Modify

BTW Tim,

If you are looking for more fun:  Have you worked out the generalization I mentioned for this problem?  It may not be that tough, but it's potentially interesting.

My checkerboard problem is also way open.  Have you dont the 1000 wires problem?  Have you done my Past, Present, Future (didn't see any posts there)?  Duck in the pond generalization:  Find the ratio of speeds r which is the boundary between who wins the game (I haven't worked that out yet, it's sufficiently tough).  Finally, the lion tamer question is still open, since all the answers posted (including mine) were wrong.

If you still need more, let me know!  I will try to post some more sometime, but I am pretty bogged down w stuff.

Best,
Eric
 « Last Edit: Aug 17th, 2002, 9:27am by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
tim
Junior Member

Posts: 81
 Re: three-way pistol duel   « Reply #13 on: Aug 17th, 2002, 10:30pm » Quote Modify

Eric: Quote:
 Have you worked out the generalization I mentioned for this problem?  It may not be that tough, but it's potentially interesting.

No, but that generalization is what led me back to this puzzle and the realization that I had misread the goal the first time.

Some regions of the parameter space have no solution. A simple example is p(A) = p(B) = p(C) = 100%. Whoever shoots to kill first loses with certainty. If they wait for someone else to shoot, they may have a 50% chance.

Let's consider a slight variation on the duel: each round, there is some independent small probability that one of the cyborgs will suffer a programming glitch that causes it to shoot at a particular one of the other two, and continue firing at it each round until one of them is dead. Both the cyborg with the glitch and its target are random.

Let pA < pB < pC, and let qX = 1-pX for each X.

In the absence of a glitch, neither B nor C will want to shoot at A until the other is dead. So it is always in A's interest not to shoot first.
If B and C have a shoot-out, B has a pB/(1-qB.qC) chance of surviving C, followed by a qA.pB/(1-qB.qA) chance of winning the shoot-out with A. B's total chance is qA.pB^2/(1-qA.qB)(1-qB.qC). C's chance is qA.qB.pC^2/(1-qA.qC)(1-qB.qC).  For qA sufficiently low, both B and C have better chances of winning by waiting for a glitch.

The original problem can be considered a limiting case as P(glitch) -> 0.

Quote:
 My checkerboard problem is also way open.  Have you dont the 1000 wires problem?  Have you done my Past, Present, Future (didn't see any posts there)?  Duck in the pond generalization:  Find the ratio of speeds r which is the boundary between who wins the game (I haven't worked that out yet, it's sufficiently tough).  Finally, the lion tamer question is still open, since all the answers posted (including mine) were wrong

I've seen (and done) the checkerboard problems before. Yes, I've done the 1000 wires problem, and a couple of generalizations. I've done PPF as well. I've also done the Duck in Pond problem and generalization. You have more information on the Lion Tamer problem -- why haven't you posted it?
 IP Logged
Aaron Kincaid
Guest

 Re: three-way pistol duel   « Reply #14 on: Oct 18th, 2002, 9:57am » Quote Modify Remove

The question is asking for the probabilities and that means not trying to predict the other cyborgs actions. You must take into account the probability of them shooting at you as well as the probability of them hitting you.

Now, it is obvious that you should not shoot at B since hitting him would ensure your death, but should you shoot at C? Lets compare the best cases from these 2 options.

Let's say you shoot at C and kill him. You now have a 50% chance of surviving to the next round then a 33% chance of winning in round 2. This is the best case for you shooting at C.

.33 x .50 x .33 = .05445 or 5.445% chance of winning

Now lets look at missing intentionally. There are 3 possible scenarios when B shoots. B kills C, B kills you, and B misses both. We will ignore B killing you since we are comparing best cases.

There is a 50% chance that B will miss whoever he chooses to shoot. In that case there becomes a 50% chance that C will shoot and kill B instead of you. You then will have a 33% chance of killing C and winning. Should you miss, C will kill you, so this is the best case for this scenario.

.50 x .50 x .33 = .0825 or 8.25%

Now for the other scenario, there is a 50% chance that B will shoot at C then a 50% chance that he will kill C. This would leave you with a 33% chance of then killing B and ending it. This is the earliest you could win so your chances will only drop from here.

.50 x .50 x .33 = .0825 or 8.25%

So in either scenario your chance of winning is 8.25% at best. Compare this to shooting at C and it is pretty clear that you should miss intentionally. It boils down to this: your chances of survival are greater with the possibility of them shooting at each other in the first round. If you choose to shoot and are successful, which is the whole point for trying to shoot, you have eliminated the chance that you won't get shot at.

Now, you might want to consider the fact that if you can miss intentionally, then the other cyborgs could too. This would change your chances of getting shot at from 1 in 2 to 1 in 3, but this is constant so you would just be inflating your overall percentage. Besides, there is no point for the other cyborgs to miss intentionally as it doesnt increase their chances as it does yours.
 IP Logged
Chronos
Full Member

Gender:
Posts: 288
 Re: three-way pistol duel   « Reply #15 on: Oct 30th, 2002, 1:06pm » Quote Modify

A friend of mine pointed out an additional subtlety to this problem:  Can you even intentionally miss?  Suppose that you have to aim at some target, and that you only have a 1/3 chance of hitting your target, no matter what it is.  What if you aim at the ground...  And miss?  What happens to the bullet?
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #16 on: Oct 30th, 2002, 1:21pm » Quote Modify

Chronos,

While it could be a potentially interesting theoretical question if modelled and added to the original, I think it's fairly clear that with any reasonable quantitative model of the situation you "can" miss.  For example, 30% could mean that you will hit within a circle of radius r, where the placement of your bullet is actually a bivariate normal with standard deviation such that the placement within r is 30%.  Then "where the bullet goes if you miss" becomes something that with arbitrarily high probability will not be anywhere near the other robots -- again assuming any reasonable original configuration (or even if not actually, for the three robot case:  here under my model you could miss the other robots with probability precisely 1).

Best,
Eric
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
erg8
Newbie

Posts: 3
 Re: three-way pistol duel   « Reply #17 on: Jul 15th, 2003, 1:56pm » Quote Modify

So... I used this riddle as my senior project at Hendrix College.

I made a few assumptions when I did an analysis of the problem:
1: players can choose to shoot into the air
2: the top two players will always target one another

Under these assumptions you can do a whole lot of neat stuff: more players, variable hit rates, etc.
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #18 on: Jul 15th, 2003, 1:58pm » Quote Modify

why do you need assumption 2?
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
erg8
Newbie

Posts: 3
 Re: three-way pistol duel   « Reply #19 on: Jul 15th, 2003, 2:02pm » Quote Modify

You would like me to defend my making assumption 2? Or you would like to know what it buys me?
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #20 on: Jul 15th, 2003, 2:05pm » Quote Modify

I guess the latter.  It sounds like you agree the problem could still be attacked without the assumption.
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
erg8
Newbie

Posts: 3
 Re: three-way pistol duel   « Reply #21 on: Jul 15th, 2003, 2:26pm » Quote Modify

I am sure that I would be answering this defferently if you had asked me this two years ago.

If we assume that the top two players will target one another, then it makes the probability tables much easier to compute. For the three player game, only one player is making a choice in the first round. For a four player game, only two players are making choices in the first round.

I analyzed an instance of a five player duel. I did the win probabilities for the four player duel as an interactive web page.

I am sorry to be vague, but I truly remember very few specifics. I will reread it... Would you be interested in reading it as well?
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: three-way pistol duel   « Reply #22 on: Jul 15th, 2003, 2:29pm » Quote Modify

no, i suppose i understand from that.  youre just saying the recursions are simplified, which certainly makes sense.  but if you reread your paper and it is very enlightening, you can post another msg to this thread and i will come read it

i guess you are two years out of college then?
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: three-way pistol duel   « Reply #23 on: Jul 16th, 2003, 1:15am » Quote Modify

Do you allways get the optimal solution for all players when the top two players shoot each other?
I suppose there's a good chance of it, but can it be proven?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Mela
Guest

 Re: three-way pistol duel   « Reply #24 on: Jul 24th, 2003, 12:56pm » Quote Modify Remove

If it is a matrix, then surely as they all want to maximise chances of survival, they can all agree to shoot at the ground or whatever so they all live
 IP Logged
 Pages: 1 2 3  ...  5 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »