[Freeciv-Dev] Re: [RFC] Caching AI values

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Mar 23, 2002 at 03:09:07PM +0000, Gregory Berkolaiko wrote:
> On Fri, 22 Mar 2002, Ross W. Wetmore wrote:
> 
> > I think Gregory's incremental counter is probably about the
> 
> Hey, it's nice to have you back, Ross! ;)
> 
> > best, but you might want to think about when the counter wraps.
> > 
> > The usual fix for this is to do ((counter2 - counter1) < 0) or
> > something that measures the relative vs absolute times, and thus
> > works across the wrap boundary. It will fail if a value is not
> > updated for more than half the time cycle, but you can't win
> > them all.
> 
> i was more thinking about (counter2 != counter1) which will fail if a 
> value isn't updated for more than the full time cycle, unless I'm missing 
> something.
> 
> > How many counters might you need to (re)set on a given operation?
> > Is this 1, a small fixed number, dynamic/open-ended?
> > 
> > Is there any control on which subsets of counters might apply if
> > there is an open-ended possibility?
> > 
> > What is the way in which you determine the dependency of something
> > and corresponding counter(s) to update? Is this hard coded or is
> > there a "registry" for each something where counters can sign up
> > to be notified?
> 
> Okay, these are very futuristic questions, but I guess one better have a 
> clear plan before doing things.  So here is the "ideal" situation.
> 
> But first a couple of examples:
> ======================================================================

> Cached value: list of all own refuelling points of the type FUEL_CITY
> (basically the list of all cities)

IMHO the speed improvement for this is very small if only cities are
included. The problem are the airbases. To get these you have to
iterate over the whole map. What about a global airbase list? 
Mantained by set_special and clear_special.

> Counter increment: hooked up on events 
> --CITY_LOSS, 
> --CITY_ACQUISITION
> 
> Cached value: list of all friendly refuelling points
> (basically the list of all cities + non-occupied airbases + ally cities)
> Counter increment: hooked up on events 
> --CITY_ACQUISITION, 
> --ENEMY_DESTROYED (it could have been occupying an air-base), 
> --END_OF_PHASE (assuming that city loss can occur only during the enemy 
>                 movement phase)
> Note the event ENEMY_DESTROYED is higly unlikely to change the cached 
> value, so we can skip it here.

Same as above.

> So, ideally, 
> 1. The counters would be subscribed to certain events.
> 2. This "subscription" can be hardcoded.  
> 3. Counter <-> cached value relation can be flexible: one counter can 
> expire several caches.
> 
> Other possibly useful cached values: 

> enemy cities on the continent (useful for global invasion
> management, diplomat code etc)

It has to be tested how much faster this would be compared to a
for each player:
 if enemy player:
  for each city:
   if city.continent==continent:

> enemy targets reachable by unittype around a city (useful for
> bombers etc)

for each unittype:
 for area accessible with this unittype around city:
  if tile has enemy unit:

should be fast.

> wonders built on a continent (useful for caravans and not building
> too many wonders at the same time).

Same as the first: list of cities for a certain player and continent.

> ....thinking.....
> It is also possible to have event_counters rather than 
> cache_type_counters.  Then each cached valued will store the signature of 
> the relevant events.  This way, each event will increment only one counter 
> and each access_*_cache function will check if any of the relevant events 
> happened since the last update to the cache.
> 
> Which scheme is more optimal depends on the access/event frequency ratio:
> if events are infrequent and accesses are, the first scheme is better.
> but if event are frequent, it makes sense to update as few counters as 
> possible after each event.

Sounds rather complex.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I do feel kind of sorry for Microsoft. Their attornies and marketing
  force must have tons of ulcers trying to figure out how to beat (not
  just co-exist with) a product that has no clearly defined (read
  suable) human owner, and that changes on an hourly basis like the
  sea changes the layout of the sand on a beach. Severely tough to
  fight something like that."
    -- David D.W. Downey at linux-kernel