[Freeciv-Dev] [RFC] approximations for win_chance

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Since freeciv-dev seems to be dead (or everyone is talking behind my 
back), 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.  By 
the way, it is really easy to cache the result of my approximation: there 
are only two real parameters.

Best,
G.