[Freeciv-Dev] Re: (PR#9763) Not fair: get_defender() fallbacs to tile arrival time when selecting between equal units.

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9763 >

On Sun, 22 Aug 2004, Marko Lindqvist wrote:

> <URL: http://rt.freeciv.org/Ticket/Display.html?id=9763 >
> 
> 
>   1. Your ally has strategically very important fortress and he has 
> already fortified 10 musketeers there.
>   2. You are sending 10 musketeers there as well.
>   3. Now you both provide equal number of musketeers to this fortress. 
> So you share risks 50/50, right?
>   4. Finally enemy arrives and attacks with his 10 cannons, killing some 
> of your musketeers and wounding rest of them. None of your allys units 
> take a scratch.

Seems fair to me : newcomers should suffer ;)

I wouldn't bother with this.

But if you really want to, we might as well go for a really elegant 
solution.  Read on.

>   Each unit arriving to fortress was inserted into beginning of the 
> tile->units list and when it was time to select defender, they were 
> selected, all other considerations equal, in list order.
> 
>   This follows from facts that
>   1. get_defender() falls back to selecting first unit in tile->units 
> list when everything else fails
>   2. tile->units is in order
> 
>   We do need some way to always select defender, so 1 is unlikely to 
> change. But I think it would be quite easy to change 2 so that unit 
> arriving to tile is placed to random position in list.

Actually 1 is much easier to implement.  Here is the algorithm (get 
get_defender before your eyes):

New variable n_equal is counting the number of equally strong best units 
so far.
1. when change is TRUE we set n_equal = 1
2. when we encounter an equally strong unit, 
  a) n_equal++
  b) assign the new unit as the defender with probability 1/n_equal
  c) do NOT reset n_equal

this algorithm selects the defender from among the equally strong units 
with equal probability, without actually knowing, a priori, how many of 
them there will be!  proof is by induction.

G.

P.S. This is a really nice maths problem...  Maybe I can put it into some 
realistic form and use to torture students and colleagues.