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

[Raahul Kumar <raahul_da_man@xxxxxxxxx>]

--- Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
> On Tue, Jan 08, 2002 at 02:22:55AM +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.
> > 
> > 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.)
> 
> This is a possible solution.
> 
> > 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.
> > 

You're right. The code is generalised to handle all units, it doesn't
specifically make allowances for special cases like air units and battleships.
The AI as a whole cannot handle the properties of air units well.

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

No, you're right.
 
> I don't know the intention either. However your ideas make sense. Note
> that this is however only an estimation.
> 
> > 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.
> 
> Freeciv has a long history. It may that the integer version was faster
> in the past. Floating problems bring there own problems with them.
>

If floating point doesn't introduce any problems with compiler issues, it would
be the better way to go. Unfortunately, there may be problems with the Amiga.
 
> > 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;
> > }
> >

Question on this function. Moves is move_rate?, you have not checked whether
the unit can even attack(battleship is never a threat to an air unit), is this
handled elsewhere?
  
> > 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.
> >

It's better. There must be a better scheme than this. Possibly something like
this might work 

Danger * if unit ignores walls
Danger * if unit is immune to zoc
etc

> > 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.
> 
> Ross has the best understanding at this.
> 

I suspect this is a very badly bugged piece of code. Petr and Ross will
probably
agree.

__________________________________________________
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
http://promo.yahoo.com/videomail/