|
||||
|
Title: three-way pistol duel Post by klbarrus on Jul 25th, 2002, 5:27pm Three-way Pistol Duel (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#threeWayDuel) 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!! |
||||
|
Title: Re: three-way pistol duel Post by Andrew Ooi on Jul 29th, 2002, 8:17pm 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. |
||||
|
Title: Re: three-way pistol duel Post by klbarrus on Jul 29th, 2002, 9:28pm 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. |
||||
|
Title: Re: three-way pistol duel Post by Chronos on Aug 15th, 2002, 5:31pm 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?). |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Aug 16th, 2002, 6:01am 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! :D Best, Eric |
||||
|
Title: Re: three-way pistol duel Post by tim on Aug 16th, 2002, 5:56pm 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. What about AB? 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 ;) |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Aug 16th, 2002, 7:07pm 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 |
||||
|
Title: Re: three-way pistol duel Post by jeremiahsmith on Aug 16th, 2002, 10:45pm on 08/16/02 at 19:07:53, Eric Yeh wrote:
Wait...isn't this a situation where "to win" equals "to survive"? The only way to win is to not get shot. |
||||
|
Title: Re: three-way pistol duel Post by tim on Aug 17th, 2002, 2:32am 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. |
||||
|
Title: Re: three-way pistol duel Post by jeremiahsmith on Aug 17th, 2002, 3:34am on 08/17/02 at 02:32:04, tim wrote:
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. |
||||
|
Title: Re: three-way pistol duel Post by tim on Aug 17th, 2002, 3:55am Quote:
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:
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? |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Aug 17th, 2002, 8:55am 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 |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Aug 17th, 2002, 9:24am 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 |
||||
|
Title: Re: three-way pistol duel Post by tim on Aug 17th, 2002, 10:30pm Eric: Quote:
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:
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? |
||||
|
Title: Re: three-way pistol duel Post by Aaron Kincaid on Oct 18th, 2002, 9:57am 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. |
||||
|
Title: Re: three-way pistol duel Post by Chronos on Oct 30th, 2002, 1:06pm 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? |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Oct 30th, 2002, 1:21pm 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 |
||||
|
Title: Re: three-way pistol duel Post by erg8 on Jul 15th, 2003, 1:56pm 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. |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Jul 15th, 2003, 1:58pm why do you need assumption 2? |
||||
|
Title: Re: three-way pistol duel Post by erg8 on Jul 15th, 2003, 2:02pm You would like me to defend my making assumption 2? Or you would like to know what it buys me? |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Jul 15th, 2003, 2:05pm I guess the latter. It sounds like you agree the problem could still be attacked without the assumption. |
||||
|
Title: Re: three-way pistol duel Post by erg8 on Jul 15th, 2003, 2:26pm 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? |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Jul 15th, 2003, 2:29pm 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? ;) |
||||
|
Title: Re: three-way pistol duel Post by towr on Jul 16th, 2003, 1:15am 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? |
||||
|
Title: Re: three-way pistol duel Post by Mela on Jul 24th, 2003, 12:56pm 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 |
||||
|
Title: Re: three-way pistol duel Post by Eric Yeh on Jul 24th, 2003, 3:30pm ye, but as long as theres any marginal utility to actually winning, this is no longer a nash equilibrium. |
||||
|
Title: Re: three-way pistol duel Post by Peter Seebach on Mar 27th, 2004, 11:37pm Other options: 1. Fire at "the set of all things which are not the 100% accurate robot". You are 33% likely to hit, and 67% likely to miss, killing the accurate robot. 2. Fire at "nothing". :) |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on Mar 28th, 2004, 5:55am on 03/27/04 at 23:37:02, Peter Seebach wrote:
That still leaves you in a duel with the 50% robot, with him having the first shot - if you have to be in a duel with either of the other robots, your chances are better if you shoot first rather than second. Once you get into a duel, firing at "the set of all things which aren't your opponent" then becomes a good idea, though it does rest on an unrealistic model of shot accuracy... Quote:
This solution (or at least "deliberately miss") was suggested in the very first post in the thread, and is generally accepted as the intended solution to the puzzle. |
||||
|
Title: Re: three-way pistol duel Post by Leon on Apr 16th, 2004, 2:41pm Even if A has 50% accuracy rate, A should still miss on purpose. :[hide] If A hits C (50%), B will fire at A (50%) = 25% of death, plus If A misses C (50%), C may fire at and kill A (50% since both A and B are equal threats) = 25% death = 50% total death rate If A fires at nothing, B fires at C. If he hits C (50%), A gets first crack at B. If B misses, then it all starts over again. 0% chance of death (same idea as original). If B misses C, C may fire at and kill A (50% since both A and B are equal threats) = 25% death = 25% total death rate. 25% < 50%, A should miss.[/hide] : If A is at 50% accuracy, what do you think B should do? |
||||
|
Title: Re: three-way pistol duel Post by Leon on Apr 26th, 2004, 10:42am Am I wrong in thinking that in a 3 way situation, regardless of anyone else's accuracy (even if B and C are 100%), unless A has a higher chance of getting shot at that B, A should always miss on purpose? i.e. A and B have 99% accuracy and C has 100% - A miss on purpose A = 99%, B and C = 100%, A miss on purpose Am I missing soemthing? |
||||
|
Title: Re: three-way pistol duel Post by King_T on May 4th, 2004, 1:32pm A = you, 33% shooter B = 50% shooter C = 100% shooter At first I did all the fractions, percentages, etc but I'm misremembering something - so I attacked this problem mechanically and followed each scenario to your death or completion of the first round, whichever came first: Shoot at C and there are 8 outcomes: 1 - hit C, B hits you 2 - hit C, B misses you 3 - miss C, B hits you 4 - miss C, B misses you, C hits you 5 - miss C, B misses you, C hits B 6, 7, 8 - (same as 4, 5, 6) 6,7,8 are repeated to reflect your shooting percentage of 1 in 3. So there are 3 happy endings and 5 unhappy endings for you. If you shoot at C, you will survive the first round (3/8) 37.5% of the time. Shoot at B and there are 13 outcomes: 1 - hit B, C hits you 2 - miss B, B hits you 3 - miss B, B misses you, C hits you 4 - miss B, B misses you, C hits B 5 - miss B, B hits C 6 - miss B, B misses C, C hits you 7 - miss B, B misses C, C hits B 8 to 13 - (same as 2 to 7) You will survive the first round (6/13) 46% of the time. If you miss on purpose there are 6 outcomes: 1 - B hits you 2 - B misses you, C hits you 3 - B misses you, C hits B 4 - B hits C 5 - B misses C, C hits you 6 - B misses C, C hits B You will survive the first round (3/6) 50% of the time. Interestingly, if you shoot at yourself with your same 33% accurracy (if that's possible), then the following 13 outcomes are possible: 1 - you shoot yourself 2 to 6 (above, like missing on purpose) 7 to 13 (same as 2 to 6) You will survive (6/13) 46% of the time. Much as the NRA would like to disagree - your best chance is to miss on purpose (or don't shoot), followed by shooting at B or yourself, followed distantly by shooting at C, the most accurate shooter. In all cases, after the first round - blaze away at the remaining robot. K |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 5th, 2004, 8:48am Assume the classical interpretation of the problem. Let probability that A hits his target = a Let probability that B hits his target = b Let probability that C hits his target = 1 Let 0 < a < b < 1 Assume that there is only A and B left, and that it is A to shoot. Let probability that A survives in this case = aB Then aB = a / [1 - (1 - a)(1 - b)]..................[1] A Shoots First at B: Let probability of A surviving in this case = AxB Then AxB = (1 - a)[a(1 - b) + baB]...............[2] A Shoots First at C: Let probability that A survives in this case = AxC Missing C first go leaves exactly the same probability of survival as missing B first go. This probability was previously found to be AxB. Hitting C first go leaves A and B, with B to shoot. Therefore chance of survival = a(1 - b)aB Hence AxC = AxB + a(1 - b)aB (thus AxC is always greater than AxB) = a(1 - a)(1 - b) + [a(1 - b) + b(1 - a)]aB...............[3] A Shoots First at Nobody: Let probability that A survives in this case = AxN Shooting at nobody leaves B to shoot at C. This is the same case as comes about when A shoots first at B and misses. That is, AxB = (1 - a)AxN Hence AxN = a(1 - b) + baB.........................[4] A Shoots First at Himself: Let probability that A survives in this case = AxA I found it very amusing to read in the previous post that A has a better chance of surviving by trying to blow his own brains out than by having a pop at C, the sure shot! In fact, AxA = AxB ...................................[5] because if you kill yourself you are dead and if you kill B you are equally dead. -------------------------------------------- For example, let a = 1/3 b = 1/2 Then aB = a / [1 - (1 - a)(1 - b)] = (1/3) / [1 - (2/3)(1/2)] = 1/2 AxB = (1 - a)[a(1 - b) + baB] = (2/3)[(1/3)(1/2) + (1/2)(1/2)] = 10/36 AxC = AxB + a(1 - b)aB = 10/36 + (1/3)(1/2)(1/2) = 13/36 AxN = a(1 - b) + baB = (1/3)(1/2) + (1/2)(1/2) = 15/36 If A shoots at nobody, B's chances of survival = b(1 - aB) = (1/2)[1 - (1/2)] = 9/36 C's chances of survival = (1 - a)(1 - b) = (2/3)(1/2) = 12/36 Finally, if we let b = 1 we get aB = a AxB = AxC = a(1 - a) AxN = a |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 5th, 2004, 9:11am I notice King_T has a hidden assumption that the other two "duellists" pick their target randomly. If you instead assume that they play to maximise their own survival chances, then C wants to eliminate both A and B as quickly as possible - except in the case where he expects A and B to shoot at each other until one of them hits - at which point he kills the other. Given the choice of which to shoot, he will choose B over A in order to cut the chances of being killed by the survivor. A and B, knowing that if either of them hits the other while C survives, they both lose, won't shoot each other. If both deliberately miss, C has a choice between shooting B and deliberately missing - the latter meaning no-one wins. So C, if everyone survives the first round will kill B. B then has a strong incentive to kill C. So, if A kills either opponent, the other will get first shot at him, while if he misses, he gets first shot against the survivor (with a 1/2 chance of the survivor being B). |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 14th, 2004, 8:46pm Nice analysis, King_T. However, for 'Shoot at C' you missed out Miss C, B hits C and Miss C, B misses C, C hits you Miss C, B misses C, C hits B Adding these would increase A's probability of surviving the 1st round by shooting first at C to 7/14 = 50% Quote:
Typo - you meant 'same as 3, 4, and 5'. |
||||
|
Title: Re: three-way pistol duel Post by TenaliRaman on May 15th, 2004, 5:29am Modifying the problem a bit, There are 3 robots A,B and C. A has a firing algorithm which has 33% accuracy B has a firing algorithm which has 50% accuracy C has a firing algorithm which has 100% accuracy Each bot starts with a energy level of 100%. When a robot is hit, its the energy level reduces by about 5%. (Assume that each bot knows every other bots firing accuracy,also every bot hits the bot which gives it the maximum survival chance). What is the probability that A can survive such a duel? (possible extension : whenever a robot B is hit by the bullet of robot A, robot A gains 5% energy, also allowing that energy level can go beyond 100%. what is the chance of A surviving now?) (inspired from this post and robocodes) (I haven't solved it and i don't know the answer.If this is tad bit too much for pen and paper then this question could be skipped and this post completely ignored) |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 15th, 2004, 11:00am Quote:
Assume that A shoots in the air at first ~ then his survival probability = 5/12 Assume that B always targets C whenever possible ~ then his survival probability = 1/4 Assume that C always targets B whenever possible ~ then his survival probability = 1/3 The number of rounds required will vary between 20 and 59. So I make it 1 - [smiley=csigma.gif](7/12)20 * (5/12)k-20 * kCk-20 for k = 20 to 59 (This is a slight approximation as on the 59th and last round there will only be two players left. However, the chance that 59 rounds are required is very small.) |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 15th, 2004, 2:21pm Quote:
Too loosely worded. ::) Not sure about this, but... Let the last man to lose 20 points be the survivor. In 36 games A will win 15 of them, gaining 30 points. In 36 games B will win 9 of them, gaining 18 points. In 36 games C will win 12 of them, gaining 24 points. In 36 games A will lose 21 of them, losing 21 points. In 36 games B will lose 27 of them, losing 27 points. In 36 games C will lose 24 of them, losing 24 points Hence in 1 game A can expect to gain 1/4 of a point. B can expect to lose 1/4 of a point. C can expect to break even. Consider C. Each game is a Bernoulli trial with probability 1/2 of winning more points than losing. He starts with 20 points and must win another 40 points to survive. Therefore his chance of not being ruined (surviving) is 20/60 = 1/3 :-/ Now what? |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 15th, 2004, 3:24pm Considering King_T's variant wherein B and C choose a target randomly: Let probability that A hits his target = a Let probability that B hits his target = b Let probability that C hits his target = 1 Let 0 < a < b < 1 Assume that there is only A and B left, and that it is A to shoot. Let probability that A survives in this case = aB Then aB = a / [1 - (1 - a)(1 - b)] Shoots First at B: Let probability that A survives in this case = AxB 1 - Hit B, C hits you 2 - Miss B, B hits you 3 - Miss B, B misses you, C hits you 4 - Miss B, B misses you, C hits B ~ probability = a(1 - a)(1 - b) / 4 5 - Miss B, B hits C ~ probability = b(1 - a)aB / 2 6 - Miss B, B misses C, C hits you 7 - Miss B, B misses C, C hits B ~ probability = a(1 - a)(1 - b) / 4 Total probability of surviving = (a/2)(1 - a)(1 - b) + (1/2)[b(1 - a)]aB Shoots First at C: Let probability that A survives in this case = AxC 1 - Hit C, B hits you 2 - Hit C, B misses you ~ probability = a(1 - b)aB / 2 3 - Miss C, B hits you 4 - Miss C, B misses you, C hits you 5 - Miss C, B misses you, C hits B ~ probability = a(1 - a)(1 - b) / 4 6 - Miss C, B hits C ~ probability = b(1 - a)ab / 2 7 - Miss C, B misses C, C hits you 8 - Miss C, B misses C, C hits B ~ probability = a(1 - a)(1 - b) / 4 Total probability of A surviving = (a/2)(1 - a)(1 - b) + (1/2)[a(1 - b) + b(1 - a)]aB Shoots at Nobody: Let probability that A survives in this case = AxN As before, AxB = (1 - a)AxN Hence AxN = (a/2)(1 - b) + (1/2)baB And AxC = AxB + (a/2)(1 - b)aB For example, let a = 1/3 b = 1/2 Then aB = a / [1 - (1 - a)(1 - b)] = (1/3) / [1 - (2/3)(1/2)] = 1/2 AxB = (a/2)(1 - a)(1 - b) + (1/2)[b(1 - a)]aB = (1/6)(2/3)(1/2) + (1/2)[(1/2)(2/3)(1/2) = 10/72 AxC = (a/2)(1 - a)(1 - b) + (1/2)[a(1 - b) + b(1 - a)]aB = (1/6)(2/3)(1/2) + (1/2)[(1/3)(1/2) + (1/2)(2/3)](1/2) = 13/72 AxN = (a/2)(1 - b) + (1/2)baB = (1/6)(1/2) + (1/2)(1/2)(1/2) = 15/72 In each case, A's chance of survival is exactly half of what it was previously, when B and C tried to maximize their chances by targeting each other. This is explained by the fact that they both now target A more often. AxB = 10/72 < 10/36 previously. AxC = 13/72 < 13/36 previously. AxN = 15/72 < 15/36 previously. When A shoots at nothing B's chances of survival = (b/2)[(1 - b) + (1 - ab)] = (1/4)[(1/2) + (1/2)] = 18/72 and C's chances of survival = (1/2)(1 - b)[(1 - a) + (1 - b)] + b/2 = (1/2)((1/2)[(2/3) + (1/2)] + 1/4 = 39/72 Hence A's chances of survival have decreased from 5/12 to 5/24 Hence B's chances of survival have remained the same at 1/4 Hence C's chances of survival have increased from 1/3 to 13/24 |
||||
|
Title: Re: three-way pistol duel Post by Three Hands on May 15th, 2004, 5:44pm Seems like a rather interesting conclusion - even though A is now more often targetted, he is more likely to survive. Of course, the only possibilities A has of walking out of the duel alive is by shooting C after B has been shot, shooting B after C has been shot, or killing C, and then surviving B's attempt to kill him, before shooting B - so shooting at B is inherently stupid, since killing B also (indirectly) kills A and so, given the two-target option (B or C), you'd prefer to shoot at C - as makes more sense. However, one interesting factor is if you miss what you target, then we're assuming you'd hit nothing. However, if you target nothing, then you'd presumably hit something. Given there are two other targets given in this example, either you hit B or you hit C - and there is no stated probability of hitting one or the other if you miss "nothing". Assuming a 50% chance to hit either of them if you miss nothing, then shooting at nothing would lead to a (2/3 * 1/2) 1/3 chance of hitting either randomly. Given you don't want to hit B (as you then automatically get killed by C), I would prefer to shoot at C in the first place - same chance of killing C, but without the 1/3 chance of killing B, and so being killed by C subsequently. I am, of course, assuming that missing either B or C doesn't lead to similar problems, but automatically hit "nothing" (something about targetting being good enough to be close, and so miss the other), and that missing nothing will not potentially cause you to hit yourself (since you could be considered a valid target, but I felt that such a death (killing yourself by "missing nothing") would be too embarassing for any robot to consider worth the risk...). However, if you bring about some kind of random "scatter" effect for missed shots, then this would probably change the dynamics of the puzzle quite a bit... |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 15th, 2004, 6:07pm Quote:
??? But if we are being realistic we would set the probability of hitting something while trying not to hit it at, for example, 0.00001; this is about as close to zero as would make very little difference to the previous calculations. Quote:
Oh, now I see! While I have been lazily adopting the usual stereotyped way of looking at things, you on the other hand have quickly hacked and probed your way to the essential core of the problem! :D |
||||
|
Title: Re: three-way pistol duel Post by TenaliRaman on May 16th, 2004, 1:42am wow! nice work :) and as rmsgrey says, it is quite an interesting conclusion considering the two cases. i think it also explains why sometimes in robocodes,with around 10 robots in the battle, the weaker ones sometimes survive till the end. |
||||
|
Title: Re: three-way pistol duel Post by Three Hands on May 16th, 2004, 5:31am True, I was going with a rather silly view of what would happen if A aimed at nothing and missed ::) The obvious solution is for A to aim instead at a passing fly which is nowhere near B or C - or any other target which is not "nothing" "B" or "C" (or indeed himself - that could end up being embarassing...) It is an interesting question, though, of what would happen if A targetted nothing, and managed to miss. Surely he would then have to hit something, otherwise he would fail to miss nothing. If the only other things he could hit were himself, B or C, then aiming at nothing could be rather hazardous... |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 16th, 2004, 10:10am Quote:
Alas, I found a problem with my numerical calculations. It is now fixed. Although the original conclusion is not true, perhaps more interestingly, B's chances of survival remain unchanged. |
||||
|
Title: Re: three-way pistol duel Post by THUDandBLUNDER on May 16th, 2004, 4:32pm on 05/16/04 at 05:31:28, Three Hands wrote:
...but evidently much less hazardous than studying too much philosophy! :D |
||||
|
Title: Re: three-way pistol duel Post by Three Hands on May 17th, 2004, 2:24am Depends on which you prefer - insanity or a possibility of death... I chose insanity ;) |
||||
|
Title: Re: three-way pistol duel Post by towr on May 17th, 2004, 5:09am He might hit himself regardless of what he targets. If he targets C and misses, he'll either hit nothing, B or himself (assuming the universe is otherwise empty) |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 17th, 2004, 5:24am A variation I came across many years ago had the three robots all perfect shots, but with doctored ammunition, so that instead of always firing live ammo, A fires harmless blanks 2/3 and B 1/2 the time. This avoids the problem of what happens when A fires at "the set of things which aren't C" - thereby invalidating some of the previous analysis as he is now a bigger threat to C than B is... |
||||
|
Title: Re: three-way pistol duel Post by Three Hands on May 17th, 2004, 6:05am on 05/17/04 at 05:09:09, towr wrote:
Granted, I was assuming that a miss would result in hitting nothing (the generally assumed victim of a miss), but such a result would raise the question "If he aims at nothing and misses, then what does he hit?" If it is a random effect on what anyone hits if they miss anything, then it is only slightly less likely to kill A if he aims at anything other than himself - and leads to his survival chances plummeting, I would imagine... |
||||
|
Title: Re: three-way pistol duel Post by Brad711 on Dec 11th, 2004, 6:27pm Man you don't need all of those algorithms and whatever to prove it. If you shoot at B, you have a 33% chance of hitting. If you hit, C shoots you, and you die for sure. If you miss, B will shoot at C. Then, If B misses, C kills B. Then you have a shot at C. 33% chance you live, 66% chance you die. So, if you shoot at B, 1/2 you die for sure and 1/2 you have a 66% chance of dying. That evens out to a 17% chance of living. If you shoot at C and you hit(33% chance) then B shoots at you (50% chance). If he misses, then I think you will keep shooting back and forth and it will be a 16.5% chance of you living. I'm not sure. If you miss C (66% chance) then B shoots at C. If he hits (50% chance) then you have a 33% chance of hitting him, and I think(not sure) it's the same 16.5% chance of living. If B misses, then C kills B and You get a shot at B. Same 16.5% chance. So I think that if you shoot at C, you have a 16.5% chance of living. Not sure, but I know it's less that a 50% for sure. If you attack no one then B attacks C. If he hits, (50%) then you get a shot at B. 1/3 of hitting. If not, 1/2 of dying. If not 1/3 of hitting. Ect. I think that this is a 66% chance of living. I dono. If he misses, C kills B, and you have a 33% chance of living, if you hit C. The average of 66% and 33% is 50%, so you have the best chance of living by deliberately missing on your first shot, with a 50% chance! Pretty good for the worst shooter! |
||||
|
Title: Re: three-way pistol duel Post by Icarus on Dec 11th, 2004, 7:25pm Those "algorithms" are how you calculate probabilities correctly. The probabilities you have stated are not correct. |
||||
|
Title: Re: three-way pistol duel Post by Keith H on Feb 8th, 2005, 6:59pm If intentional missing is allowed, A should shoot at nothing to win with probability 5/12. If it is not allowed, A should shoot at C to win with probability 13/36. First off, let us define some things: A, B and C are as before. X, Y, Z, and W are metasyntactic variables, and can be any of A, B, or C. P_X(YZ) is the total probability of a win for robot X, given that there are two robots Y and Z remaining, and it is time for robot Y to shoot. So, obviously, P_A(BC) = 0 and so forth. Also, P_X(CX) = 0 and P_C(CX) = 1. Let's work these out. For P_A(AB), we add up the probability of winning on each round (when we shoot) times the probability of making it to that round. So for round 1, the probability that we get there is 1 and the probability of winning is 1/3. For round 2, the probability that we get there alive is 2/3*1/2 (2/3 of the time B gets a shot, and 1/2 of that time it misses). The probability of winning on round 2 is again 1/3. For round 3, we have to get to round 2 (probability 2/3*1/2) and then get to round 3 from there (probability 2/3*1/2 again). Again we win there with probability 1/3. P_A(AB) = 1/3 + (2/3*1/2)*1/3 + ((2/3*1/)2*(2/3*1/2))*1/3... = 1/3 + 1/(3**2) + 1/(3**3).... # by fraction simplification = 1/2 # by infinite summation P_B(AB) = 1/2 # by subtraction P_A(BA) = 1/2*P_A(AB) = 1/2*1/2 = 1/4 # should be obvious why P_B(BA) = 3/4 P_A(AC) = 1/3 P_B(BC) = 1/2 P_C(AC) = 2/3 P_C(BC) = 1/2 Now, let's introduce another notation: P_X(WYZ) is the probability that X will win with three robots left, firing in order W -> Y -> Z. We cannot calculate these directly without knowing what strategy each robot will take on his turn. One final quantity: P_X(XYZ, W) is the probability that X will win given that it is X's turn and he chooses to shoot (W can be X, Y, or Z). I'll ignore the option to consider survival winning, because it is trivial to realize that if all robots choose this strategy, they all have probability 1 of survival by never shooting at any robot. Since they are smart enough to be crafting strategies, they can figure this out. So, in other words, let's only talk about WINNING, which requires being the unique survivor. Now let's start with C's choices: P_C(CAB, A) = 1*P_C(BC) = 1/2 P_C(CAB, B) = 1*P_C(AC) = 2/3 P_C(CAB, NONE) = P_C(ABC) For now, let's assume P_C(ABC) is less than 2/3. We will come back to this later. So, C will choose to shoot B in that case, to maximize his chance to survive. Note that this means that P_B(CAB) = 0 P_A(CAB) = P_A(AC) = 1/3 Now let's look at B's choices: P_B(BCA, C) = 1/2*P_B(AB) + 1/2*P_B(CAB) = 1/2*1/2 + 1/2*0 = 1/4 P_B(BCA, A) = 1/2*P_B(CB) + 1/2*P_B(CAB) = 0 + 0 = 0 P_B(BCA, NONE) = 1*P_B(CAB) = 0 So B will choose to shoot C, to maximize his chances of survival. Remember, we are still assuming that P_C(ABC) < 2/3. Finally, we look at A's choices: P_A(ABC, B) = 1/3*P_A(CA) + 2/3*P_A(BCA) = 2/3*P_A(BCA) P_A(ABC, C) = 1/3*P_A(BA) + 2/3*P_A(BCA) = 1/3*1/4 + 2/3*P_A(BCA) = 1/12 + 2/3*P_A(BCA) P_A(ABC, NONE) = 1*P_A(BCA). What exactly is P_A(BCA)? Well, we know B will shoot C: P_A(BCA) = 1/2*P_A(AB) + 1/2*P_A(CAB) = 1/2*1/2 + 1/2*P_A(AC) = 1/4 + 1/2*1/3 = 5/12 Well, now we can generate P_A(ABC, B) = 2/3*5/12 = 5/18 P_A(ABC, C) = 1/12 + 5/18 = 13/36 P_A(ABC, NONE) = 5/12 That means A should shoot at nothing, if that is allowed. If A shoots at nothing, then P_C(ABC) < 7/12 (since P_C(*) + P_A(*) <=1), which satisfies our assumption. So there is no contradiction generated by that assumption. What if P_C(ABC) > 2/3? Then C will shoot the ground, and B has to reexamine his options. Let's say that B decides to miss intentionally. Then C must miss intentionally (by assumption) and A is the only one who can shoot. Will she? Well, if she doesn't, she has P_A(ABC) = 0 because nobody else will shoot either. So she must shoot. Whom will she shoot? She'll shoot at C (since a hit puts her in a 1-on-1 and her best odds (by far) are with P_A(BA)). As long as she misses, B and C will pass. So P_C(ABC) = 0 with this strategy, since C cannot survive. That's a contradiction, so we must take back our last assumption that B misses intentionally. Thus, B must choose between shooting A and C. It is fairly obvious that shooting at C is the best bet. Uh oh. What does A do? If she does nothing, B will just keep shooting at C until he hits him, making for P_C(ABC) = 0 again. So A has to shoot somebody. Obviously, shooting at C is her best bet. But now C cannot possibly win, since he is just letting A and B fire at him, paralyzed by our assumption that P_C(ABC) > 2/3. Obviously, that assumption has led to this contradiction and must be abandoned. C will choose to shoot at B, B will choose to shoot at C, and A should miss intentionally. A's chance of survival is P_A(ABC, NONE) = 5/12. If intentional missing is not allowed, then A should shoot at C to win with probability P_A(ABC, C) = 13/36, which is only 1/18 worse. |
||||
|
Title: Re: three-way pistol duel Post by Keith H on Feb 8th, 2005, 7:10pm Small correction: ------------------------ One final quantity: P_X(XYZ, W) is the probability that X will win given that it is X's turn and he chooses to shoot W (W can be X, Y, Z, or NONE). I'll ignore the option to consider survival winning, because it is trivial to realize that if all robots choose this strategy, they all have probability 1 of survival by never shooting at any robot. Since they are smart enough to be crafting strategies, they can figure this out. So, in other words, let's only talk about WINNING, which requires being the unique survivor. ----------------------------------- |
||||
|
Title: Re: three-way pistol duel Post by jackdhammer on May 11th, 2005, 11:50am I know I'm kind of rehashing this but I liked this riddle. It appears to me that in order to maximize your chance of survival over time you need to kill robot C. He is the only one that hits 100% of the time. So I think your first shot should be at him. The problem doesn't say that the cyborg wil shoot back at whoever shot at it. So you really have to assume that each cyborg is trying to maximize his chance of survival. After all, why wouldn't they? So if you shoot at Cyb C if you miss and cyb B miss you will still have one more shot since he would logically shoot at cyborg B first since he has a greater chance of hitting than you do. If you happen to hit cyborg C than you are in a shoot out with cyborg B who only has a 50% chance of hitting you. So taking your first shot at C really increases your chance of long term survival instead of taking 2 shots you get to take 3 and you may not have to deal with shooter B at all. The reason I thought about this was something a favorite math teacher said when I was young. He said that even though there is a 50% chance to flip a coin and get heads, you could potentially flip the coin a hundred times and get tails. The odds don't really play themselves out over a short span. I would rather take the shot at C and get that extra chance to kill him and then flip the coin with B and hope I get a lot of Tails ;) |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 12th, 2005, 5:31am on 05/11/05 at 11:50:36, jackdhammer wrote:
If you kill C, then you face a duel with B with him taking the first shot - half the time you're dead; the other half, you get into a duel with him where you take the first shot. If you don't kill C, half the time you end up in a duel with B where you take the first shot; the other half you get a shot at C with a 1/3 chance of killing him and a 2/3 chance of dying. If you compare the two situations, in each case, half the time you have first shot in a duel with B, so it's the other half the time that decides which is better for you - if you kill C, then you die the rest of the time, while not killing C means you only die most of the rest of the time... |
||||
|
Title: Re: three-way pistol duel Post by jackdhammer on May 12th, 2005, 10:13am on 05/12/05 at 05:31:07, rmsgrey wrote:
lol. thats awesome. But if you don't kill C and B does'n't kill C than you only have 2/3 of a chance to live. Where as if you do kill C you have a 50/50 chance to live. I see that by shooting at neither you would get a "free" round where no one would shoot at you and your chance of survival is 100% for that round, but for long term survival wouldn't you be better off trying to take out the 100% shooter and take your chances with the 50/50 guy? |
||||
|
Title: Re: three-way pistol duel Post by asterex on May 12th, 2005, 1:42pm The enemy of my enemy is my friend. In other words, as long as both B and C are alive, they will only shoot at an enemy of yours, so why kill one of your friends? Let them fight it out, then you begin a duel with the survivor where you get first shot. |
||||
|
Title: Re: three-way pistol duel Post by jackdhammer on May 12th, 2005, 2:15pm on 05/12/05 at 13:42:17, asterex wrote:
Yes but the enemy of your enemy in this case is also YOUR enemy. By not shooting at C you are only buying your self one extra round and reducing the chance that he will be dead before he has a chance to kill you. For long term survivabitiy you have to get rid of the 100% shooter as soon as possible. Let me elaborate. Worse case senario: If you don't shoot at C and then B misses C you have a 66% chance of guarnteed death. If you miss C on your turn Game over. However, if you shoot C or B shoots C theoretically speaking the game could go on for a while. It may take 1million shots before Bs 50% chance of hitting you plays itself out in his favor. He could go on a run of 1000 misses. The point is while it isn't likely, you at least have a chance (a 50% chance to be exact ;) ) to live long enough to shoot him first, where you only have a very limited number of chances to kill C. So why limit that number (and your chances of survival) even more by not shooting at him with your first shot? |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 12th, 2005, 6:46pm on 05/12/05 at 10:13:52, jackdhammer wrote:
Scenario A - Do not kill C immediately 1/2 - B kills C. Scenario C starts. 1/6 - C kills B and you kill C. 1/3 - C kills B and C kills you. Scenario B - Do kill C immediately 1/2 - B kills you immediately. 1/2 - B misses you initially. Scenario C starts. Scenario C - C is gone and it's your shot 1/3 - you kill B immediately. 1/3 - you miss B and B kills you. 1/3 - both miss. Scenario C restarts. In scenario B, half the time you die before you can find yourself in scenario C. In scenario A, 1/3 of the time you die and 1/6 of the time you win before you can find yourself in scenario C. In both scenarios A and B, you find yourself in scenario C half the time. Essentially, you'd rather have B use his first shot trying to kill C than spend it trying to kill you - if B fails to kill C (worst case), you still have a chance to kill C yourself, while if B fails to miss you (worst case) you have no chance to win. Since the worst case outcomes of B's first shot are equally likely between the two scenarios, and the best case outcome is the same situation and equally likely between the two scenarios, you prefer the scenario where you can survive the worst case... |
||||
|
Title: Re: three-way pistol duel Post by jackdhammer on May 13th, 2005, 9:17am on 05/12/05 at 18:46:14, rmsgrey wrote:
Really good answer (imo) but this is starting to feel like a high road low road type of deal. I feel that the only way to have any long term survival is to kill C. So in my opinion I would rather have as many shots as I can at him since neither I nor the other cyborg have 100% accuracy. I know those guys said that mathmatically speaking you should shoot at neither but when it comes to odds numbers don't always play themselves out like you think they should. Anyone who has been to Vegas and played black jack knows that. Hell, you can flip a coin a bunch of times to see how 50/50 doesn't guarantee even results. However the more times you flip, the better your chances of getting what you need. Thanks for humoring me on this one guys/gals. I haven't had any intelligent conversation with anyone in sometime so this is quite refreshing. |
||||
|
Title: Re: three-way pistol duel Post by SMQ on May 13th, 2005, 9:42am Hmm, the way I interpret it it's not about "playing the odds" Vegas style so much as about getting the first shot when it's down to two. You're the least-accurate dueler, so as long as all three remain the other two will duke it out and leave you alone--I think everybody agrees on that much at least. Now if you shoot at C and hit him, it's down to just you and B, and B has the first shot, giving him a three-to-one advantage over you. If, however, you intentionally miss and leave B and C to duke it out first, you have the first shot against whoever survives. That gives you even-odds against B and C is only two-to-one over you--either way better than your chances with B (or, worse, C) firing first against you. The advantage of having the first shot in the two-way duel outweighs the advantage of firing at C as soon as possible. --SMQ |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 16th, 2005, 4:55am In the possible duel scenarios: Taking first shot against C, you die on his first shot 2/3 times, and win the rest. Taking second shot against B, you die on his first shot only half the time, but after he's had two shots at you, your chances are down to 1/3 of even being alive - you only have a 1/6 chance of having won before B gets a second shot, and only a 1/12 chance of winning at some point after B's second shot (or a 1/4 chance of winning overall) Taking first shot against B, you win on the first shot as often as against C (1/3) and have a good chance of winning later (1/6 - 1/2 overall) Even if each of you only has 2 bullets, your chances of survival are no better if you kill C than if C kills B - and if you don't kill C, you also have the chance of getting the best-case result of B killing C. If you have more than 2 bullets each, your chances of survival with C dead go down, while your chances of survival with C killing B remain the same - either C gets his second shot and wins, or you win with your second shot - either way, having spare bulets doesn't change anything, so shooting C looks worse the more bullets you have. The trouble with having a long shoot-out with B is that, while it gives you more chance to get lucky and hit, it also gives him more chances to get lucky and hit, and he's more likely to get lucky than you are - the only way you can negate that advantage is by getting more shots off than him - since you can have at most one extra shot (by shooting first), the longer the duel, the less that advantage counts for - your 3 shots to his 2 early on is a lot more of an advantage than 1001 to his 1000 if it drags on a bit. If you and B were to replace your lethal weapons with paintball guns and fire an agreed number of rounds at each other, the winner being the one who scores the most hits, then your best chance would be to make the number of rounds as small as possible - the more rounds you play, the closer the end results become to the "average" ones of him hitting three times for every twice you manage... Another possible variant to give you a feel for how things work out: you and B duel with paintball guns again, but one of you gets an extra shot every time you hit - whoever would have had first shot in the live-fire duel. It should be fairly obvious that if B gets the extra shots, he absolutely slaughters you, while, if you get the extras, things are a lot closer. This effectively breaks up the paintballing into repeated "first to hit" duels with the same person starting each one - effectively playing out the same duel many times - and the end result is the same as the result of trying the normal duel that many times. |
||||
|
Title: Re: three-way pistol duel Post by jackdhammer on May 19th, 2005, 10:42am But thats my point exactly, you said "a long shoot out with B" I understand it gives him more chances to hit you. But at least you have a chance and a "long shoot out with B" is possible. There is no chance for a long shoot out with C. From the way the riddle is worded you feel like you really are SOL but you are looking for the shot that will give you the best chance of survivng longer. If that is the case then getting the extra shot on C is your best bet. If B misses you have a 1/3 chance of living because on the next turn you die. If you happen to kill C then you have a 50/50 chance of living and then a 1/3 chance of winning. |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on May 20th, 2005, 6:32am on 05/19/05 at 10:42:05, jackdhammer wrote:
If you work it through, after everyone has had up to two shots: Killing C with your first shot: B has won 2/3 of the time You have won 1/6 of the time The duel continues 1/6 of the time Missing C with your first shot: C has won 1/3 of the time B has won 1/6 of the time You have won 1/3 of the time The duel continues 1/6 of the time If you compare the possible durations: Killing C with your first shot: dead on the 2nd shot 1/2 dead on the 4th shot 1/6 dead on the 6th or later shot 1/12 survive indefinitely 1/4 Missing C with your first shot: dead on the 4th shot 1/6 dead on the 5th shot 1/3 dead on the 6th or later shot 1/12 survive indefinitely 5/12 Killing C first shot not only means that you're less likely to actually win the duel, but also that you're likely to die sooner than if C lives - half the time you don't even get a second shot. |
||||
|
Title: Re: three-way pistol duel Post by Deedlit on May 21st, 2005, 2:25am Jackdhammer, it seems that you accept the mathematics as correct, but are unwilling to accept it based on a logical argument. Look at it this way: Let's say instead that C has a 100% chance of killing someone when he shoots, and B has a 99% chance. Does your argument still hold in this case? But we can see that, if we shoot at C and kill him, we obviously have a less than 1% chance of surviving the duel (it's actually a little above 0.3 %). Whereas, if we wait until someone dies, we have at least a 1/3 chance of killing the remaining person and winning the duel. So there's no question on what you should do here. Now, you might say that this situation is different, since B has a better chance of killing you. This is true; but where does that 50% versus 99% chance appear in your argument? If you insist that your argument applies to 50% and not to 99%, what is the reason for this? At what percentage does the argument switch from applying to not applying? It should be clear that, since your logical argument is not about the numbers, it has no way of determining exactly the percentage at which C's strategy should change. So really, you can't determine the correct strategy from an argument like that; at best you can have a reasonable heuristic. I ran into a similar situation when some people told me the optimal strategy for blackjack couldn't possibly be right; they tried to convince me with an argument that didn't take into account all the mathematical details, just some round numbers. But that doesn't work; the reason it is better to hit on a 12 when dealer shows 2 is that, when you crunch the numbers on the millions of possible outcomes, you get that hitting returns 37% on the average, and standing returns 35%. No logical argument can deduce that. Quote:
I'm afraid I don't see the point you are trying to make. It's true that you aren't usually guaranteed to get the expected value; that's why we're talking about probability in the first place! The best we could have hoped to do is maximize C's chances of survival, not guarantee his survival. So how can this be an objection to the solution? And what do you mean by "high road low road type of deal"? |
||||
|
Title: Re: three-way pistol duel Post by treid on Apr 25th, 2006, 8:17pm I'm new here, I just stumbled across this thread, I'm sure most of the principles have long gone but I wanted to post an idea: The previous calculations were correct, but it doesn't seem that everyone feels that good about the answer. If multiplying the probabilities doesn't make intuitive sense to you, try this: Start at the end, and work backwards. No real math involved. If I type AB, that means A shoots at B first, BA means it's B's turn to shoot at A. If A is dead: 1. BC = 50% win for B 2. CB = 100% win for C If B is dead: 3. AC 33% win for you 4. CA 100% win for C If C is dead: 5. BA = you win 1/4 of the time 6. AB = you win 1/2 of the time but even though I calced the #s on this one, you actually don't have to worry about the exact probability! the only factor is that you can see BA is not as good as AB. This should be clear because if you go first you win 1/3 plus a chance if B misses. If B goes first, he wins 1/2 the time, plus half of the times you miss. Ok, back a step. A + B still alive, who does C shoot? C's decision is easy because he has 100% accuracy, so he just looks at cases 1 and 3 above. You win 33% and B wins 50%, so C will shoot B for a greater chance. A + C still alive, who does B shoot? B knows that C goes next, and will 100% shoot him, based on C's decision above. So B MUST shoot at C. If B misses, C will shoot B, and you go to case 3. If B succeeds, you go to case 6. So who do you shoot? You can see that if you miss, it just devolves into the above case with everyone still alive. So the only case you have to work out is if you're successful. If you get B, you're 100% dead. If you don't, you have a chance. If you HAVE to shoot someone, it should be C. But if you don't have to shoot someone? The trick here is that if one of those guys shoots the other, it's YOUR TURN TO SHOOT, with only one other guy. If you succeed in shooting one of them, it's THE OTHER GUY'S TURN TO SHOOT. So you can see without even looking at the cases above, that you win more often when you shoot first. It's best not to shoot at all. -t. |
||||
|
Title: Re: three-way pistol duel Post by flamingdragon on Oct 27th, 2006, 10:00am What is with these 3 pages of long explanations? Most likely whoever made the joke meant that you have to shoot. The answer is as simple as this: You have only 33% chance of killing either cyborg you shoot, so the most probable outcome will be both cyborgs being alive after your shot regardless of which cyborg you pick to shoot first. The probabilities of your survival from the 50% cyborg's shot will be the same if both cyborgs are alive, regardless of which you shoot first (If you exclude revenge factors). So you only have to consider the chance of dying if you happen to kill whichever cyborg you shoot at. Simple. If you kill the 50% cyborg, you have a 100% chance of dying. If you kill the 100% cyborg, you have a 50% chance of dying. So shoot the 100% cyborg! |
||||
|
Title: Re: three-way pistol duel Post by SMQ on Oct 27th, 2006, 10:39am on 10/27/06 at 10:00:40, flamingdragon wrote:
I respectfully disagree. The riddle (as linked to from the first post of this thread) ends "...what should you shoot at in round 1...". Not "which other cyborg should you shoot at", but "what should you shoot at" (emphasis added). I think this phrasing clearly establishes the validity -- if not the correctness -- of "the ground" as an answer. --SMQ |
||||
|
Title: Re: three-way pistol duel Post by Icarus on Oct 27th, 2006, 3:58pm Once you realize the "shoot the ground" answer, it becomes obvious that this is the intended solution. This is the nature of a good puzzle: the answer is counter-intuitive, but clearly correct. Because the solution runs against your intuition, it both makes the riddle harder, and challenges you to revise your false conceptions that led to the false intuition in the first place. That shooting the ground (or otherwise passing up your chance to shoot someone else) should actually improve your chances of survival is definitely counter-intuitive, but the mathematics to see that it does is fairly straight-forward, so there is no doubt that it is correct. |
||||
|
Title: Re: three-way pistol duel Post by Three Hands on Oct 28th, 2006, 2:59am on 10/27/06 at 10:00:40, flamingdragon wrote:
Quite often, the explanation is there because people have asked questions about the riddle, or the answer was not believed to be immediately obvious to all who saw it. Also, from what I remember of the thread (I didn't bother re-reading it for this post) it is not all explanation, but involves some side-tracking based on semantics, creating different versions of the problem to be discussed and solved. In general, long discussions on this board are based around exploring alternatives, rather than just immediately jumping to an answer an concluding that it is correct. If everyone had accepted the first answer which gave a solution in the "100 Prisoners and a lightbulb" thread, then it would be a whole lot shorter and much less interesting or innovative. Yes, a lot of the time the discussions lead nowhere, but that's part of being creative. Sorry for the rant, just felt this was something I wanted to explain. |
||||
|
Title: Re: three-way pistol duel Post by Whiskey Tango Foxtrot on Oct 28th, 2006, 8:12am Actually, the three pages of explanation are here to disprove processes like the one dragon gave, as these were soon shown to be the wrong ones. |
||||
|
Title: Re: three-way pistol duel Post by flamingdragon on Nov 16th, 2006, 8:14pm The ground would be the best answer, but it really all depends on wether the riddler meant for u to be able to not shoot a cyborg. The only way to know would be to ask him. |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on Nov 17th, 2006, 2:24pm on 11/16/06 at 20:14:46, flamingdragon wrote:
I'm pretty sure W.Wu intended for the deliberate miss to be an option - otherwise the puzzle isn't that interesting. Incidentally, my personal favourite framing of the riddle is for 3 perfectly accurate gunmen to have different ammo loadouts - one has 100% live ammo; one has 50% live ammo, 50% blanks/tracers; and the last has a third live ammo, two-thirds assorted duds. The duds and the live ammo are thoroughly mixed and indistinguishable except by firing them, and the duds are harmless. Starting with the 1/3 live guy, followed by the 1/2, they take turns in firing one round of ammo from their supply in any direction with the aim of being the sole survivor. |
||||
|
Title: Re: three-way pistol duel Post by Zatanna on Aug 15th, 2007, 3:06pm Chronos nailed it when he said "don't shoot at all". (Ever see the movie "The Duelists"?) But if you do shoot, aim for the 100%er. This is NOT a mathmatic problem, it's a LOGIC puzzle! Cyborg C presents the greatest danger and must be taken out first. Sure, you only hit the target once in three times, but all you need is that ONE CHANCE! If you miss, the 50%er tries his hand. If he misses, the 100%er kills him and you get another shot. If the 50%er kills Cyborg C, you face a less dangerous opponant. |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 15th, 2007, 3:20pm on 08/15/07 at 15:06:48, Zatanna wrote:
Why wouldn't it be a mathematics problem? If you calculate your probability of survival given the options, that should tell you which choice is the logical one to make. Quote:
Let's say we also have a cyborg D which misses everything he shoots. Voila, C still poses the greatest threat, but shooting D is the better option. |
||||
|
Title: Re: three-way pistol duel Post by Zatanna on Aug 15th, 2007, 3:59pm Quote:
OK, you got me there. ::) |
||||
|
Title: Re: three-way pistol duel Post by Hippo on Aug 16th, 2007, 3:48am on 08/15/07 at 15:20:51, towr wrote:
Very nice argument :) BTW: As the original problem is almost trivial ... there were some modifications in the thread ... like not killing with probability, but killing requiring several shoots (power/toughtness) ... these variants were not formulated as standalone thread nor solved in this thread ... isn't it. If I remember well the mentioned power/toughtness variant often ends with stalemate so the problem probably is not interesting at all... |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 16th, 2007, 4:07am on 08/16/07 at 03:48:22, Hippo wrote:
Probability seems more interesting to me because you are dealing with an infinite search tree from the start . Combining the two is probably more interesting than either though. |
||||
|
Title: Re: three-way pistol duel Post by mikedagr8 on Aug 16th, 2007, 4:11am How about, what if all 3 shoot at the same time? What are the tactics now? |
||||
|
Title: Re: three-way pistol duel Post by Grimbal on Aug 16th, 2007, 6:36am I'll assume everybody shoots at the exact same time, meaning there is no race to kill before being killed. I guess C would first shoot at B, meaning B is sure to die whatever he does. I am not sure whether there is a point for B to shoot. Since B is certain to die, there is no point for A to shoot at B. But if C survives, C will kill A on the second round. So A must try to kill C in the first round. |
||||
|
Title: Re: three-way pistol duel Post by Hippo on Aug 16th, 2007, 10:05am Suppose everybody has two numbers ... constant power ... the damage dealt by one shot and "remaining life" ... decreased whenever been shot. Situation 1/1,1/1,1/1 is stalemate as whoever shoots first die ... the best strategy is to shoot second (and not to be target ;) ) Of course 3/1,7/2,2/3 is stalemate either. A lot of positions tends to stalemate. Of course one should define what are the priorities ... is better to stay trapped alive in infinite duel or to kill somebody and die? :) |
||||
|
Title: Re: three-way pistol duel Post by Hippo on Aug 16th, 2007, 11:11am on 08/16/07 at 06:36:47, Grimbal wrote:
You msut thing about combined strategies in general ... strategy S_X=(p^X_A,p^X_B,p^X_C,p^X_D) of a person X are probabilities p^X_Y to shoot at person Y. p^X_X=0, p^X_D is probability of intentional miss. It seems to me that if in the strategy for A has 0<p^A_B<1 then contrastrategy for B is p^B_A=1. ... It seem to me that resulting optimal strategies are S_A=(0,1,0,0), S_B(1,0,0,0), S_C(1,0,0,0) for the situation all are alive. After it of course ... shoot the remaining alive. So B will die, C has probability 2/3 to stay alive alone after first shot. A has probability 2/9 to stay alive alone after two shots. With probability 1/9 everyone is killed. |
||||
|
Title: Re: three-way pistol duel Post by mikedagr8 on Aug 16th, 2007, 8:49pm B still gets to shoot, otherwise it is the same situation as a 1v1 duel with A going first. Also it is better to have no winners, or at least no winners while you are alive (hence, you would prefer it if if there were only 2 robots left, you killed the other robot at all costs. |
||||
|
Title: Re: three-way pistol duel Post by Hippo on Aug 20th, 2007, 8:17am on 08/16/07 at 20:49:04, mikedagr8 wrote:
Simultaneous firing is not exactly same ... as B cannot remain alive if A fires at him. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 27th, 2007, 10:12am Assuming they don't have a sense of revenge(won't increase chances of shooting you because you shot them and missed), you should clearly shoot at c. And if there was d who always misses, you shouldn't ever waist a shot on him until he is the only one left. He can't win. |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 27th, 2007, 12:24pm on 08/27/07 at 10:12:04, srn347 wrote:
That's just how the maths works out. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 28th, 2007, 1:04pm They aren't specifically programmed to get revenge if you try to shoot them. If you didn't have d you'd shoot c, not b. |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 28th, 2007, 1:18pm on 08/28/07 at 13:04:53, srn347 wrote:
|
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 28th, 2007, 8:08pm Obviously shooting b is useless since if I kill him I die and if I miss, well I miss. If I shoot c he has a 2/3 chance of dying and whos turn it is is 50-50. I should increase the chance of c dying even at the cost of decreasing the chance of it being my turn. |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 29th, 2007, 12:56am on 08/28/07 at 20:08:12, srn347 wrote:
Just read the first post of this thread! to summarize: If you shoot B, you have a 10/36 chance of winning If you shoot C, you have a 13/36 chance of winning If you shoot at the ground, you have 15/36 chance of winning! 15/36 > 13/36, so shooting the ground is the best option if it is allowed. Why are you ignoring the math in favour of faulty arguments? All the data is there, heck the entire solution is there. "Use the math Luke" -- not Obi Wan |
||||
|
Title: Re: three-way pistol duel Post by mikedagr8 on Aug 29th, 2007, 1:03am Quote:
"Becuase there is no answer..." "He said you would understand" --Matrixes if it were all mathematical :D ;D |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 29th, 2007, 9:34am Would you like to battle b with it being his turn or battle c with is being your turn. I'd choose the first one. Remember that you only have 1/3 accuracy. |
||||
|
Title: Re: three-way pistol duel Post by towr on Aug 29th, 2007, 10:14am on 08/29/07 at 09:34:24, srn347 wrote:
Would you rather survive with probability 13/ [e]damn typos[/e] Just please, read the first post of this thread. If you think it's wrong for another reason than that it doesn't correspond with your intuition, feel free to point out where you think the error is. Common sense intuition is generally a bad adviser with puzzles; because they're meant to puzzle. |
||||
|
Title: Re: three-way pistol duel Post by rmsgrey on Aug 29th, 2007, 3:20pm on 08/29/07 at 10:14:54, towr wrote:
I'd rather 13/26 than 15/36, but I'd rather 15/36 than 13/36... |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 29th, 2007, 4:32pm What about 15/26? |
||||
|
Title: Re: three-way pistol duel Post by mikedagr8 on Aug 29th, 2007, 5:14pm It's a typo, good pick up. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Aug 29th, 2007, 5:43pm Shoot c. |
||||
|
Title: Re: three-way pistol duel Post by Razor on Sep 21st, 2007, 6:10pm Sorry Newbie Here, Alternate solution suggestion. This may have been suggested already but I can't read them all. Shoot yourself in the foot. Can't miss if holding barrel against foot. Any cyborg that is shot is immediately removed (it doesn't say fatally shot) You are thus removed , albeit damaged, but functional. |
||||
|
Title: Re: three-way pistol duel Post by Krull on Sep 21st, 2007, 8:10pm on 08/29/07 at 09:34:24, srn347 wrote:
Raise your arms in the air...shoot 'em like you just don't care. You're forgetting the scenario that if you (A) choose not to shoot at B or C, then B has a 50% chance of shooting C for you, still giving you first shot and 1/3 chance, and possibly a 2nd shot, against B. If B misses, you still have first shot against C, 1/3 chance. What if you devise a version of this puzzle where it's not fixed probability. It could be kind of like the loaded bullets vs. tracers version, but you have a finite set of "bad" shots in you, so that if you shoot a tracer one time, you have a better chance of shooting a live round next time. Let's say you start with only 3 rounds, and B has a 66% chance instead of 50%. Or raise the number of rounds to 6 and keep B at 50%, to increase the complexity for the mathematically inclined. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Sep 22nd, 2007, 3:35pm If they all shot in unison, a would shoot c. B wouldn't bother to shoot. C would have known and shot c. B would have known and shot... B would eventually realize that he would still shoot. |
||||
|
Title: Re: three-way pistol duel Post by grikdog on Sep 22nd, 2007, 10:49pm The cliche "shoot at the ground" result, while missing, is to shoot yourself in your own foot. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Sep 23rd, 2007, 9:14pm doesn't that count as you getting hit? |
||||
|
Title: Re: three-way pistol duel Post by JiNbOtAk on Sep 23rd, 2007, 10:09pm Not if you miss. |
||||
|
Title: Re: three-way pistol duel Post by srn347 on Sep 23rd, 2007, 10:29pm still, if b and c are infinitely smart, one of them might shoot you. |
||||
|
Title: Re: three-way pistol duel Post by shasta on Jan 19th, 2008, 3:29pm According to a strict interpretation of the wording of the puzzle; you should aim at the entire portion of the universe that doesn't contain the 100% accurate robot. 2/3rds of the time you will miss what you are aiming at, in this case resulting in killing your most deadly opponent on your first shot. Should you survive the other cyborg's shot at you, you then repeat the process, aiming at the entire universe that doesn't contain it until you hopefully win. |
||||
|
Title: Re: three-way pistol duel Post by vinylsiding on Feb 12th, 2008, 2:12pm In order to maintain the spirit of the puzzle, let's eliminate the loophole that each could survive by simply refusing to shoot. We state that after a period of time, if no one has attempted a shot, a survivor will be chosen at random. Note: even with that natural condition, there are still instances where each is best off shooting straight at the ground. Consider the trivial case of p1=p2=p3=1.00. NOW, onto the puzzle and arguably the most natural followup question. For what values of p1, p2 and p3 will an optimal strategy be to shoot straight at the ground? More generally, how do we partition the unit cube into the three regions that correspond to the three strategies available for A: shoot at the ground, shoot at B, shoot at C? |
||||
|
Title: Re: three-way pistol duel Post by towr on Feb 12th, 2008, 3:23pm on 02/12/08 at 15:20:38, vinylsiding wrote:
Is there really any need to repeat yourself four times? Let alone making that fourth one an hour after the first? |
||||
|
Title: Re: three-way pistol duel Post by Talabeh on Apr 5th, 2012, 6:13pm I propose the following working conjuncture (solution): Since the problem asks one to determine "whome/what we should shoot at to maximize one's chances of survival, it would be prudent to approach the problem from the neutral observer perspective (non-dueler). If i am C, i know that since i can take out both A and B with a single shot, my best option would be to take out B - it has 50 percent accuracy- in the first around. If i am A i know that the probability of hitting B and C is the same. Therefore, it makes no difference to whome A shoots at because his chances of survival is depended on the success and failure of both B and C. Let also look at how B would reason. B is in the worst possible situation. No matter what option B takes, the odds are always stacked against it. If B shoots at either A or C, its success of survival are always lower than both A and C. Thus, B's object of target is irrelevant to his survival. From the above analysis, it follows that if both A and B shoot at C (combining their probability of hitting the target: 30% +50%), the probability is higher that they will hit C. Hence, maximizing their chances of survival. Since C is always in a win win situation. it would be pragmatic that A (and B) shoot at C! It seems that most think that A shouldn't shoot at anything. Hence, maximizing his/or her chances of survival. However, given the nature of the puzzle, this solution is irrelevant (Re-Read the puzzle to see what i mean!!!!). Just a thought!!! |
||||
|
Title: Re: three-way pistol duel Post by v_blade on Jun 1st, 2012, 8:04am You should shoot at neither of the two... Case 1: if you shoot at Cyborg100 and hit, there is a 50% chance that you will die in the next turn if you shoot at Cyborg100 and miss, Cyborg50 will obviously shoot at Cyborg100. Even if he misses(then Cyborg100 obviously kills him) or hits, you have 33% chance of killing the one who is left. Case 2: if you shoot at Cyborg50 and hit... you're dead. if you miss, then again you have 33% chance of killing the one who is left as above. Cyborg100 and Cyborg50 will only shoot at each other. So, you have best chance of survival if you miss, or rather not shoot either of them at all |
||||
|
Title: Re: three-way pistol duel Post by roady on Mar 27th, 2014, 6:56pm Running with the assumption that the cyborgs will always shoot when there are only 2 left. But in otherwise still allowing a cyborg to pass their turn: I get either, everyone passes, or you should not shoot at C giving a chance of survival of 5/12 (1/4 and 1/3 for A and B respectively) compared to a chance of 13/36 (5/12 and 2/9 for A and B respectively) if you were to shoot C. How exactly the case where C died should be considered may have some effects on the result. (it changes things somewhat if B is very likely to not shoot in the AB pairing, making it better to shoot C on the first turn in that case) ... I basically drew out some kind of expectimax tree. allowing some parts to loop back on themselves. Setting values the case ABC survive and C passes turn, to X, and comparing it to the value obtained at the root. (which should be equal since they are basically the same state) |
||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |