Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002:
[Freeciv-Dev] [RFC] approximations for win_chance

[Freeciv-Dev] [RFC] approximations for win_chance

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] [RFC] approximations for win_chance
From: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Date: Sat, 23 Mar 2002 20:30:33 +0000 (GMT)

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 

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


[Prev in Thread] Current Thread [Next in Thread]
  • [Freeciv-Dev] [RFC] approximations for win_chance, Gregory Berkolaiko <=