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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 02:22 AM 02/01/08 +0000, andi payn wrote:
>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.

If you have you might be the first, including the original author :-)

But you've done a reasonable analysis.

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

There is code to reset this in some places where it is used.

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

This is the effective code, i.e. MIN(1<<24,val) or the equivalent. This
may not be enough to guarantee that multiplying it by some factor, or
adding up enough factors doesn't overflow. You get 2^7 or 2^ 8, i.e 128 
or 256 chances which is not really that big.

Setting the cutoff at anything over about 2^10 won't cause much of a 
difference. This is a panic reaction. Infinity x panic == panic in most
situations.

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

Don't ask ... that way lies therapy.

>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?

One should not read too much into individual factors here. One could
explain this with some arcane suggestion that this is a probability
that the plane will randomly pick this <blort> to attack that dies off
as the inverse of the distance, i.e. based on how many other things
might lie in that square (constant distance is a square not circle in 
Freeeciv) divided by some other distance related factor like the number
of squares it would need to random walk to reach <blort>, so it works
out to inverse distance.

The only value in this is giving you a warm fuzzy feeling that you 
understand something.

The end result is a weighting function that scales as a number of
parameters and which someone thought made units move about the map
in a sensible fashion.

Surprisingly, it usually does work, and often not badly.

There are also at least 2^31 other possible algorithms just as good, 
and 2^31 worse on a 32 bit architecture :-).

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

I suspect, that modern chips can do FP arithmetic almost as fast as
integer, and with the parallel internal pipelines, this is a totally
unused CPU resource. Old performance excuses are likely gone, but they
were only excuses.

Unix types, especially "C" programmers hate floating point, which is
really only loved by FORTRAN programmers ... proof complete as to its 
value or lack thereof.

You get too many integer exceptions when large floats are stuffed
back into integer values, and the code to check and work around all
this is a real pain. 

Most people can't do floating point math in their heads and screwup 
the roundoffs, so they can never figure out what the algorithm should 
have done anyway. This is a special problem for "C" programmers who
just can't except that 2+2 = 3 is perfectly good floating point math
no matter how many times the FORTRAN programmers patiently try to
explain precision to them or why brackets really need to be respected
and not optimized away by the peephole optimizer.

Floats are also less precise than integers, and dfloats take up too 
much memory.

For most games and simple stuff, it is easier to accept the old "C"
biases and just work in integral math.

>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, 

The overflow warnings don't do anything either. No matter how loud it
cries "I'm dead" it is believed approximately same amount of the time, 
with the same effect.

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

This is the real test. After watching hours of client autogames and
dumping out the internals from a few suspicious cases is there something
better or worse about the AI play.

In most cases, even a bad move or two doesn't affect the game materially 
over the total game span. So it is really difficult to decide. 

If you can catch an edge case where it will consistently do the wrong 
thing and correct this, this is much more productive.

>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

Cheers,
RossW
=====