The n-duel problem is something those of us who solve puzzles may have come across in a simplified manner. There are n archers/gunmen/assassins/whatever(I'll go with archers for the purpose of this post) who agree to participate in a turn-based battle. Each of them have 1/n, 2/n, 3/n...n/n probability of killing their target when they shoot. The rules of their engagement are:
1.If there is one person left alive, that person is the winner.
2.If there are multiple people left alive, at any time, it is the turn of the person alive who has shot the least number of arrows to shoot.
3.If there are multiple people who satisfy this criterion, it is the turn of the person who has the lesser accuracy to shoot.
The problem is to determine the ideal strategy for the a/g/a with accuracy 1/n, given that all archers are perfectly rational.
If you haven't solved the puzzle for n=3, stop now and try it. This post will include the answer to it.
I originally saw the generalised version of the puzzle on puzzling.stackexchange.
Let's build up our solution from the base.
n=1
This is the degenerate case; whoever is alive wins.
n=2
This case is also trivial, the strategy is to simply shoot the other person, and hope for the chance of success.
n=3
This is where it gets interesting. The weakest archer appears to have two different options: shoot the medium or the strong archer. Shooting the medium archer means that there is a 1/3 chance that he will succeed, at which point the strong archer will kill him, or a 2/3 chance that it becomes the turn of the medium archer. Shooting the strong archer means that there is a 1/3 chance that he will kill him, and then engage in a duel with the medium archer, with the medium archer getting the first shot, or a 2/3 chance that he misses, and it becomes the medium archer's turn.
Let us look at the medium archer now. If the strong archer is still alive, the medium archer has to target him, otherwise the strong archer will pick him off as the bigger threat on his turn. He kills the strong archer with probability 2/3, and misses with probability 1/3 at which point the strong archer will kill him, resulting in a duel between the weak and the strong archer with the weak archer getting in the first shot.
The strong archer's strategy is straightforward: shoot whoever is still alive with the highest accuracy other than himself. Thus, if the medium archer is still alive, he will shoot him, else he will shoot the weak archer.
This looks like it will require significant calculations to solve, though the answer appears to be(intuitively) for the weak archer to shoot the strong archer on the first turn. However, let's instead work the problem in reverse :- building up from base cases.
Let us call a given set-up of archers alive along with whose turn it is a state. If we enumerate all the possible states(ignoring the obviously impossible case where no-one is alive), we get:
(1 in the ith digit represents that the ith archer is alive, while 0 in the ith digit represents that the ith archer is dead, and underline in the jth digit represents that it is the turn of the jth archer)
There are 12 states. As the archers are perfectly rational, the ith archer's strategy at any given moment is always to try to bring the 3-duel(truel?) to state i(their victory state).
States 1-3 are victory states, and are the only way that the n-duel can end. Now, let's start working out the strategies of the archer whose turn it is at each state(if you think that this method seems overly laborious for a simple puzzle, bear with me for a while). The corresponding probabilities of victory(henceforth called pv) for each of these states are:
pv[1]=[1 0 0],
pv[2]=[0 1 0],
pv[3]=[0 0 1]
State 4: The weak archer's strategy is trivial: to shoot the medium archer. There is a 1/3 chance of going to state 1, and a 2/3 chance of going to state 5.
State 5: The medium archer's strategy is trivial: to shoot the weak archer. There is a 2/3 chance of going to state 2, and a 1/3 chance of going to state 4.
Because these two states are mutually recursive, we will need to manually calculate one of their transition probabilities. Let's take state 4.
P(state 4 -> state 1 eventually) = 1/3 + 2/3*1/3*1/3+1/3*(2/3*1/3)^2 + ...
= 3/7
This means that pv[4](pv for state 4) is [4/7 3/7 0].
Hence, pv[5]= 2/3*pv[2]+1/3*pv[4]
=[0 2/3 0]+[4/21 1/7 0]
=[4/21 17/21 0]
State 6: The weak archer's strategy is trivial: to shoot the strong archer. There is a 1/3 chance of going to state 1, and a 2/3 chance of going to state 7
State 7: The strong archer simply shoots the weak archer to win(state 3). pv[7]=pv[3]=[0 0 1]
Hence, pv[6]=1/3*pv[1]+2/3*pv[3]=[1/3 0 2/3]
State 8: The medium archer's strategy is to shoot the strong archer. There is a 2/3 chance of going to state 2, and a 1/3 chance of going to state 9.
State 9: The strong archer simply kills the medium archer to win. pv[9]=pv[3]=[0 0 1].
Hence, pv[8]=2/3*pv[2]+1/3*pv[9]=[0 2/3 1/3]
State 10: The crux of the problem is to solve for state 10, so we will look at it later.
State 11: The medium archer has to kill the strong archer or die, hence the strategy must be to shoot the strong archer. There is a 2/3 chance of going to state 4, and a 1/3 chance of going to state 12.
State 12: The strong archer will kill the medium archer with no hesitation, taking the fight to state 6.
Hence, pv[12]=pv[6]=[1/3 0 2/3]
Hence, pv[11]=2/3*pv[4]+1/3*pv[12]=2/3*[4/7 3/7 0]+1/3*[1/3 0 2/3]
=[8/21 2/7 0]+[1/9 0 2/9]
=[31/63 18/63 14/63]
Now, we look at state 10. We can clearly see that as a result of the weak archer's action, the fight will go to one of 3 states: 5, 7 and 11. Of these, the most favourable to him is state 11. This is where the "aha" moment of the whole puzzle lies: the weak archer wants the most to bring the fight to state 11, with the next preference being state 5. It may then seems that the strategy should be to take a shot at the strong archer, which would result in pv[10] = 1/3*pv[5]+2/3*pv[11]
=[4/63 17/63 0]+[62/189 36/189 28/189]
=[74/189 87/189 28/189]
The probability of the weak archer winning works out to 74/189. Is that all?
Well, for one thing, if it were, this wouldn't be a fairly well-known puzzle, would it? It would just be a mathematical calculation.
The key observation here is that state 11 is actually better for the weak archer than state 10. This requires the weak archer to not kill anyone. With a little bit of out of the box thinking, you may hit upon the answer: simply shoot the ground/air/whatever to waste the shot, moving the state to state 11. This means that the correct strategy becomes to waste the first shot, and from the next round onwards, shoot the opponent left standing until the fight ends.
An interesting observation is that the weak archer actually has the best chance of winning the fight at almost 50%!
Now, let's get to the actual meat of this post.
n=4
For n=4, the number of states blows up to 32! Let's start by enumerating them:
1.If there is one person left alive, that person is the winner.
2.If there are multiple people left alive, at any time, it is the turn of the person alive who has shot the least number of arrows to shoot.
3.If there are multiple people who satisfy this criterion, it is the turn of the person who has the lesser accuracy to shoot.
The problem is to determine the ideal strategy for the a/g/a with accuracy 1/n, given that all archers are perfectly rational.
If you haven't solved the puzzle for n=3, stop now and try it. This post will include the answer to it.
I originally saw the generalised version of the puzzle on puzzling.stackexchange.
Let's build up our solution from the base.
n=1
This is the degenerate case; whoever is alive wins.
n=2
This case is also trivial, the strategy is to simply shoot the other person, and hope for the chance of success.
n=3
This is where it gets interesting. The weakest archer appears to have two different options: shoot the medium or the strong archer. Shooting the medium archer means that there is a 1/3 chance that he will succeed, at which point the strong archer will kill him, or a 2/3 chance that it becomes the turn of the medium archer. Shooting the strong archer means that there is a 1/3 chance that he will kill him, and then engage in a duel with the medium archer, with the medium archer getting the first shot, or a 2/3 chance that he misses, and it becomes the medium archer's turn.
Let us look at the medium archer now. If the strong archer is still alive, the medium archer has to target him, otherwise the strong archer will pick him off as the bigger threat on his turn. He kills the strong archer with probability 2/3, and misses with probability 1/3 at which point the strong archer will kill him, resulting in a duel between the weak and the strong archer with the weak archer getting in the first shot.
The strong archer's strategy is straightforward: shoot whoever is still alive with the highest accuracy other than himself. Thus, if the medium archer is still alive, he will shoot him, else he will shoot the weak archer.
This looks like it will require significant calculations to solve, though the answer appears to be(intuitively) for the weak archer to shoot the strong archer on the first turn. However, let's instead work the problem in reverse :- building up from base cases.
Let us call a given set-up of archers alive along with whose turn it is a state. If we enumerate all the possible states(ignoring the obviously impossible case where no-one is alive), we get:
(1 in the ith digit represents that the ith archer is alive, while 0 in the ith digit represents that the ith archer is dead, and underline in the jth digit represents that it is the turn of the jth archer)
- 100
- 010
- 001
- 110
- 110
- 101
- 101
- 011
- 011
- 111
- 111
- 111
There are 12 states. As the archers are perfectly rational, the ith archer's strategy at any given moment is always to try to bring the 3-duel(truel?) to state i(their victory state).
States 1-3 are victory states, and are the only way that the n-duel can end. Now, let's start working out the strategies of the archer whose turn it is at each state(if you think that this method seems overly laborious for a simple puzzle, bear with me for a while). The corresponding probabilities of victory(henceforth called pv) for each of these states are:
pv[1]=[1 0 0],
pv[2]=[0 1 0],
pv[3]=[0 0 1]
State 4: The weak archer's strategy is trivial: to shoot the medium archer. There is a 1/3 chance of going to state 1, and a 2/3 chance of going to state 5.
State 5: The medium archer's strategy is trivial: to shoot the weak archer. There is a 2/3 chance of going to state 2, and a 1/3 chance of going to state 4.
Because these two states are mutually recursive, we will need to manually calculate one of their transition probabilities. Let's take state 4.
P(state 4 -> state 1 eventually) = 1/3 + 2/3*1/3*1/3+1/3*(2/3*1/3)^2 + ...
= 3/7
This means that pv[4](pv for state 4) is [4/7 3/7 0].
Hence, pv[5]= 2/3*pv[2]+1/3*pv[4]
=[0 2/3 0]+[4/21 1/7 0]
=[4/21 17/21 0]
State 6: The weak archer's strategy is trivial: to shoot the strong archer. There is a 1/3 chance of going to state 1, and a 2/3 chance of going to state 7
State 7: The strong archer simply shoots the weak archer to win(state 3). pv[7]=pv[3]=[0 0 1]
Hence, pv[6]=1/3*pv[1]+2/3*pv[3]=[1/3 0 2/3]
State 8: The medium archer's strategy is to shoot the strong archer. There is a 2/3 chance of going to state 2, and a 1/3 chance of going to state 9.
State 9: The strong archer simply kills the medium archer to win. pv[9]=pv[3]=[0 0 1].
Hence, pv[8]=2/3*pv[2]+1/3*pv[9]=[0 2/3 1/3]
State 10: The crux of the problem is to solve for state 10, so we will look at it later.
State 11: The medium archer has to kill the strong archer or die, hence the strategy must be to shoot the strong archer. There is a 2/3 chance of going to state 4, and a 1/3 chance of going to state 12.
State 12: The strong archer will kill the medium archer with no hesitation, taking the fight to state 6.
Hence, pv[12]=pv[6]=[1/3 0 2/3]
Hence, pv[11]=2/3*pv[4]+1/3*pv[12]=2/3*[4/7 3/7 0]+1/3*[1/3 0 2/3]
=[8/21 2/7 0]+[1/9 0 2/9]
=[31/63 18/63 14/63]
Now, we look at state 10. We can clearly see that as a result of the weak archer's action, the fight will go to one of 3 states: 5, 7 and 11. Of these, the most favourable to him is state 11. This is where the "aha" moment of the whole puzzle lies: the weak archer wants the most to bring the fight to state 11, with the next preference being state 5. It may then seems that the strategy should be to take a shot at the strong archer, which would result in pv[10] = 1/3*pv[5]+2/3*pv[11]
=[4/63 17/63 0]+[62/189 36/189 28/189]
=[74/189 87/189 28/189]
The probability of the weak archer winning works out to 74/189. Is that all?
Well, for one thing, if it were, this wouldn't be a fairly well-known puzzle, would it? It would just be a mathematical calculation.
The key observation here is that state 11 is actually better for the weak archer than state 10. This requires the weak archer to not kill anyone. With a little bit of out of the box thinking, you may hit upon the answer: simply shoot the ground/air/whatever to waste the shot, moving the state to state 11. This means that the correct strategy becomes to waste the first shot, and from the next round onwards, shoot the opponent left standing until the fight ends.
An interesting observation is that the weak archer actually has the best chance of winning the fight at almost 50%!
Now, let's get to the actual meat of this post.
n=4
For n=4, the number of states blows up to 32! Let's start by enumerating them:
- 1000
- 0100
- 0010
- 0001
- 1100
- 1100
- 1010
- 1010
- 1001
- 1001
- 0110
- 0110
- 0101
- 0101
- 0011
- 0011
- 1110
- 1110
- 1110
- 1101
- 1101
- 1101
- 1011
- 1011
- 1011
- 0111
- 0111
- 0111
- 1111
- 1111
- 1111
- 1111
States 1-4 are trivial as we saw before with states 1-3 of n=3.
pv[1]=[1 0 0 0]
pv[2]=[0 1 0 0]
pv[3]=[0 0 1 0]
pv[4]=[0 0 0 1]
States 5-16 are also trivial, being simple 2 person duels. With some calculations, we can find that:
pv[5]=[2/5 3/5 0 0]
pv[6]=1/2*pv[2]+1/2*pv[5]
=[1/5 4/5 0 0 ]
pv[7]=[4/13 0 9/13 0]
pv[8]=3/4*pv[3]+1/4*pv[7]
=[1/13 0 12/13 0]
pv[10]=pv[4]=[0 0 0 1]
=> pv[9]=1/4*pv[1]+3/4*pv[10]
=[1/4 0 0 3/4]
pv[11]=[0 4/7 3/7 0]
pv[12]=3/4*pv[3]+1/4*pv[11]
=[0 1/7 6/7 0]
pv[14]=pv[4]=[0 0 0 1]
=>pv[13]=2/4*pv[2]+2/4*pv[14]
=[0 1/2 0 1/2]
pv[16]=pv[4]=[0 0 0 1]
=>pv[15]=3/4*pv[3]+1/4*pv[4]
=[0 0 3/4 1/4]
State 17-28 are very similar to the states 10, 11 and 12 when n=3, and hence the strategies to be adopted remain the same. With some calculations, we can find that:
pv[17]=pv[18]
pv[18]=2/4*pv[5]+2/4*pv[19]
pv[19]=3/4*pv[7]+1/4*pv[17]
These 3 are mutually recursive. Simplifying,
pv[18]=4/7*pv[5]+3/7*pv[7]
=[164/455 156/455 135/455 0]
=>pv[17]=pv[18]=[164/455 156/455 135/455 0]
=>pv[19]=[146/455 39/455 270/455 0]
pv[22]=pv[9]=[1/4 0 0 3/4]
=>pv[21]=2/4*pv[5]+2/4*pv[22]
=[13/40 12/40 0 15/40]
=>pv[20]=pv[21]=[13/40 12/40 0 15/40]
pv[25]=pv[9]=[1/4 0 0 3/4]
=>pv[24]=3/4*pv[7]+1/4*pv[25]
=[61/208 0 108/208 39/208]
=>pv[23]=pv[24]=[61/208 0 108/208 39/208]
pv[28]=pv[13]=[0 1/2 0 1/2]
=>pv[27]=3/4*pv[11]+1/4*pv[28]
=3/4*[0 4/7 3/7 0]+1/4*[0 1/2 0 1/2]
=[0 31/56 18/56 7/56]
=>pv[26]=pv[27]=[0 31/56 18/56 7/56]
Now we come to the new cases: states 29-32.
State 32 is very obvious: The strongest archer eliminates the next strongest, changing the state to state 20.
pv[32]=pv[20]=[13/40 12/40 0 15/40]
State 31 is similarly obvious. The second strongest archer must try to eliminate the strongest, lest he be killed immediately.
pv[31]=3/4*pv[17]+1/4*pv[32]
=3/4*[164/455 156/455 135/455 0]+1/4*[13/40 12/40 0 15/40]
=[5119/14560 4836/14560 3240/14560 1365/14560]
Now we arrive at state 30. The possible resultant states are 19,22,27,31. Of these, state 27 is the best option, followed by state 31. Hence, the optimal strategy is to shoot at the weakest archer.
pv[30]=2/4*pv[27]+2/4*pv[31]
=2/4*[0 31/56 18/56 7/56]+2/4*[5119/14560 4836/14560 3240/14560 1365/14560]
=[5119/29120 12896/29120 7920/29120 3185/29120]
If you think about it, it makes sense. The second archer cannot shoot at either archer 3 or 4, as if he kills either of them, it reduces to a 3 archer fight with him as the medium archer, meaning he has to duel an archer stronger than him who gets the first shot. Wasting his shot is also not optimal because one of archers 3 and 4 will kill the other, and the game will reduce to a 3 archer fight with him as the medium archer, though this way he will get the first shot in the duel with a stronger archer. Instead, if he can try to create a 3 archer situation with himself as the weakest archer, that will work best in his favor. This requires him to eliminate the weakest archer, and hence he fires on him.
Now comes the crux of the question: what of state 29, the initial state?
The possible resultant states from here are 18,21,24, and 30. Coincidentally, those are also the decreasing order of states in terms of probability of his victory. To maximize his chances, he must shoot at the 4th archer.
pv[29]=1/4*pv[18]+3/4*pv[30]
=1/4*[164/455 156/455 135/455 0] + 3/4*[5119/29120 12896/29120 7920/29120 3185/29120]
=[25853/116480 48672/116480 32400/116480 9555/116480]
This also makes logical sense. As we know, in a 3 archer situation, the weakest archer will duel one of the two stronger ones. Hence, it is in the weakest archer's interest to bring the fight to a state where the two stronger archers are the weakest they can possibly be. Hence, the weakest archer should shoot to try to kill the strongest.
There you go. The problem is solved.
As a bonus, the big O time complexity of solving the problem this way for n archers is Theta(n 2^(n-1)), which also happens to be the space complexity(since you're calculating all the states' pvs and storing them), making this a super-exponential problem to solve. For n=5, you will need to handle 80 states, and by n=10, you're handling 5120 states.
Clearly, the brute force method is suboptimal, though to be fair, it also gives us all the information about the problem(down to the accurate probabilities). Let's try another approach, where we ignore the numbers, and just assume we have k archers of varying accuracies alive at some time, and try to work out the optimum strategies.
The topmost archer:
If k=1, he is the only 1 alive, and hence wins. Else, he shoots at the next best archer, as he is the biggest threat to him.
The second best archer:
Shoots the best archer, as he is the biggest threat to him.
3rd:
Is at no danger from the 2 archers above him, and will hence shoot the 4th best archer if he exists, else idle.
4th:
If he idles/misses, the 3rd will attack him for sure. The only ways to avoid this are to kill any 1 archer above him, reducing to a 3 archer problem with him as the weakest. The biggest threat to him is the best archer, so he targets him.
5th:
He is not in danger from any of the archers above him, and will hence shoot the 6th best archer if he exists, else idle.
And so on.
You get the idea at this point. Counting from best to worst, odd numbered archers always aim at the next best archer still alive, defaulting to idling if they are the weakest archer still alive, while even numbered archers always aim at the best archer still alive. It's a beautiful symmetry, isn't it?
From my understanding, this seems to be the optimal solution. If the reader finds something incorrect, please drop a comment pointing it outso I can sulk,
Now we arrive at state 30. The possible resultant states are 19,22,27,31. Of these, state 27 is the best option, followed by state 31. Hence, the optimal strategy is to shoot at the weakest archer.
pv[30]=2/4*pv[27]+2/4*pv[31]
=2/4*[0 31/56 18/56 7/56]+2/4*[5119/14560 4836/14560 3240/14560 1365/14560]
=[5119/29120 12896/29120 7920/29120 3185/29120]
If you think about it, it makes sense. The second archer cannot shoot at either archer 3 or 4, as if he kills either of them, it reduces to a 3 archer fight with him as the medium archer, meaning he has to duel an archer stronger than him who gets the first shot. Wasting his shot is also not optimal because one of archers 3 and 4 will kill the other, and the game will reduce to a 3 archer fight with him as the medium archer, though this way he will get the first shot in the duel with a stronger archer. Instead, if he can try to create a 3 archer situation with himself as the weakest archer, that will work best in his favor. This requires him to eliminate the weakest archer, and hence he fires on him.
Now comes the crux of the question: what of state 29, the initial state?
The possible resultant states from here are 18,21,24, and 30. Coincidentally, those are also the decreasing order of states in terms of probability of his victory. To maximize his chances, he must shoot at the 4th archer.
pv[29]=1/4*pv[18]+3/4*pv[30]
=1/4*[164/455 156/455 135/455 0] + 3/4*[5119/29120 12896/29120 7920/29120 3185/29120]
=[25853/116480 48672/116480 32400/116480 9555/116480]
This also makes logical sense. As we know, in a 3 archer situation, the weakest archer will duel one of the two stronger ones. Hence, it is in the weakest archer's interest to bring the fight to a state where the two stronger archers are the weakest they can possibly be. Hence, the weakest archer should shoot to try to kill the strongest.
There you go. The problem is solved.
As a bonus, the big O time complexity of solving the problem this way for n archers is Theta(n 2^(n-1)), which also happens to be the space complexity(since you're calculating all the states' pvs and storing them), making this a super-exponential problem to solve. For n=5, you will need to handle 80 states, and by n=10, you're handling 5120 states.
Clearly, the brute force method is suboptimal, though to be fair, it also gives us all the information about the problem(down to the accurate probabilities). Let's try another approach, where we ignore the numbers, and just assume we have k archers of varying accuracies alive at some time, and try to work out the optimum strategies.
The topmost archer:
If k=1, he is the only 1 alive, and hence wins. Else, he shoots at the next best archer, as he is the biggest threat to him.
The second best archer:
Shoots the best archer, as he is the biggest threat to him.
3rd:
Is at no danger from the 2 archers above him, and will hence shoot the 4th best archer if he exists, else idle.
4th:
If he idles/misses, the 3rd will attack him for sure. The only ways to avoid this are to kill any 1 archer above him, reducing to a 3 archer problem with him as the weakest. The biggest threat to him is the best archer, so he targets him.
5th:
He is not in danger from any of the archers above him, and will hence shoot the 6th best archer if he exists, else idle.
And so on.
You get the idea at this point. Counting from best to worst, odd numbered archers always aim at the next best archer still alive, defaulting to idling if they are the weakest archer still alive, while even numbered archers always aim at the best archer still alive. It's a beautiful symmetry, isn't it?
From my understanding, this seems to be the optimal solution. If the reader finds something incorrect, please drop a comment pointing it out
No comments:
Post a Comment