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

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

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.

Cheers,
RossW
=====