[Freeciv-Dev] Re: [RFC] approximations for win_chance

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Mar 23, 2002 at 08:30:33PM +0000, Gregory Berkolaiko wrote:
> Since freeciv-dev seems to be dead 

> (or everyone is talking behind my back)

Nothing goes over a bit of paranoia ;)

> , I'll continue flooding it with my spammy messages.
> 
> Although Raimar doesn't think that win_chance computation is heavy, I was 
> still thinking how we can approximate it's result without summing the 
> series.
> 
> The approximation used widely in the AI code (through kill_desire 
> equation) is 
> prob_to_win = 
>   (HP_A * P_A * FP_A)^2 / ((HP_D * P_D * FP_D)^2 + (HP_A * P_A * FP_A)^2)
> where
> A stands for attacker, D stands for defender,
> HP is hitpoints
> P is the corresponding power (attack or defense)
> FP is the firepower
> 
> I suspect that sometimes the values are not squared.
> 
> Recently I encountered an example where this approximation gives a wrong 
> answer:
> Attacker = Stealth Bomber(HP=20, A=21, FP=2, cost=160)
> Defender = Partisan fortified on a mountain with a river
>                          (HP=20, D=27, FP=1, cost=50)
> 
> The exact answer (win_chance) is: .8845473776
> The approximation (with squares) is: .7075812274
> Approximation without squares is: .6086956522
> 
> 0.177 absolute error might seem to be insignificant but the effect is that 
> the bomber doesn't want to risk trying to kill the partisans:
> kill_desire (win_chance) is: 25 shields
> kill_desire (approx w/squares) is: -11 shields
> 
> Recently I played a little bit with Maple and discovered that win_chance 
> can be very well approximated by 
>  (HP_A * P_A * FP_A)^5 / ((HP_D * P_D * FP_D)^5 + (HP_A * P_A * FP_A)^5)
> 
> I don't know what is the meaning of the magic number 5, but it seems to 
> work: I plotted numerous graphs (*.mws is available upon request) and I 
> very rarely saw the absolute error be above 0.02.
> 
> In the example above my approximation gives: .9010694067 which is
> 0.0165 greater than the exact value.  This results in kill_desire being
> 29 shields.  I think it's not too bad.

> In future I will probably base my computations on the exact win_chace, 
> to avoid stupid behaviour.  And when the unbelievers will see the time 
> consumed by win_chance soaring, we can convert to my approximation.

This is ok. Have you measured how fast the approximation is?

> By the way, it is really easy to cache the result of my
> approximation: there are only two real parameters.

And the others?

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Transported to a surreal landscape, a young girl kills the first woman
  she meets and then teams up with three complete strangers to kill again."
    -- TV listing for the Wizard of Oz in the Marin Independent Journal