PDA

View Full Version : Gunslingers



DanishDynamite
2007-Nov-27, 01:46 AM
Aron, Bob and Charlie, three gunslingers, decide to have a shootout under the following unusual conditions:

After drawing lots to determine who will be the 1st, 2nd and 3rd shooter, they take their place at the corners of an equilateral triangle, i.e. they are all equidistant from each other. It is decided that each person takes a shot in the order determined and that this continues until 2 of the 3 are dead. It is known that Aron always kills what he aims at. Bob has an 80% chance of killing his target, while Charlie has just a 50% of the same.

Assuming that each gunslinger uses the best possible strategy, which gunslinger has the best chance of survival?

DanishDynamite
2007-Nov-29, 01:57 AM
No takers? No one even care to make a qualified guess? Come now folks, don't be afraid.

Should I post a hint at a fairly manageable way of solving this probability tree?

Infinite Horizons
2007-Nov-29, 02:00 AM
I tried earlier but your thread wouldn't accept it..
My best guess was for Aron to get first draw and shoot Bob, which left Charlie only having a 50% chance of shooting Aron..
Of course it could be a trick ? and their all left alive looking sheepish and shuffling their feet:)

DanishDynamite
2007-Nov-29, 02:49 AM
I tried earlier but your thread wouldn't accept it..
My best guess was for Aron to get first draw and shoot Bob, which left Charlie only having a 50% chance of shooting Aron..
Of course it could be a trick ? and their all left alive looking sheepish and shuffling their feet:)
There is no trick. You just need to first work out what is the best strategy for each shooter and analyze from there.

danscope
2007-Nov-29, 02:58 AM
Hi, Quite simply......Arron and Bob are going to shoot each other. Charley is going to shoot Bob , and then finish off Arron if he has to. Bob is likely to die outright because Arron never misses. Done. Charlie wins.

Best regards,
Dead Eye Dan

DanishDynamite
2007-Nov-29, 03:11 AM
Hi, Quite simply......Arron and Bob are going to shoot each other. Charley is going to shoot Bob , and then finish off Arron if he has to. Bob is likely to die outright because Arron never misses. Done. Charlie wins.

Best regards,
Dead Eye Dan
Charlie definitely has an advantage in being perceived as "least dangerous" and therefore least likely to get shot at.

As I said before, though, you should first work out the best strategy for each individual and then analyze from there.

(Anytime anyone wants a hint, just say so.)

Sarawak
2007-Nov-29, 04:09 AM
I think Arron has 3/10 chance, Bob has 8/45 chance, and Charlie has 47/90 chance.

DanishDynamite
2007-Nov-30, 11:01 PM
I think Arron has 3/10 chance, Bob has 8/45 chance, and Charlie has 47/90 chance.
I think you are right! :)

Care to show your work?

Sarawak
2007-Dec-02, 02:17 PM
I think you are right! :)

Care to show your work?

I think there is a subtle point, we must define success as the death of the other two, not just survival. If their objective is only survival, then we can not rule out optimality of strategies where everyone always aims to miss. This gives everyone 100% chance of survival :)

But the first job is to consider two person games. If there are two people left, then the optimal strategy is always to fire at the other person. We can write survival probabilities as {x,y,z} where x is the probability that Aaron wins, y is the probability that Bob wins, and z is the probability that Charlie wins. Then notation can be P(BC)={x,y,z}, which gives the probability of each person winning, given that only B and C remain, and that B shoots next, and C afterwards. Then

P(AB)={1,0,0}
P(AC)={1,0,0}
P(BA)={0.2,0.8,0}
P(BC)={0,8/9,1/9}
P(CA)={0.5,0,0.5}
P(CB)={0,4/9,5/9}

The only cases which are difficult are P(BC) and P(CB). But it can be seen the probabilities above are the correct solution. If B shoots next, then he has a 0.8 probability of killing C and winning immediately, and a 0.2 probability of missing, so his probability of winning from P(CB) is then 4/9. So his probability of winning is 0.8+0.2*4/9=8/9. If C shoots next, then he has a 0.5 probability of killing B and winning immediately, and a 0.5 probability of missing, so his probability of winning from P(BC) is then 1/9. So his probability of winning is 0.5+0.5*1/9=5/9. So the probabilities above are correct.

When there are three people in the game, it cannot be optimal for B or C to shoot at each other. Shooting at A is always better (but aiming to miss could be better still). If B shoots at C, then he has a 0.8 chance of hitting, and only A and B are left, and A moves next. He has a 0.2 chance of missing, then all three or left, so the order is ACB or ABC. So the winning probabilities if he shoots at C are

0.8*P(AB)+0.2*[P(ACB) or P(CAB), depending on the order]

If he shoots at A instead, by similar reasoning, the winning probabilities are

0.8*P(CB)+0.2*[P(ACB) or P(CAB), depending on the order]

Since P(CB) has higher probability of B winning than P(AB), B will not shoot at C. For C, if he shoots at B, the probabilities are:

0.5*P(AC)+0.5*[P(ABC) or P(BAC), depending on the order]

If he shoots at A instead, the winning probabilities are

0.5*P(BC)+0.5*[P(ABC) or P(BAC), depending on the order]

Since P(BC) has higher probability of C winning than P(AC), C will not shoot at B.

So when there are still three players, B and C will not shoot at each other. They will shoot at A, or aim to miss.

Then it cannot be optimal for A to aim to miss. If he does, then he cannot win. If everyone aims to miss, then A will never win because the game goes on forever. If one other player shoots at A, then eventually, A will be hit, and he will not win. So A must shoot at someone.

If A shoots at C, then he hits him for sure, and only A and B are left, and B shoots next. So P(BA) gives 0.2 probability of A winning. If he shoots at B, then P(CA) gives 0.5 probability of A winning. So A will shoot at B. Then

P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}

So P(BAC), P(BCA), P(CAB), and P(CBA) are still needed. We already know the decision for B if he shoots next is to shoot at A or to aim to miss. If he aims to miss, A always kills him next, so B cannot win. So B always shoots at A. Then there is a 0.8 chance he hits, and the order is now CB, and a 0.2 chance he misses, and the order now is ACB or CAB, depending on the original order.

P(BAC)=0.8*{0,4/9,5/9}+0.2*{0.5,0,0.5}={0.1,16/45,49/90}

We will calculate P(BCA) later.

For C, if he shoots A, then there is 0.5 chance he kills A, and then it is only B and C, with B next, and 0.5 chance he misses, then the order is BAC or ABC. If the order is CAB and C shoots at A, then the winning probabilities are

P(CAB)=0.5*{0,8/9,1/9}+0.5*{0.5,0,0.5}={1/4,4/9,11/36} (but this is wrong!)

But if C aims to miss, then P(CAB)=P(ABC)={0.5,0,0.5}. So C has a higher chance of winning if he aims to miss. So in the order CAB, C aims to miss, and probabilities are {0.5,0,0.5}.

So we know

P(AB)={1,0,0}
P(AC)={1,0,0}
P(BA)={0.2,0.8,0}
P(BC)={0,8/9,1/9}
P(CA)={0.5,0,0.5}
P(CB)={0,4/9,5/9}
P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}
P(BAC)={1/10,16/45,49/90}
P(CAB)={0.5,0,0.5}

We still need P(CBA) and P(BCA). For BCA, we already know B always shoots at A, so there is a 0.8 chance of CB, and a 0.2 chance of CAB. So

P(BCA)=0.8*{0,4/9,5/9}+0.2*{0.5,0,0.5}={1/10,16/45,49/90}

If the order is CAB, we know C aims to miss, but the order CBA must be analyzed. If C shoots at A, there is 0.5 chance the next order is BA, and 0.5 chance it is BAC. So

P(CBA)=0.5*{0,8/9,1/9}+0.5*{1/10,16/45,49/90}={1/20,28/45,59/180} (but this is wrong!)

But if C aims to miss, then the next order is BAC, and C has a 49/90 chance of winning. This is higher than 59/180, so C aims to miss, and P(CBA)={1/10,16/45,49/90}

So when there are three players, A always shoots at B, B always shoots at A, and C always aims to miss. Once someone is killed, the remaining two always shoot at each other. The probabilities for the six possible orderings

P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}
P(BAC)={1/10,16/45,49/90}
P(CAB)={0.5,0,0.5}
P(BCA)={1/10,16/45,49/90}
P(CBA)={1/10,16/45,49/90}

The six orderings have equal probability, so the unconditional probabilities are

P={3/10,8/45,47/90}

But to get this, I think it is important to define success as killing the others, not as surviving. If success is survival, then we cannot rule out the optimality of the strategy where everyone always aims to miss.

danscope
2007-Dec-02, 06:10 PM
So Charlie finishes off A if B only wings him and Charlie's first shot doesn't kill him. Sounds fair. :)
Dan

DanishDynamite
2007-Dec-03, 12:20 AM
Very nicely argued, HB! :)

Your intial worry regarding a "pact" among the players never to actually fire at anyone (with the intention to kill) would mean that the game never finished and would thus not be a valid scenario, as the OP requires that 2 of 3 die.

Anyway, nicely done!

Dragon Star
2007-Dec-03, 12:43 AM
I think there is a subtle point, we must define success as the death of the other two, not just survival. If their objective is only survival, then we can not rule out optimality of strategies where everyone always aims to miss. This gives everyone 100% chance of survival :)

But the first job is to consider two person games. If there are two people left, then the optimal strategy is always to fire at the other person. We can write survival probabilities as {x,y,z} where x is the probability that Aaron wins, y is the probability that Bob wins, and z is the probability that Charlie wins. Then notation can be P(BC)={x,y,z}, which gives the probability of each person winning, given that only B and C remain, and that B shoots next, and C afterwards. Then

P(AB)={1,0,0}
P(AC)={1,0,0}
P(BA)={0.2,0.8,0}
P(BC)={0,8/9,1/9}
P(CA)={0.5,0,0.5}
P(CB)={0,4/9,5/9}

The only cases which are difficult are P(BC) and P(CB). But it can be seen the probabilities above are the correct solution. If B shoots next, then he has a 0.8 probability of killing C and winning immediately, and a 0.2 probability of missing, so his probability of winning from P(CB) is then 4/9. So his probability of winning is 0.8+0.2*4/9=8/9. If C shoots next, then he has a 0.5 probability of killing B and winning immediately, and a 0.5 probability of missing, so his probability of winning from P(BC) is then 1/9. So his probability of winning is 0.5+0.5*1/9=5/9. So the probabilities above are correct.

When there are three people in the game, it cannot be optimal for B or C to shoot at each other. Shooting at A is always better (but aiming to miss could be better still). If B shoots at C, then he has a 0.8 chance of hitting, and only A and B are left, and A moves next. He has a 0.2 chance of missing, then all three or left, so the order is ACB or ABC. So the winning probabilities if he shoots at C are

0.8*P(AB)+0.2*[P(ACB) or P(CAB), depending on the order]

If he shoots at A instead, by similar reasoning, the winning probabilities are

0.8*P(CB)+0.2*[P(ACB) or P(CAB), depending on the order]

Since P(CB) has higher probability of B winning than P(AB), B will not shoot at C. For C, if he shoots at B, the probabilities are:

0.5*P(AC)+0.5*[P(ABC) or P(BAC), depending on the order]

If he shoots at A instead, the winning probabilities are

0.5*P(BC)+0.5*[P(ABC) or P(BAC), depending on the order]

Since P(BC) has higher probability of C winning than P(AC), C will not shoot at B.

So when there are still three players, B and C will not shoot at each other. They will shoot at A, or aim to miss.

Then it cannot be optimal for A to aim to miss. If he does, then he cannot win. If everyone aims to miss, then A will never win because the game goes on forever. If one other player shoots at A, then eventually, A will be hit, and he will not win. So A must shoot at someone.

If A shoots at C, then he hits him for sure, and only A and B are left, and B shoots next. So P(BA) gives 0.2 probability of A winning. If he shoots at B, then P(CA) gives 0.5 probability of A winning. So A will shoot at B. Then

P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}

So P(BAC), P(BCA), P(CAB), and P(CBA) are still needed. We already know the decision for B if he shoots next is to shoot at A or to aim to miss. If he aims to miss, A always kills him next, so B cannot win. So B always shoots at A. Then there is a 0.8 chance he hits, and the order is now CB, and a 0.2 chance he misses, and the order now is ACB or CAB, depending on the original order.

P(BAC)=0.8*{0,4/9,5/9}+0.2*{0.5,0,0.5}={0.1,16/45,49/90}

We will calculate P(BCA) later.

For C, if he shoots A, then there is 0.5 chance he kills A, and then it is only B and C, with B next, and 0.5 chance he misses, then the order is BAC or ABC. If the order is CAB and C shoots at A, then the winning probabilities are

P(CAB)=0.5*{0,8/9,1/9}+0.5*{0.5,0,0.5}={1/4,4/9,11/36} (but this is wrong!)

But if C aims to miss, then P(CAB)=P(ABC)={0.5,0,0.5}. So C has a higher chance of winning if he aims to miss. So in the order CAB, C aims to miss, and probabilities are {0.5,0,0.5}.

So we know

P(AB)={1,0,0}
P(AC)={1,0,0}
P(BA)={0.2,0.8,0}
P(BC)={0,8/9,1/9}
P(CA)={0.5,0,0.5}
P(CB)={0,4/9,5/9}
P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}
P(BAC)={1/10,16/45,49/90}
P(CAB)={0.5,0,0.5}

We still need P(CBA) and P(BCA). For BCA, we already know B always shoots at A, so there is a 0.8 chance of CB, and a 0.2 chance of CAB. So

P(BCA)=0.8*{0,4/9,5/9}+0.2*{0.5,0,0.5}={1/10,16/45,49/90}

If the order is CAB, we know C aims to miss, but the order CBA must be analyzed. If C shoots at A, there is 0.5 chance the next order is BA, and 0.5 chance it is BAC. So

P(CBA)=0.5*{0,8/9,1/9}+0.5*{1/10,16/45,49/90}={1/20,28/45,59/180} (but this is wrong!)

But if C aims to miss, then the next order is BAC, and C has a 49/90 chance of winning. This is higher than 59/180, so C aims to miss, and P(CBA)={1/10,16/45,49/90}

So when there are three players, A always shoots at B, B always shoots at A, and C always aims to miss. Once someone is killed, the remaining two always shoot at each other. The probabilities for the six possible orderings

P(ABC)={0.5,0,0.5}
P(ACB)={0.5,0,0.5}
P(BAC)={1/10,16/45,49/90}
P(CAB)={0.5,0,0.5}
P(BCA)={1/10,16/45,49/90}
P(CBA)={1/10,16/45,49/90}

The six orderings have equal probability, so the unconditional probabilities are

P={3/10,8/45,47/90}

But to get this, I think it is important to define success as killing the others, not as surviving. If success is survival, then we cannot rule out the optimality of the strategy where everyone always aims to miss.

Holy ****.

Mellow
2007-Dec-03, 07:59 AM
Yeah, just what I was thinking.

Sean Clayden
2007-Dec-03, 02:22 PM
Aaron shoots bill, charlie misses aaron aaron shoots charlie.

Aaron the winner................

Sarawak
2007-Dec-04, 01:29 PM
Aaron shoots bill, charlie misses aaron aaron shoots charlie.

Aaron the winner................

This scenario occurs with probability 1/6.


Very nicely argued, HB! :)

Your intial worry regarding a "pact" among the players never to actually fire at anyone (with the intention to kill) would mean that the game never finished and would thus not be a valid scenario, as the OP requires that 2 of 3 die.

I do not worry about a "pact," but depending on how the problem is set up, this outcome may occur if each player pursues the "best" strategy. I agree it must be excluded, but how? Which gunfighter has the obligation to fire first if nobody wants to fire? But if we define this outcome as failure (because they do not kill the other two) rather than success (because they survive), then it takes care of itself; they will not want to aim to miss (except for Charlie).


Anyway, nicely done!

Thanks :) It is a good problem. I know of someone who uses a problem like this as a job interview question.