Captain Galaxy and Commander Glarcon are locked in mortal combat. Each mans a battle tank armed with N photonic missiles which move at the speed of light. They move toward each other at constant velocity=v on a 1-dimensional track, unable to stop or reverse direction. Assume v << c. The probability of scoring a kill with a missile is described by a function f(d) which monotonically increases from 0 to 1 as the distance between the tanks decreases from infinity to 0. If the distance closes to 0 and no missiles are fired, both tanks are destroyed in the collision. Assume each combatant attempts to maximize their own probability of survival.
Note that this is not strictly a zero-sum game, since it is possible for neither player to survive. But it is impossible for both to survive.
The state of the game is thus described by three variables:
- d=distance between the players
- N1= number of own missiles remaining
- N2= number of opponent’s missiles remaining
A strategy S(d,N1,N2) would describe a combatant’ actions (shoot or don’t shoot) for all possible states.
- If each player has exactly one missile what is the optimal strategy? Clearly, if the first player shoots and misses, the 2nd will win by waiting for d to approach 0 and then make a last minute shot.
- What if each player has exactly two missiles?
- What if each player has N missiles?
It may simplify the problem to assume f(d) is proportionate to 1/d or 1/d^2 and then solve the general case.
Brandon says
Well, the strategy for having exactly 1 missile seems clear. If your opponent has no ammunition left, advance to touching and fire. If you have >50% chance of success from current position, fire. Otherwise advance.
Two missiles seems much trickier. The combination of the probabilities of both your missiles should get you to over 50%, but just how, and the interactions of CG having one missile left while CG has two missiles left eludes me so far.
Vadim Ponomarenko says
First, let us determine the likelihood of winning. If my strategy kills you with probability p (ignoring your shots entirely), then by symmetry you could achieve the same. I win with probability p(1-p), you win with probability (1-p)p, and we both die with probability p^2+(1-p)^2. My winning probability is maximized with p=1/2, in which case I will kill you with probability 1/2 and win with probability 1/4. I will now show that this is achievable, against any opponent.
By the properties of f, there is some time t* such that if I fire all my missiles at this time, I will kill you with probability 1/2. This is my strategy. If you fire any of your missiles before time t*, you would do better waiting until time t*. If you fire any of your missiles after time t*, then by delaying you have raised my win percentage to over 1/4.
Comments:
(1) Delaying some missiles until after t* sounds like a good idea; it raises my win percentage, but it may also raise your win percentage. In an extreme case (lots of missiles), if you mostly follow the above strategy but save a single missile until the last moment, then I will win slightly more than 1/4 of the time, but you will win almost half the time. The problem with this is that you are at my mercy. If I mimic this strategy but shoot my last missile a split second before you do, then you end up winning less than 1/4 of the time. Only the minimax strategy above guarantees a 1/4 chance of winning.
(2) If the players have different f functions (e.g. one is a better shot) the problem becomes more complicated.
Fiery Spirited says
Vadim, very nice overview…but how can I be at your mercy if you can only detect my missiles in case they missed you? If the crucial problem of the saving-a-missile strategy is that you could improve on the strategy by choosing an earlier shooting point for the extra missile to the same strategy then that is something you can gamble about and it can be questioned from what aspect the firing spot of the extra missile is optimal.
Basically I think that what makes the problem hard is that it is a winner takes it all problem…an early hit will mean that your remaining missiles does not matter. On the reverse knowing that you have more missiles left than the opponent is something that clearly change the strategy. It would not surprise me if you are correct, but your present arguments does not seem conclusive to me.
Matt says
Nitpicky correction — “If the distance closes to 0 and no missiles are fired, both tanks are destroyed in the collision,” should probably read “If the distance closes to 0 and neither tank has previously been destroyed, both tanks are destroyed in the collision.” Otherwise, the possibility of one side firing, missing, and a non-fatal collision is left open.
Fiery Spirited says
Back after a night sleep…if each person has one single missile and wait until they get 50% chance to hit then the survival chance is 25%. The curious thing is that since each shoot is independent I get an higher chance to survive if I delay my shoot since the likelihood that I die at the 50% mark is the same and I get a higher chance to kill the opponent if I fire later. Firing later than your opponent is beneficial provided the opponent miss, if both fire at later point then both tanks loose. Indeed a tricky problem to analyze…
If we look at the other extreme repeated missiles sent at the 50% mark has an diminishing effect. If I send 4 missiles with 50% chance to hit then the likelihood for a hit is 94%, adding many more missiles at this point is rather pointless. Extra missiles would make more sense earlier to avoid the expected death at the 50% mark. If I can spare 50 missiles I am pretty much bound to get a hit if I send them at the 10% mark. My hunch so far is for each number of missiles there exist some point when it is better to send all your missiles than to risk facing more missiles later, yet it is always better to use spare missiles before this. I am currently unable to determine how the math really works out, but the above reasoning feels rational.
yoonkit says
But Captain Galaxy _ALWAYS_ wins!
Mark says
I can’t leave maths problems alone, I saw this today and had to take a closer look :P Here’s how I see it:
Let P(A|M) be the probability that Captain Galaxy survives on the condition he takes the next shot
And P(A|O) be the probability that Captain Galaxy survives on the condition that the Commander Glarcon takes the next shot.
Both P(A|M) and P(A|O) depend on d of course. As d -> 0, P(A|M) will increase and P(A|O) will decrease.
There will be a point where P(A|M) > P(A|O) and this is the point at which Captain Galaxy will take a shot since his chance of survival is better if he takes than if his opponent takes it.
So we’re looking for the point at which P(A|M) = P(A|O).
P(A|M) = f(d).1 + (1-f(d)).(P(Strategy(d, N1-1, N2)))
based on if he hits at distance d, then he wins, if he doesn’t hit, it depends on the probability of the strategy with him now having 1 less missile.
P(A|O) = f(d).0 + (1-f(d)).(P(Strategy(d, N1, N2-1)))
base on if he gets hit at distance d, then he loses, if he doesn’t get hit, it depends on the probability of the strategy with Commander Glarcon now having 1 less missile.
Obviously, P(Strategy(d, 0, N2)) = 0 since he has no missiles left, (for N2 >= 0)
and P(Strategy(d, N1, 0)) = 1 since Commander Glarcon has no missiles left (for N1 > 0)
By following through the recursive algebra or making a table, we can see that the optimum distance for Captain Galaxy to shoot his missile is when:
f(d) = 1/(N1+N2), where he will win with a probability p = N1/(N1+N2)
I hope that makes sense! :)
Mark
Eugene Kruglikov says
Gentlemen, allow me to offer an unorthodox solution, but one that is nontheless derived from the imposed conditions. We find that the combatants start with d=infinity, and because both they and their projectiles travel at finite speeds, neither they nor the missles can ever reach each other. Another fallout of this condition is that the limit of f(d) is zero, therefore there is no chance that any damage could occur even if they were able to reach. Fairly fruitless endeavor this war is if you ask me.