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

["Marko Lindqvist" <marko.lindqvist@xxxxxxxxxxx>]

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

Gregory Berkolaiko wrote:
> But if you really want to, we might as well go for a really elegant 
> solution.

  Yes, that's number 2 :-)

>>  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
> 
> 
> 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.

  And _implementation_ for 2 (used in my patch):

  1. insert new unit into position rand( list size + 1 )

  _Algorithm_ is a bit more complicated, but rest (handling of list size 
variable) is automatically handled by existing code.

> 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.

  I'm afraid my solution will not torture you :-) But still; prove that 
every unit has equal chance of being in any given position in the list, 
no matter how many units there is.


  - Caz