[freeciv-ai] Re: ai bug when splitting up settlers

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, May 18, 2002 at 02:17:55PM -0400, Ross W. Wetmore wrote:
> At 09:31 AM 02/05/18 +0200, Raimar Falke wrote:
> >On Fri, May 17, 2002 at 10:42:42PM -0400, Ross W. Wetmore wrote:
> 
> >> >> Again, the per tile stats can be computed once at game startup. You
> >> >> could even do the full city sums then as well. They really only change
> >> >> if you terraform, and even then you just need to apply the appropriate
> >> >> deltas when this happens. Virtually all of the terrain based bonuses
> >> >> fall into this category. You can use these as a starting base and add 
> >> >> any dynamic things as a non-constant part of the bonus calculation.
> >> >
> >> >Government change?!
> >
> >> Good, one. You probably want to store 3 sets (sigh), one for each level 
> >> of government, this will be almost mandatory for any reasonably complex
> >> computed value.
> >
> >I count 6 governments. Note the values of these can be changes anytime
> >by the user in the ruleset.
> 
> There are 7 government types ...
> anarchy,despotism, monarchy,communism,fundamentalism, republic,democracy
> 
> ... but, I believe, as far as terrain resources, just 3 effective states
>   limited(food <=2), standard, enhanced(prod,trade 50% bonus)
> 
> You also need to include rapture effects, since cases like raptured
> communist cities receive republic/democracy terrain bonuses, and 
> raptured despotic cities, monarchy food levels.
> 
> But this should just be 3 government adjustment sets, however you compute 
> the effective government state for terrain bonus, no?
> 
> 
> >> Just for fun, here is a quickie analysis of how simple resource values
> >> might be organized for caching with rough estimate of the memory costs 
> >> for the cache. Values are assumed to be computed once at startup and 
> >> tiles repointed to the set for the current tile state. All tile values 
> >> are thus a simple lookup with no runtime computation.
> >
> >> Such lookups could replace significant code/computation in routines like
> >> ai_calc_*() and city_refresh() that are commented as being resource pigs.
> >> In addition the government effect could be builtin at a cost of tripling
> >> the storage, but could then be used everywhere it currently is listed as
> >> a wishlist.
> >
> >I agree that such caching of such tile stats my speed up city_refresh
> >and some other functions. However this is a generic problem and it
> >isn't connected to settlers.
> >
> >> A more complex citymap statistic could be quickly computed from these
> >> values. Because datasets are easily recognized as constant or modular
> >> components of such computations, it may make running totals, or update
> >> choke points much simpler to identify.
> 
> Reading one paragraph further might provide some sort of connection.
> 
> >>     The resource values for each of the 3 resources in each state plus a
> >> weighted average that reflects a standard mix (e.g. food(x5), shield(x4),
> >> trade(x3)) can be stored in 4 bytes.
> >
> >IMHO you can't define such standard mix.
> 
> Why not? The current code does. 
> 
> I agree, that mix ratios should be personality effects, i.e. adjustable.
> But that still doesn't stop one from using a standard pre-computed mix
> for some purposes.
> 
> >>     Government effects can be handled in 2 ways. The first is to increase
> >> the cache size as for any of the above to reflect the 3 basic levels. The
> >> second is to recognize that specific values will be mapped in well-defined
> >> ways by the government effect and provide an extra translation lookup for
> >> each government type. The latter will work as long as the values to be
> >> adjusted are unique. This should not be a problem with simple resources,
> >
> >> but the totals may give some trouble in a few cases. 
> 
> The totals referred to above were for single tile mix computations, not 
> full city stats. If you added additional per tile cached values, then the
> logic applies to these as well. I think it breaks down for RMS, and 
> certainly for citystats (multi-tile).
> 
> >IMHO it is fast to calculate such totals:
> > food_sum=0
> > for each ptile:
> >   food_sum+=govern_food_change[type_to_base_prod[ptile->type],
> current_govern]
> 
> The above is certainly a *lot* slower that a single lookup. This is the
> source of the basic piggery in ai_calc*() and city_refresh(). Plus the
> fact that you do this looping everytime you request a value, whether
> or not the underlying conditions have changed.
> 
> The basic thrust of caching is to identify the static or unchanging
> elements. If an effect causes a recompute then you look to cache the
> computed value for each effective state and build the effect into the
> lookup selection. You can cache all states, or just the last state to
> limit the recompute cycle and provide some way to flag the state
> parameters that have changed. This leads into GB's work.
> 
> >>     City stats would be a sum/average over a citymap set of these values,
> >> with a root mean square (RMS) comparable calculation providing a useful
> >> handle on the diversity of the sum/average. 
> >
> >> This would occupy 8 bytes per map tile.
> >
> >Why should we do this for every tile.
> 
> Try reading the above as, if you do it, it costs 8 bytes per map tile.
> 
> You can do a lazy evaluation on first access, or determine more 
> complex update scenarios if you like (a la GB). It probably makes 
> sense to exclude update to all but the city center of a citymindist 
> map once a city is founded.
> 
> But settler tasking iterates over every tile when determining city 
> founding choice so this would eventually initialize every land tile 
> (+ocean if one has civAC type sea cities).
> 
> Adding the stats object the server map allows everyone to query the
> same constant values without recompute.
> 
> >Lets suppose we are talking about a cache for base_city_* (I know that
> >you are also about talking caching some sums). The main user of
> >base_city_* is city_tile_value causing 7.7 mio calls out of 10.5 mio
> >calls total. All base_city_* functions total take 12.4% of the total
> >time.
> >
> >Question: can the city_tile_value values be cached? Or calls be
> >avoided? I know that this does solve all remaining problems. It just
> >looks like a good opportunity.
> >
> >     Raimar
> 
> It is good you are picking up concepts rather than treating this as a 
> set of specific one-off implementation threads (implementation is for
> clarifying example rather than hard proposal at this stage of design
> conceptualization).
> 
> From the concept standpoint, 
> 1)  it is pretty obvious base_city_* values are still too complex to 
> be simply cached. So as you suggest, one needs to look at sub-elements.
> 2)  most of the work is in the iteration, and city_tile_value computation
> is only one aspect of this. Simply improving it will at least initially
> provide a linear boost but will asymptotically approach the 20-25% limit.
> 3)  it is easier to optimize city_tile calculation by not doing it, than
> by doing it more efficiently. If the iteration set doesn't change, then
> you don't need to do any new calculation. If the iteration set changes
> only in one or two elements, then you may be better off doing a delta
> iteration. set_food_trade_shields() should be optimized to use some sort
> of city sum caching.
> 4)  you need to move things like superhighway effects out of the lowest,
> base_city_get_trade_tile() in this case, levels of the computation. This 
> means a layer that calculates just raw or summed stats and a layer that 
> adds improvement effects. There may be different interface calls for full
> standalone city_tile computation or raw stats to be used in further work. 
> Superhighway and harbour are tricky. You need the iteration count broken 
> down to provide land+ocean subcounts. Offshore is another in this 
> category, as is Supermarket (but supermarket probably needs to be a flag 
> on whether the base stats point to farmland or irrigation), right?
> But I think you can move these up to be outside the loop in 
> set_food_trade_shields() with a little effort. You would add the same
> adjustments in the non-base flavours if you just want a single tile value
> but this makes non-base calls non-cacheable (or highlights this fact).
> 
> Aside: it would be a neat rule option to make harbour, superhighway and
> offshore (at least offshore) work like farmland, i.e. you need to take a 
> worker out in a boat and do the mine/irrigate/road activity. Or conversely
> turn off the additional farmland step and have all irrigated tiles become
> farmland with the building of a supermarket. If there is a special terrain 
> improvement activity, then the terrain stats need to include this case. If
> it is just an improvement effect, the adjustment layer needs to be added.
> End_aside:
> 
> But with 4) I think you could do this. And with 3) I think you would see
> fairly dramatic changes much quicker, even with the current underlying
> versions.

Ok I now think that I understand you. You want to cache certain
tile/terrain stats. While I agree that it is a good idea to test this
for the general stats (return values of base_city_get_*_tile and
get_*_tile) I don't like the idea that code in common/ update AI
specific sums/values. General callbacks which common/ code calls and
the ai/ code sets are however ok. Note that with test I mean that we
have to see how much code impact this would have (it shouldn't be
much) and how much speed we can get.

As a side note I would also like to move tile_move_cost_ai,
reset_move_costs and initialize_move_costs to ai/ and replace them
with a generic callback.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 Make a software that is foolproof, and only fools will want to use it.