[Freeciv-Dev] Re: TODO

[Trent Piepho <xyzzy@xxxxxxxxxxxxx>]

On Mon, 25 Sep 2000, Thue wrote:
> > I wonder if "NIH" is refusing to use his code; anyway, here is a revised
> > version using Trent's algoritm. (though I couldn't make his version work)
> > 
> > -Thue
> 
> Umm, use this version instead.
> And before Trent goes raving that his version already was perfect, he should
> try pitting a unit with 1power, 2hp, 2fp against one with 1power, 1hp, 1fp in 
> his
> own version.

I get a the chance of the first unit winning at 75%.  This is what my code
calculates, and it is the correct answer.

I'll walk you through it, line by line, so that you will understand.  Assume
that the first unit you mentioned is the attacker.

int attackpower=get_total_attack_power(attacker,defender);
int defensepower=get_total_defense_power(attacker,defender);

I don't know if these functions still exist in freeciv, but it should be clear
to anyone what they are supposed to do.  attackpower will be 1, and
defensepower will be 1.  You can't just use the attack and defense power from
the unit structure, because some units get bonuses against other units.

if (!attackpower) return 0;
if (!defensepower) return 100;

This checks if the attacker has a zero attack strength, and returns 0%.  If
the defender has zero defense strength, 100% is returned.  I'm not sure what
civ2 rules say when both attacker and defender have zero attack strength. 
Normally units with no attack strength can't attack, so I suppose it's not
defined.

p=(double)(attackpower)/(double)(attackpower+defensepower);

p is the probability of the attacker winning.  In statistics, using p to refer
to a probability is common practice.  To use some screwy name like
"att_P_lose1" just makes it harder to understand.  In this case, p is 0.5.

if(is_sailing_unit(defender) && map_get_city(defender->x, defender->y)) {
    afp=1;   /* defending ships in port only get a FP of at most 1 */
} else {
    afp=get_unit_type(attacker->type)->firepower;
};
dfp=get_unit_type(defender->type)->firepower;

I've actually got a silly bug in my code here; the "Pearl Harbor Effect"
applies to the defender's firepower, not the attacker's as I've done.  But it
doesn't matter in this case.  afp will be 2, and dfp will be 1.

dhp=defender->hp+afp-1;   /* add afp-1 so we round up instead of down */
ahp=attacker->hp+dfp-1;

dhp will be set to the defender's hit points, plus afp-1 so that it will be
rounded up.  The comment clearly states why afp-1 is being added, as it would
be non-obvious otherwise.  dhp will be 2, ahp will also be 2.

p=sum_binomial(p,dhp/afp,ahp/dfp);
return((int)(100*p));

Finally, the computation.  Remember that p is 0.5, dhp/afp is 2/2 = 1, ahp/dfp
is 2/1 = 2.  The fraction returned is multiplied by 100 to turn it into an
integer percentage, so as to avoid excessive floating point usage.  

The "bug" you first thought you found, where dhp/afp should become dhp/afp +
dhp%afp is not bug.  My method is right, yours is wrong.  It appears you later
realized your mistake, and used dhp/afp + (dhp%afp != 0 ?  1 :  0) which is
just a more complicated and less efficient way of integer division, rounding
up, which is where I was all along.

/**************************************************************************
 sums the area under a binomial distribution with parameters p and n = x+y-1
 from x to n.  This is the chance a unit has of winning if the probably of
 it winning a round is p, the attacker needs to win x times, and the defender
 needs to win y times.
**************************************************************************/
double sum_binomial(double p, int x, int y)

This explains what the parameters to sum_binomial mean.  p, the chance of the
attacker winning a round, is 0.5.  The number of rounds the attacker needs to
win, x, is 1.  The defender needs to win y = 2 rounds. 

From looking at your comments, it doesn't appear as if you don't know what the
binomial _distribution_ is, and are thinking of binomial coefficients.  Here
is a nice web page that might explain it to you:

http://faculty.vassar.edu/~lowry/binom_stats.html

You will see that the variables, p, q, k, n are all used in this classic
formula in the same manner as they are in my code.  b is the value of the
binomial distribution at k, in the web page they use 'P'.  It's common
practice to use N for normal distribution, t for Student's t distribution,
etc. so I felt b for binomial wasn't out of line.  s is the sum of the
binomial terms calculated so far.

Look at the formula on the web page, and think about what it reduces to for
k=0, k=1, etc..  I'll give you a hint:

P(k=0) = q^n
P(k=1) = n * p * q^(n-1)
P(k=2) = n * (n-1) / 1 * p^2 * q^(n-2)
P(k=3) = n * (n-1) * (n-2) / 2 * p^3 * q^(n-3)

If you think about it, you'll see that P(k=1) = P(k=0) * (n-k+1)/k*p/q, and
that this property will hold true for each new term.

So, I sum the distribution from k=0 to k=x.  Here's the code in two lines:

r=p/q; s=b=pow(q,n);
for(k=1;k<x;k++) s+=(b*=(double)(n-k+1)/k*r);

But wait, back in the function's comment I said:

"sums the area under a binomial distribution ... from x to n."

But it looks like I'm summing from k=0 to x-1.  Well, one nice property about
distributions is that the total area under them is equal to 1.  Since I've
calculated the "easy" half, from 0 to x-1, I can find the "hard" half, from
x to n, by just subtracting what I've calculated from 1.  Hence the last
line:

return(1-s);

What's the other part of the "else" for, where I set r=q/p instead of p/q, and
return just (s) and not (s-1)?  Well, I'm just finding the odds of the
defender winning instead of the attacker winning, since they are easier to
calculate.  I've just switched p for q and x for y.

That's my statistics lesson for today.  As you can see, I knew what I was
talking about, and my code works.  Perhaps the math was just a bit above your
level.

> And he should wonder why his code is rejected so often that he has learned to
> start a code submission by saying that everybody always NIH's his code. Hint:
> it
> is not because it is perfect and readable.

Whatever.  I have far more code in freeciv than you do, and I stop working on
it around 2 years ago.  I didn't have people reject my code, I was the one who
rejected other's code.  I don't think it a stretch to say if I hadn't stepped
in and made freeciv a usable game when Claus, Peter, et al left, freeciv
probably would have died some 3 star game on linuxberg.