wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Weapon Allocation
        
(Message started by: ThudanBlunder on Feb 1^st, 2010, 12:46pm)

Title: Weapon Allocation
Post by ThudanBlunder on Feb 1^st, 2010, 12:46pm

Imagine that you have a mortar set up with ten shells and that you are ready to fire them in sequence. Within your range are three enemy mortars (A, B, and C, say) which your intelligence unit has determined have seven, two, and one shells, respectively. None of them is ready to fire, and you have time to get off all your shells before they have a chance to retaliate. You are within range of each of the three enemy mortars, no two of which are close enough to be destroyed by a single shot. But your problem is complicated by the fact that, although you know the coordinates of A, B, and C, your view of them is obstructed by the terrain. In other words, you have no damage-assessment capability which would enable you to stop wasting shells on a dead mortar.

Assuming that every time you fire you have a probability of 1/2 of hitting your target, how many of your ten shells would you allocate to each enemy mortar?

Title: Re: Weapon Allocation
Post by SMQ on Feb 1^st, 2010, 1:00pm

Medium, really? ;)

[hide]The chance of enemy mortar i surviving is 2^-ai where a_i is the number of shells allocated to morter i. There are only 66 possible allocations of the 10 shells at your disposal. Assuming you wish to minimize the average number of shells headed your way, I find a minimum expected value of 0.71875 = 23/32 shells with an allocation of 5,3,2.
[/hide]
--SMQ

Title: Re: Weapon Allocation
Post by towr on Feb 1^st, 2010, 1:10pm

[hide]Going by expected retaliation, allocate shells in such a way that at each step you decrease the potential of the enemy which currently has the maximum expected power for retaliation.
so
7, 2, 1 -- 1,0,0
3.5, 2, 1 -- 2,0,0
1.75, 2, 1 -- 2,1,0
1.75, 1, 1 -- 3,1,0
0.875, 1, 1 -- 3,2,0
0.875, 0.5, 1 -- 3,2,1
0.4375, 0.5, 0.5 -- 4,2,1
0.4375, 0.25, 0.5 -- 4,3,1
0.4375, 0.25, 0.25 -- 4,3,2
0.21875, 0.25, 0.25 -- 5,3,2

You don't even need to try the 66 possible allocations of shells; local minimization suffices.

If you have an unspecified number of shells, you can use this method to determine the order in which to bomb them and get the best expected result.[/hide]

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 1^st, 2010, 2:03pm

on 02/01/10 at 13:10:23, towr wrote:

If you have an unspecified number of shells, you can use this method to determine the order in which to bomb them and get the best expected result.

But is this the right way to go about it? Suppose a 50% marksman selects one of a pair of pistols at random before shooting at a target. One pistol has two bullets, the other none. What is the probability that he will hit the target? Using your method, his expected number of shots is one; hence his probability is 1/2. Using the correct method, he has a 1/2 chance of getting no shots and 1/2 chance of getting two. In the second case, his chance of hitting the target at least once is 1 - (1/2)² = 3/4 and so his overall probability is 3/8.

[hide]But I think you will find that if you let the enemy kill probabilty also be 1/2, the optimum allocation ought to be 4: 3: 3
That is, I value my hide enough for me to minimise the probability that the enemy will successfully retaliate rather than merely minimise the enemy's retaliatory capacity. [/hide]

on 02/01/10 at 13:00:48, SMQ wrote:

Medium, really? ;)

Well, I didn't think that even a well-placed banana skin justified putting it in Hard. :P

Title: Re: Weapon Allocation
Post by towr on Feb 1^st, 2010, 2:18pm

on 02/01/10 at 14:03:48, ThudanBlunder wrote:

Of course not, my method says nothing about probability. It says how many shells you can expect to be fired in your direction.

[edit]
If you want to minimize the probability of being hit, then if the each enemy has an accuracy of ~0.1954 or less, 5,3,2 is best, anything over and 4,3,3 is best.
On the other hand, what if the distribution of shells on the enemies side was chosen to maximize the chance of killing you, taking into account their varying rates of accuracy and your best response?

Of course, better is to just pack up and run once you fired off all your shells.
[/edit]

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 1^st, 2010, 3:19pm

on 02/01/10 at 14:18:59, towr wrote:

Of course not, my method says nothing about probability. It says how many shells you can expect to be fired in your direction.

So are you minimising the enemy's capacity to retaliate?
Well, as the question was deliberately vague and did not ask for any particular optimum, perhaps one answer is as good as another.
But your method seems to give undue importance to the capacity of the enemy to unsuccessfully retaliate.
Whereas any coward will tell you that the probability of being hit is more important than the probability of being fired upon.

Title: Re: Weapon Allocation
Post by SMQ on Feb 2^nd, 2010, 5:50am

on 02/01/10 at 14:03:48, ThudanBlunder wrote:

Well, I didn't think that even a well-placed banana skin justified putting it in Hard. :P

Eh, why should I assume my enemy has the same accuracy as I do? For all I know each of the three mortars I'm facing has a different accuracy. I thought I'd start with the simplest solution and wait for you to object. ;)

--SMQ

Title: Re: Weapon Allocation
Post by Grimbal on Feb 2^nd, 2010, 6:43am

on 02/01/10 at 14:18:59, towr wrote:

On the other hand, what if the distribution of shells on the enemies side was chosen to maximize the chance of killing you, taking into account their varying rates of accuracy and your best response?

I would say the best allocation is to give all shells to the most accurate mortar. Since all of them got shells, the accuracy should be equal.

Title: Re: Weapon Allocation
Post by towr on Feb 2^nd, 2010, 6:48am

on 02/02/10 at 06:43:42, Grimbal wrote:

I would say the best allocation is to give all shells to the most accurate mortar. Since all of them got shells, the accuracy should be equal.

If one mortar has 100% accuracy, they only need one shell to kill you, so you'd be better off giving the rest of the shells to less accurate mortar crews.

Title: Re: Weapon Allocation
Post by Grimbal on Feb 2^nd, 2010, 7:38am

on 02/02/10 at 06:48:30, towr wrote:

If one mortar has 100% accuracy, they only need one shell to kill you, so you'd be better off giving the rest of the shells to less accurate mortar crews.

Ah, yes, right. The mortars can be damaged.

The next step would be to take into account that the enemy knows that you will draw conclusions from the allocation and that you will fire accordingly. The enemy could try to bluff you by giving a single shell to an inaccurate mortar.

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 2^nd, 2010, 11:54am

on 02/02/10 at 05:50:45, SMQ wrote:

Eh, why should I assume my enemy has the same accuracy as I do?

I was merely claiming that this gives a different optimum allocation, assuming we are not interested in enemy shells that miss.

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 4^th, 2010, 4:01am

on 02/01/10 at 14:18:59, towr wrote:

If you want to minimize the probability of being hit, then if the each enemy has an accuracy of ~0.1954 or less, 5,3,2 is best, anything over and 4,3,3 is best.

That's funny, when the enemy are sure shots their capacity for retaliating successfully equals their capacity for retaliating, successfully or not, which is the quantity you minimized in your first post. For the first, from above optimum allocation is 4,3,3, whereas for the second optimum allocation was found to be 5,3,2 But as they are now the same quantity we should get the same answer.

Title: Re: Weapon Allocation
Post by towr on Feb 4^th, 2010, 4:31am

Well, as they become less accurate their shots become less dependent on each other.
Which is to say, the probability 1-(1-p)^k approaches k*p for smaller p. Which means 7 shells become relatively more dangerous than 2 or 1. (Because you're less likely to already be dead when the 7th hit.)

Title: Re: Weapon Allocation
Post by rmsgrey on Feb 4^th, 2010, 6:49am

on 02/04/10 at 04:01:26, ThudanBlunder wrote:

The first is optimising their chance of getting any hits; the second is optimising the expected number of shots. Even at 100% accuracy, where the expected number of hits equals the expected number of shots, you'd expect the two to be different.

Consider the situation with two enemy mortars, one with just one round, and one with a quasi-infinite supply of ammo. If you want to minimise the expected number of hits, you ignore the single-shot mortar and throw everything at the other one (unless you are 100% accurate). If you want to minimise your chance of being hit at all, you start splitting your fire as the enemy becomes more accurate, splitting it evenly when the enemy is 100% accurate.

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 18^th, 2010, 8:18am

on 02/04/10 at 06:49:48, rmsgrey wrote:

Consider the situation with two enemy mortars, one with just one round, and one with a quasi-infinite supply of ammo. If you want to minimise the expected number of hits, you ignore the single-shot mortar and throw everything at the other one (unless you are 100% accurate). If you want to minimise your chance of being hit at all, you start splitting your fire as the enemy becomes more accurate, splitting it evenly when the enemy is 100% accurate.

Agreed, although when the enemy is 100% accurate I cannot see the point in minimising the expected number of hits.

Anyway,
Let p = probability that one of our shots misses
Let q = probability that one of the enemy's shots misses
Let a = number of shells we fire at Gun A
Let b = number of shells we fire at Gun B
So 10 - a - b shells are fired at Gun C

Expected number of enemy shells fired back = 7p^a + 2p^b + p^{10 - a - b}
In theory overkill will be minimised when these three terms are equal.
In fact, plugging in p = 1/2 and a : b : c = 5 : 3 : 2 gives 7/32 + 2/8 + 1/4 = 23/32 (as pointed out by SMQ), and we can see that they are almost equal.

Obviously miinimising the number of enemy shells improves our chance of surviving
where chance of surviving = 1 - q^k = 1 - q^23/32
However, (unless q = 0 or 1) this equation implies that a fraction of a shell is more lethal than a whole shell! ???

Title: Re: Weapon Allocation
Post by Ant_Man on Feb 18^th, 2010, 7:36pm

Our chance of surviving is q^(23/32) not 1 minus that. You defined q as the probability the enemy misses, not his probability of hitting.

Title: Re: Weapon Allocation
Post by ThudanBlunder on Feb 19^th, 2010, 4:10am

on 02/18/10 at 19:36:54, Ant_Man wrote:

Our chance of surviving is q^(23/32) not 1 minus that. You defined q as the probability the enemy misses, not his probability of hitting.

Ah yes, I seem to be making silly mistakes these days. ::)