[bushindo]

5 prisoners are on a death row. Let's call them A, B, C, D, and E. The warden gives them a chance of living. He gives them each a doctored gun and let them engage in a death match. Let's say the guns are modified so that their chances of hitting varies. A's chance of hitting and killing any other player is always 1/5. B's chance is always 2/5, C's is 3/5, D's is 4/5, and E's is 5/5. Assume that every single shot will either miss or kill. A player must shoot someone on his turn. Each player knows his gun's accuracy rate and the others' as well.

The players take turn shooting in the following order: A, B, C, D, and E. During his turn, a gun slinger can choose to shoot at anyone he wants. If a player is killed, then the order of shooting will continue in the same sequence but with the dead player skipped. Players take turn shooting until there is only 1 player remaining.

Assume that each player wants to maximize their own chances of living, and that each player knows that the others will do the same. Answer the following

1) What should A do on this first turn?

2) What should B do on the second turn?

3) What should C do on the third turn?

Super hard bonus: Suppose that the warden likes you, so the night before the game he allows you the chance to choose your gun. Essentially he allows you to choose your position as A, B, C, D, or E. Which position should you choose to maximize your chances of living, assuming that everyone plays optimally? Assume that the other prisoners don't know about this so they won't unduly target you out of spite.

[Guest]

1) A will shoot at C

2) if A succeeds then B will shoot at A, else B will shoot at C

3) if A or B succeed then C is dead , other wise C would shoot at B.

I drew the following colcusions..

1) if A succeeds at killing anyone then B would want A dead for optimal survival (note 1). If A kills B then C would target him (note2). A is better off with B trying to kill him than C, so he does not kill B. If he assumes that B will fail at killing him, then :

> If A had killed C, and B failed at killing A, then D would have to kill E or E would kill D on his turn.

> If A had killed D, and B failed at killing A, then C would have to kill E or E would kill C on his turn.

> If A had killed E, and B failed at killing A, then C would have to kill D or D would kill C on his turn.

The best chance A has is to force D to target E, so A should try to kill C first.

If he fails he is not a target. B would try to do the same, and try to shoot C.

> If A fails at killing C, and B kills C, then D would kill E.

> If A fails at killing C, and B kills D, then C would kill E.

> If A fails at killing C, and B kills E, then C would kill D.

The best chance B has is to force D to target E, so B should try to kill C

But this is only if A fails, if A succeeds in killing C then B should kill A (note1).

Now if A fails and B fails as well then:

> If A and B have failed at killing C, and C kills A, then D would kill E (or E would kill him on his turn).

> If A and B have failed at killing C, and C kills B, then D would kill E (or E would kill him on his turn).

If C kills D then E would kill him on his turn, same if he kills E.

So C must kill A or B. C is better of saving A for the final round. So C will kill B. But only if A and B both fail at killing C on their turns

note 1: Say if A kills C and B does not kill A, but kills E,then it would be D's turn, and D has to choose between A and B. He would kill B and face A on the next turn. Now if B kills A, then D would have to kill E, and B gets to shoot at D. He isn't safe but his chances are better as he has reached the final round and gets to shoot first. Same holds good if A kills D or E.

note 2: If A kills B, and C does not kill A, but kills E, then it would be D's turn, and D has to choose between A and C. He would kill C and face A on the next turn. Now if C kills A, then D would have to kill E, and C gets to shoot at D in the final round.

[Guest]

I am am not very clear at times....

This is why B must kill A if A succeeds at killing C, D or E

Say A kills C.

Then B has to kill A, D or E.

> If B kills D, then E will kill B, and be shoot at by A on the next turn (getting shot at by A is better for E)

> If B kills E, then D will kill B, and be shot at by A on the next trun.

> If B kills A, then D will kill E ( or E will kill D on his turn), and then it will be B's turn, and he gets to shoot at D.

Of the three cases, B killing A gives him the best chance of survival.

Edited June 1, 2009 by adiace

[Guest]

The bonus question... the order is still A to E right?

Edited June 1, 2009 by adiace

[Guest]

so i see my mistake if a person has two people above him he doesnt want to take a shot at the highest anymore (a person never wants to chance leaving only one person above him because this means the best shot left in the game will shoot at you) but that is the only reason i see. You want to take out the highest person there is without it making you the next target so i say. A shoots at E. B shoots at E if A missed otherwise he only has two above him so he shoots at A. C shoots at D if E is dead and B (the highest that doesnt make him an immediate target) otherwise. D shoots at E if alive or C if E isnt alive. E shoots at D if e is alive. so D has the best chance for the first round.

ok the reason a shoots a E not C. Think of this as you have your place and people above and below. The only thing that matters to you is that you have at least two people above you or none so the people above you can fight it out or there are none. Now all the people above you are just identical items. The only thing that matters is if you want to kill someone above you or below you. If you kill c the logic for your opponents d and e is the exact same as if you kill e for c and d. They also only care how many are above and below them. So if you(b at the time) kill one aboive you then have one of the people above you has one up two down and one has three down. Thats what determines there new logic. There old spot is mute. So since it doesnt matter who you kill for there logic you might as well take out the best shot of the equals. So if your aiming below yourself aim one below. If your aiming above aim all the way.

now i need to rework the second part

Edited June 2, 2009 by final

[bushindo]

so i see my mistake if a person has two people above him he doesnt want to take a shot at the highest anymore (a person never wants to chance leaving only one person above him because this means the best shot left in the game will shoot at you) but that is the only reason i see. You want to take out the highest person there is without it making you the next target so i say. A shoots at E. B shoots at E if A missed otherwise he only has two above him so he shoots at A. C shoots at D if E is dead and B (the highest that doesnt make him an immediate target) otherwise. D shoots at E if alive or C if E isnt alive. E shoots at D if e is alive. so D has the best chance for the first round.

ok the reason a shoots a E not C. Think of this as you have your place and people above and below. The only thing that matters to you is that you have at least two people above you or none so the people above you can fight it out or there are none. Now all the people above you are just identical items. The only thing that matters is if you want to kill someone above you or below you. If you kill c the logic for your opponents d and e is the exact same as if you kill e for c and d. They also only care how many are above and below them. So if you(b at the time) kill one aboive you then have one of the people above you has one up two down and one has three down. Thats what determines there new logic. There old spot is mute. So since it doesnt matter who you kill for there logic you might as well take out the best shot of the equals. So if your aiming below yourself aim one below. If your aiming above aim all the way.

now i need to rework the second part

Excellent, the answer to part I is entirely satisfactory. Good work to adiace and final. Now there's still the second part.

[bushindo]

The bonus question... the order is still A to E right?

yes, for the bonus question, the game is entirely the same, proceeding in order from A to E. Except that you get to have your choice of position. Good work on part I, by the way.

Edited June 2, 2009 by bushindo

[Guest]

so i see my mistake if a person has two people above him he doesnt want to take a shot at the highest anymore (a person never wants to chance leaving only one person above him because this means the best shot left in the game will shoot at you) but that is the only reason i see. You want to take out the highest person there is without it making you the next target so i say. A shoots at E. B shoots at E if A missed otherwise he only has two above him so he shoots at A. C shoots at D if E is dead and B (the highest that doesnt make him an immediate target) otherwise. D shoots at E if alive or C if E isnt alive. E shoots at D if e is alive. so D has the best chance for the first round.

ok the reason a shoots a E not C. Think of this as you have your place and people above and below. The only thing that matters to you is that you have at least two people above you or none so the people above you can fight it out or there are none. Now all the people above you are just identical items. The only thing that matters is if you want to kill someone above you or below you. If you kill c the logic for your opponents d and e is the exact same as if you kill e for c and d. They also only care how many are above and below them. So if you(b at the time) kill one aboive you then have one of the people above you has one up two down and one has three down. Thats what determines there new logic. There old spot is mute. So since it doesnt matter who you kill for there logic you might as well take out the best shot of the equals. So if your aiming below yourself aim one below. If your aiming above aim all the way.

now i need to rework the second part

I think that clears it up...

Another way if putting all the logic together is:

If there is an odd number of prisoners in front of you - shoot the strongest (shoot E).

If even or zero, shoot the prisoner who would go b4 you (A would shoot E, B would shoot A).

example

ABCDE

A shoots E misses > even so A-1 >> E

B shoots E misses > odd so strongest >> E

C shoots B kills him > even so C-1 >> B

ACDE

E shoots D kills > zero so E-1 >> D

ACE

A shoots E misses> even so A-1 >> E

C shoots E kills> odd so strongest >> E

.

.

.

Using this algorithm we can expand this to any number of prisoners

[Guest]

so my power went out while typing this up so you guys get the abridged version

AxE means a try to shoot at e and it = the chance that A shot at e times the chance he succeeded so

AxE automatically happens=1/5=.2

BxE if E is still alive=4/5*2/5=.32

BxA if e is dead = 1/5*2/5=.08

CxD if e is dead = 3/5(1/5+4/5*2/5)=.312

CxB if e is alive = 3/5(4/5*3/5)=.288

DxE if e is alive and d is alive= .688*.48*4/5=.264192

DxC if d is alive e is dead=.688*.52*4/5=.286208

ExD e is alive d is alive=(.48-.264192)(.688)*1=.14847

ExC e is alive d is dead=(.48-.264192)(.312)*1=.06735

survival rates after 1 round

A=.92

B=.712

C=.93267

D=.53903

E=.215008

if -- is alive then

now A shoots at whoever is highest

B shoots at a if only one above is dead otherwise shoots at highest

C shoots at one above or if both dead b if he is also dead a

d shoots at the highest person lower then him (either d or e has to be dead (maybe both))

e shoots at highest low person

i will continue (maybe) tell me if you see any errors please before i work forever

Edited June 2, 2009 by final

[Guest]

Calculated after 4 iterations

A = 0.92

B = 0.71

C = 0.76

D = 0.69

E = 0.1

What ever the precise values may be, it is very clear that A is nice and cozy

Edited June 2, 2009 by adiace

[Guest]

Excellent, the answer to part I is entirely satisfactory. Good work to adiace and final. Now there's still the second part.

So I got mixed up there for a minute. Are you saying A or B has best chance? If so I have to disagree.

Here is the most likely outcome:

A shoots whoever, and most likely misses.

B does the same, and again has better chance of miss than hit.

C knows if he eliminates D or E the other one will kill him, so he shoots B, most likely killing him with 60% chance.

D shoots E, if he hits then the order starts over.

If E is alive, he's gunning for D and kills him, so the order starts over.

Now your left with A, C, DorE.

A shoots whoever and most likely misses.

C shoots DorE with a good chance at hitting.

Now A and C are left, and I say C will have better chance of survival.

Now go back and say C misses B.

Your left with A, B, C, DorE

A shoots and misses.

B is not going to risk killing one of the 2 ahead of him, so he shoots at A.(say he missed again)

C shoots DorE with a good chance at hitting.

That leaves A, B, C. or if B hit, then B, and C.

C would have best chance at surviving still I believe.

It seems to me in earlier posts, that people were assuming A or B would hit, and I'm assuming the more likely chance that they miss.

Maybe someone could explain why they think A or even B are going to hit anyone.

Sorry I'm still going with C.

[Guest]

A, B, and C will all probably try to kill E. If E isn't dead by the time C tries (about a 3% chance), then D will shoot E and E will almost certainly die. Then, A, B, and C will shoot for D, and A and B will shoot for C. However, considering the chances of A and B hitting C (52%), C would be a better option as he has a 60% chance of killing B and then A. Therefore my choice would be C.

5 prisoners are on a death row. Let's call them A, B, C, D, and E. The warden gives them a chance of living. He gives them each a doctored gun and let them engage in a death match. Let's say the guns are modified so that their chances of hitting varies. A's chance of hitting and killing any other player is always 1/5. B's chance is always 2/5, C's is 3/5, D's is 4/5, and E's is 5/5. Assume that every single shot will either miss or kill. A player must shoot someone on his turn. Each player knows his gun's accuracy rate and the others' as well.

The players take turn shooting in the following order: A, B, C, D, and E. During his turn, a gun slinger can choose to shoot at anyone he wants. If a player is killed, then the order of shooting will continue in the same sequence but with the dead player skipped. Players take turn shooting until there is only 1 player remaining.

Assume that each player wants to maximize their own chances of living, and that each player knows that the others will do the same. Answer the following

1) What should A do on this first turn?

2) What should B do on the second turn?

3) What should C do on the third turn?

Super hard bonus: Suppose that the warden likes you, so the night before the game he allows you the chance to choose your gun. Essentially he allows you to choose your position as A, B, C, D, or E. Which position should you choose to maximize your chances of living, assuming that everyone plays optimally? Assume that the other prisoners don't know about this so they won't unduly target you out of spite.

[Guest]

three things

1. adiace how did you do that i got .92 for A after one rotation and then i agree he is probably the best but just wondering how you did the math.

for others who are confused. It is most likely a will lose to whoever he is matched up at last call but out of all of them he is the vast favorite to end up in the last two so that gives him the edge

2.james one of your mistakes is a and b have a 50% (1/5+4/5*2/5)=(chance a hits +chance a missed times chance b hits) chance of hitting e making any prediction wrong because there is a 50% chance e is gone before c shoots and then there is 3/5 chance the d's gone within that 50% even more really, so this throws a wrench into the gears

3.kids there is a twenty percent chance A B and C will miss E if all shoot at him and as described by adiace in one of his first posts c wont ever shoot for e first turn (look at his post)

also a 60% chance and within that other percentages is far from proving anything

sometimes with a small amount of these quick assumptions you can get a good guess but after that many 60% 80%'s the calculation is worthless unless you figure out the other 20% and 40%.

[Guest]

three things

1. adiace how did you do that i got .92 for A after one rotation and then i agree he is probably the best but just wondering how you did the math.

for others who are confused. It is most likely a will lose to whoever he is matched up at last call but out of all of them he is the vast favorite to end up in the last two so that gives him the edge

2.james one of your mistakes is a and b have a 50% (1/5+4/5*2/5)=(chance a hits +chance a missed times chance b hits) chance of hitting e making any prediction wrong because there is a 50% chance e is gone before c shoots and then there is 3/5 chance the d's gone within that 50% even more really, so this throws a wrench into the gears

3.kids there is a twenty percent chance A B and C will miss E if all shoot at him and as described by adiace in one of his first posts c wont ever shoot for e first turn (look at his post)

also a 60% chance and within that other percentages is far from proving anything

sometimes with a small amount of these quick assumptions you can get a good guess but after that many 60% 80%'s the calculation is worthless unless you figure out the other 20% and 40%.

Using the table, multiply all probability from top to bottom and add all the paths:

Left side success, right side failure. ( on each level)

so for A: chances of dying >> E 0.2 x A 0.4 >> 0.2X0.4 = 0.08 , chances of survival = 1- 0.8 = 92%

for B: 1 - 0.8X0.6X0.6 = 78% (i made a mistake b4)

for C: 1 - (.2x.4x.6x.4 + .2x.4.x4.x.8 + .... ) = 76%

for D: 69%

for E: 10%

.... I would like to go one more iteration but thats 32 more terms...

[Guest]

I know its time i will never get back but.....

[bushindo]

I know its time i will never get back but.....

I think that clears it up...

Another way if putting all the logic together is:

If there is an odd number of prisoners in front of you - shoot the strongest (shoot E).

If even or zero, shoot the prisoner who would go b4 you (A would shoot E, B would shoot A).

For what it's worth, I got to give you and final props for tackling this problem. These results so far looks right for the number of iterations you have, but the decision tree is pretty deep, and you probably don't want to fully extend down the entire tree.

Another route is to divide and conquer. Consider the case where there are 3 players with their known shooting probabilities, and you can probably derive exact analytical expectation for their survival rates. You'll see then that your game tree becomes a lot more managable since for any node of the tree where 2 player dies,you can substitute the 3-players result in.

An easier route is to do simulation, which is surprisingly easy once you apply the decision rules you derived earlier (the ones in bold). Since the decision rules apply for every single player, you can simulate the game in some short code, assuming that you're using a math-oriented language. Running the game like half a million times should tell you should player has the advantage. that's my prefered route, at least.

Edited June 2, 2009 by bushindo

[Guest]

i was better off on my first guess then ever before. d and e are eliminated with great frequency a b c battle it out a and b gang on c to get it out then a just doesnt have the balls to finish the job. I still think A's in something like 90% of the bottom three and 70% of the bottom two but then again im just making that up. Ran a program to 100000 trials and low and behold

the answers above so i dont know y i started spoiler here but here it is

ans 0.241 0.3076 0.30339 0.12824 0.01977

for a through b respectively. I think the problem was we were trying to just use math. The problem was alot easier if you used math till u understand it then use reasonable predictions to help get there. all the math used to justify A B or C was wrong or incomplete tho i guess

there are no gaurentees my programming worked by i traced the first few and they were working. Method for choosing target is aim at the highest guy unless there are only two above you then aim at the guy right below you.

]

i dont know where u get these problems bushindo but my sleep schedule hates u

[Guest]

What happens if you run the program with A shooting at C first, then shooting at highest? just curious. i don't know how long it takes to do this. Or how....

[bushindo]

i was better off on my first guess then ever before. d and e are eliminated with great frequency a b c battle it out a and b gang on c to get it out then a just doesnt have the balls to finish the job. I still think A's in something like 90% of the bottom three and 70% of the bottom two but then again im just making that up. Ran a program to 100000 trials and low and behold

the answers above so i dont know y i started spoiler here but here it is

ans 0.241 0.3076 0.30339 0.12824 0.01977

for a through b respectively. I think the problem was we were trying to just use math. The problem was alot easier if you used math till u understand it then use reasonable predictions to help get there. all the math used to justify A B or C was wrong or incomplete tho i guess

there are no gaurentees my programming worked by i traced the first few and they were working. Method for choosing target is aim at the highest guy unless there are only two above you then aim at the guy right below you.

]

i dont know where u get these problems bushindo but my sleep schedule hates u

Your programming is correct. Well done. I have the following slightly different number, but that's because we're running simulations

Percentages for A to E: 23.9412 30.5358 30.5734 12.9128 2.0368. Turns out the best position is either B or C.

I'll tone down the computational aspect in the next couple of questions. I figure you and adiace deserve a rest. I swear you two alone have solved about 90% of my problems.

Edited June 2, 2009 by bushindo

[Guest]

Your programming is correct. Well done. I have the following slightly different number, but that's because we're running simulations

Percentages for A to E: 23.9412 30.5358 30.5734 12.9128 2.0368. Turns out the best position is either B or C.

I'll tone down the computational aspect in the next couple of questions. I figure you and adiace deserve a rest. I swear you two alone have solved about 90% of my problems.

I suspected going only 5 iterations would not be enough... this can go on infinitely and all those small probabilities of death start to add up. ( cases such as A and B being the only two and shotting it out..). I have a tendency to pen mathematical equations for these type of problems, but with the polling of players it makes it very hard. But I still think this can be formed into a mathematical equation, and solved, since the deeper we go, the more the probabilities converge, so there is a definite answer

All in all, good fun!

Edited June 2, 2009 by adiace

[Guest]

if a shoots at c first then continues as normal

ans 0.23834 0.29741 0.25777 0.16702 0.03946

also i did 10 million trials and c was still .05% or .0005 lower then b maybe my programming is a lil off somewhere tho

Edited June 2, 2009 by final

[bushindo]

if a shoots at c first then continues as normal

ans 0.23834 0.29741 0.25777 0.16702 0.03946

Copied and pasted from final's work.

A shoots E first: probability of survival A-E (0.241, 0.3076, 0.30339, 0.12824, 0.01977)

A shoots C first: probability of survival A-E (0.23834, 0.29741, 0.25777, 0.16702, 0.0394)

Looks like if A shoots C first, he lowers his own survival rates by about 1 percent, but he will drastically improves D's survival rates (33% increase) at expense of C (16% reduction). It is probably to D's advantage to slip A a couple of cigarattes before the game to bribe him.

also i did 10 million trials and c was still .05% or .0005 lower then b maybe my programming is a lil off somewhere tho

I'll take your results over mine. I only ran the simulation only half a million times. So I guess we'll declare B the best spot to be, since it has a slightly better chance, and because it is not too sensitive to bribing, as we just discussed above. That is, unless adiace comes up with a exact analytical solution to this problem.

Edited June 2, 2009 by bushindo

[CaptainEd]

I've seen a lot of plausibility-talk, but very little numerical or analytical proof. Did either of you run a simulation according to the strategy presented very early by genmaximus, that each player should shoot at the strongest player available (including that E should shoot at D, etc.)? Did it really come out inferior to a combined strategy in which certain players shoot at certain other ones?

Edited June 2, 2009 by CaptainEd

[Guest]

so if everyone shoots at highest guy

ans 30.22482 36.43106 19.75267 13.30722 0.28423

but this lower c's chance considerabley so he wouldnt want to do it. and since this change is mostly on his part (in the other theory he is the one that most often shoots at the guy 1 below him. (he does this 50% of the time) and b's the only other person to do this who is extactic about people doing this new strategy but if c won't participate in it then he won't either.

if everyone shoots at highest and c realizes this is happening then he goes back to the old strategy to up his chances if he is the only person that shoots below him if exactly two people are above him then

ans 0.28753 0.25626 0.33449 0.10365 0.01807

but then B realizes this is happening and also shoots below him when he should raising his chances to my first post of these numbers

ans 0.241 0.3076 0.30339 0.12824 0.01977

hope my logic makes sense

[Guest]

Hello,

im having same troubles here.. any inputs would be great!

Thanks!

simulation assurance vie

[Guest]

I also created a simulation program that assumed that any given person would aim at the person with the largest accuracy rating with E being the most targeted person... and A being the least targeted... (Also I made the program force the people to shoot the other people, not themselves) The program would then produce a random number and based on that number determine whether the person could shoot or not.

The results of running the program in a loop for 10000 times concluded that:

A would get about 3887 times winning for about 38.87% chance of winning.

B would get about 4010 times winning for about 40.10% chance of winning.

C would get about 1691 times winning for about 16.91% chance of winning.

D would get about 412 wins for a bout 4.12% chance of winning.

E never won during the simulation.

So the person with the greatest chance of winning would be person B.

Does this mean that my program does or does not give a decent answer to the question.