[Freeciv-Dev] AI danger (Re: Re: A bunch of patches)

["andi payn" <paynfc@xxxxxxxxxxx>]

While hacking out the infinite move patch, I ran into problems with
danger overflow in advmilitary.c. Looking at the code while rebuilding my 
patches, I think I've figured this out.
The AI adds v * m / dist to danger for each unit or potential unit
threatening a city, where v is the threat value for the unit, m is its
move rate, and dist is its distance from the city. Since infinite move
rate is turned into the map's width + height, this means you're often
multiplying by some huge value here, which can cause overflow pretty
easily.

Even without infinite move, I've seen the total danger overflow a couple of 
times. Get enough stealth bombers and cities capable of producing stealth 
bombers close enough to an enemy city, and you'll at least get a warning, 
and you may get an actual crash (when it overflows to negative) or wrong 
decision (when it wraps all the way around to small positive numbers).
I came up with a hack that gets me through. If an individual unit's
contribution is over 1<<24, just use 1<<24+1. If the total gets over
1<<25, just use 1<<25+1. Of course the AI may not be able to properly
decide whether the horde of tanks or the horde of stealth bombers is a
greater danger if they're both 1<<25+1, but then the city's pretty
much screwed in that case anyway, so it doesn't matter much. (I can't
remember if this code is in the patch I uploaded or not, but I'll put it in 
a new patch.)
But looking at the code a bit more carefully, I began to wonder why
exactly we're adding v * m / dist in the first place.

Imagine that you have a stealth bomber, with move 12. If it's 12
squares away, its threat is v. If it's 13 squares away, the threat is
v * 12 / 13. If it's 23 squares away, the threat is v * 12 / 23. Why?
Is this supposed to compensate for the fact that it can't reach you in
one turn? Then the bomber 13 squares away is nowhere near 12/13ths as
dangerous as the one 12 squares away, and the one 23 squares away is
certainly almost as dangerous as the one 13 squares away, not barely over 
half as dangerous.
Similarly, if the bomber is 6 squares away, is it twice as dangerous?
If it's 1 square away, is it 12 times as dangerous? If this is
supposed to compensate for the fact that it can hit you more than once
in one turn (which, being a stealth bomber, it can't do anyway), this
is completely wrong. The first unit could hit you 6 times. So if that
makes it twice as dangerous as one that can only hit you once, then
the unit that can hit you 12 times surely isn't 12 times as dangerous.

Maybe I'm misunderstanding the intention here?

Meanwhile, I began wondering why the code is using scaled integers
rather than floating point. It can't be to let FreeCiv run on machines
without FPUs, because there are a few floating point values used in
the program (although the vast majority of the calculations done use
scaled integers, you couldn't have any fp if that were the goal). Presumably 
it's meant to be a performance optimization.
So I pulled out the code, wrote a simple driver to call it over and
over, and wrote an equivalent program using floating point. On my
Pentium 200, with as little other CPU work going on as possible
(single-user mode in linux), I got relative times for the floating
point version from .8 to 1.5, averaging 1.1. So using integer math
speeds things up 10%. Pretty small savings, especially since it
doesn't look like much total time is spent in these calculations
anyway.

Then I tried it on some other machines. On a Pentium Pro 200, a
PowerPC 604e 160, and a PowerPC G3 333, the floating point version is
always faster; the relative time ranged from .25 to .85. And when the
CPU is busy doing other things (like running X, Gnome, and a hungry
Gtk app like civclient), the floating point version does even better
(especially on the 604e).

So if this is an optimization, it's not a very good one. On one
processor, it saves you 10%; on three others, it takes twice as
long. It also makes the code harder to read, write, and maintain, and 
there's a known overflow bug (which of course goes away in floating point 
math), along with a bunch of ugly code to detect it.
Anyway, forgetting about the overflow and fp issues, I decided to rewrite 
the code locally to see what effect the m/dist rule has on the AI. 
Everywhere the code used v * m / dist, it instead calls this function:
int adjust_danger_for_distance(struct unit *punit,
                              int danger, int move, int distance)
{
 int moves = distance / move;
 int attacks = move / distance;
 if (moves)
   return danger / moves;
 if (attacks && !unit_flag(punit, F_ONE_ATTACK))
   return danger * attacks;
 return danger;
}

To handle overflow, I then added checks to limit any individual contribution 
and the total with each addition, and a check in the function above to make 
sure that danger * attacks doesn't overflow.
This still seems very wrong to me, but it's at least less wrong.

I playtested this to see how it affects the AI. First, it never overflows, 
but that's not the main issue. It does make different decisions sometimes, 
but it's hard to tell whether these decisions are better, and they don't 
show up all that often.
If anyone else would like to either explain the intention behind the m/dist, 
playtest this variant, or suggest other possibilities to playtest, I'd be 
very happy.


_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com