[Freeciv-Dev] Re: AI danger (Re: Re: A bunch of patches)
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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.
>
> 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?
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.
> 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.
Ross has the best understanding at this.
Raimar
--
email: rf13@xxxxxxxxxxxxxxxxx
"Just because you put a flag on the moon doesn't make it yours, it just
puts a hole in the moon."
|
|