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

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

At 09:57 AM 02/05/17 +0200, Raimar Falke wrote:
>On Thu, May 16, 2002 at 09:25:02PM -0400, Ross W. Wetmore wrote:
>> At 09:09 AM 02/05/16 +0200, Raimar Falke wrote:
>> >On Wed, May 15, 2002 at 08:59:43PM -0400, Ross W. Wetmore wrote:
>> >> At 08:49 AM 02/05/15 +0200, Raimar Falke wrote:
>> >> >On Tue, May 14, 2002 at 07:38:09PM -0400, Ross W. Wetmore wrote:
>> >> 
>> >> >We have two different problems here:
>> >> > - which city have to build at which time a worker
>> >> > - if we have a worker how should it be used
>> >> 
>> >> Yes, and recognition of this is a key step, kudos.
>> >> 
>> >> >I have code for the second problem but not for the first one.
>> >> 
>> >> >> You would be better off keeping a running tally of the possible 
>> >> >> improvements to all controlled terrain with a quick shield/food/trade
>> >> >> weighted benefit scaled by the size of your Civ in cities or pop.
This
>> >> >> would consume almost no CPU even if you did a full reset every few
>> >> >> turns as a sanity check. Set threshold levels on how many workers
you 
>> >> >> need to maintain a given rate of growth. Rate of growth is a 
>> >> >> personality/management concept missing from Freeciv. 
>> 
>> >> When I say a running tally, I mean a really trivial
>> >> count of the possible improvements as shield/food/trade totals. As a
>> >> per Civ enhancement I might scale each by the current *_WEIGHTING so as
>> >> to reflect the Civ strategy better. The reason for scaling by Civ size
>> >> is so I can gauge whether I am a perfectionist or have no interest in
>> >> improvements and thus if one in twenty of my tiles are improved I am
>> >> happy and don't need workers.
>> 
>> >Ok. I agree and understood expect this "scale by the size of your
>> >civ". What is scaled? and how?
>> 
>> The running tally is scaled so the value reflects weighted improvement
>> workload per city, i.e. the total workload / city_count. If I found more
>> cities and increase the tile base, but complete a comparable number of
>> improvements at the same time the per city counts will remain constant.
>
>Since I also don't understand this now, let me guess:

First the exact makeup isn't really critical for running tally purposes
which are really just used as rough guidelines to measure worker load
vs current worker capacity. Absolute accuracy isn't required either, so
if your tally isn't quite up-to-date because you haven't yet processed
something for this turn, it shouldn't make a huge difference. It means
you may end up with a worker or two more or less than some inaccurate
estimation says is optimal.

> 1) there is a list of open jobs/tasks/actions. This list is limited to
> x*number_of_cities. Where x is maybe 21.

If it helps you conceptualize the problem, then you can think of the
running tally as being done over the list of open tasks from all your
citymaps. If you were keeping this as a list, say for SMA use, then
you might probably have road/rail lines between cities as tasks, or
other embellishments. I wouldn't get hung up on "limited" as an
rigorous concept, but "on the order of" is correct.

> 2) the gains of all possible jobs are summed. This structured (food,
> shield, trade) sum is divided by number_of_cities.

Yes. 

I would use a weighted sum for the total and maybe keep the individual
resource sums as well. A weighted ETA might be quite useful too.

Note, the only time you need to adjust the running total is when you add
a new set of tasks to your virtual list, or complete one and remove it.
The running totals take at most 4-5 ints, right?

And each tile could keep a running subtotal or list of tasks specific 
to it.

> 3) the gains of all jobs which are done are summed. This structured
> (food, shield, trade) sum is divided by number_of_cities.

You could do this too, I guess. I presume it would allow you to calculate
the total number of tasks more accurately to do a percentage completion.
Or turn to turn values would give the current worker completion rate, as 
opposed to the current task generation rate.

Note in general a tile will have 3 or 4 improvements, a road + rail plus
a mine or irrigation + farm. Transform resets the tile clock, and pollution
is just ongoing noise. So you can think of a tile as starting from 4 or 3
and counting down to 0 (fully improved).

A citymap will thus have somewhere between 0 and ~80 outstanding tasks.

A city of size 10 will have somewhere between 0 and ~40 outstanding tasks
for it to reach its fully improved state. 

You can do a fair bit with just this sort of estimated data. For example,
a perfectionist might try to keep the outstanding task list below 50% of
pop size, and concentrate on doing this for the largest cities on down
on a per city basis.

Another strategy might be to keep this below 200% of pop size and do 
those cities that are farthest from the civ-wide average first.

If you are losing ground, you need more workers, if at or gaining ground
you probably have too many.

> 4) food, shield and trade is summed over all tiles which are in the
> citymap of any of the cities you control. This structured (food,
> shield, trade) sum is divided by number_of_cities.

This is really the resource base for your Civ, and thus this is the
critical set of paramters you probably want to have for a number of 
other analyses.

For worker load management, you probably want just the task stats
though.

>Is it 1, 2, 3 or 4? Or 5?

Is it clearer?

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

For simple resource values, you can probably do a lookup of the value
in a per government array to get back the adjusted one. You might even
get by with lookup transformation of linear weighted totals.

>> Note needs are typically set by outside or straightforward influences
>> and computed as a general category selection then internal comparison. 
>> Benefits typically require in depth case specific calculation for final
>> comparison across disjoint categories.
>
>I understand. However I would say that except possible CPU
>optimization a need problem can be transformed into benefit problem
>and back.

Possibly, but the selection criteria generally do not follow the same
algorithms, or go for quite the same results.

That is why socialists (on the need side) can't quite transform their 
values into capitalist terms and vice versa :-)

That is also why benefit arguments always sound like hand waving, and
need arguments so much more obvious :-) :-).

Or why temples, colosseums and cathedrals cost less than marketplaces 
banks and stockmarkets ...

>       Raimar

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.

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.

Cheers,
RossW
=====

/*
    This shows how the various resource statistics might be organized for
precomputed caching and fast runtime lookup.

    The following terrain breakdown shows there are 128 core terrain
types that can be improved to 16 different/compatible states by worker
actions (road/rail, mine, irrigate/farm). There are 4 possible pollution
states which may be reverse improved to restore a Base unpolluted state.
    Terraforming is considered separately as it merely changes the type
to point to another index entry.
    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.

    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 largest simple
resource is currently 7, so even with a lookup per resource type the
size is not a serious factor. The total will probably be a full 256
values.

    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. One could add a state boolean which can be flagged STALE
whenever there is a permanent terrain feature change within the citymap
and delayed recompute, or do a running update when the terrain change
occurs over the surrounding citymap region.

    To handle the government effect, 3 x 8 bytes per tile would be needed
with the 3 separate stats sets computed.

 CITY STATS[8 or 32]
   {Total, food, shield, trade}                 4
 x {Base, RMS}                                  2
 x {retarded, standard, enhanced, gov-reserve}  4

 TERRAIN RESOURCES[4]
   {Total, food, shield, trade}                 4

 TERRAIN IMPROVEMENTS[64]
   {Base, mine, irrigate, farm}                 4
 x {Base, road, rail, maglev}                   4
 x (Base, pollution)                            2
 x (Base, fallout)                              2

 TERRAIN TYPES[128]
   {Base, river}                                2
 x {Base, special1, special2, reserve3}         4
 x {T_ARCTIC ... T_USR3}                       16

e.g. A tstat cache computed once at game startup from ruleset input.
     One would need one per government level, or use a lookup mapping.

char tstat[4 entries][4 pollution][16 impr_states]
          [2 river][4 specials][16 terrain_types]
 => [32K byte values]  (compare to 80x50 map with at least 2 enums/tile)

    Note, if the terrain_type is coded as a carefully crafted bit vector
then the appropriate stats can be indexed by a masked lookup. The reference
vector for any state would be TSTAT[(terrain_index & ~T_<type>SET) | <type>].
Individual stats would be accessed as
  ttotal1(t_index, target_type) or  ttotal0(t_index)
  tfood1(t_index, target_type)  or  tfood0(t_index)
  tprod1(t_index, target_type)  or  tprod0(t_index)
  ttrade1(t_index, target_type) or  ttrade0(t_index)
The benefit vector for any improvment would be
  tref1(t_index, type) - tbase(t_index, type)
In the case where an improvement is destroyed as in irrigating a mine, this
would be
  tref1(t_index, target_type) - tref0(t_index)
Such lookups could replace significant code/computation in routines like
ai_calc_*() and city_refresh().

    The tile structure would store one int or ushort variable in
place of the various enums and stats objects. This would be used to index
various static data such as the above stats, struct tile_type info (string
names, etc. for the base terrain types), ...

    In general access to backend data structures should be through a
function (or macro) reference, so that lookup or computation techniques
can be used interchangeably, with various levels of caching to control
memory vs CPU usage.
*/

/* This is the definition of the basic terrain index */

enum terrain_type = {
  T_ARCTIC,                     /* 16 basic terrain types */
   ...
  T_TUNDRA,
  T_UNKNOWN,
  T_TYPESET   = 0x000f,

  /* Bit vector extensions - sets of key index elements */

  T_BASE      = 0x0000,  /* base plus 3 special types */
  T_SPEC1     = 0x0010,
  T_SPEC2     = 0x0020,
  T_SPEC3     = 0x0030,
  T_SPECSET   = 0x0030,

  T_RIVER     = 0x0040,  /* river (with canal/channel order some day) */
  T_RIVERSET  = 0x0040,

  T_ROAD      = 0x0080,  /* road, rail (and future maglev) */
  T_RAIL      = 0x0100,
  T_MAGLEV    = 0x0180,
  T_ROADSET   = 0x0180,

  T_MINE      = 0x0200,  /* mine, irrigation , farm improvements */
  T_IRRIG     = 0x0400,
  T_FARM      = 0x0600,
  T_IMPR1SET  = 0x0600,

  T_POLLUTION = 0x0800,  /* pollution and fallout reduction - 1 or 2 sets? */
  T_FALLOUT   = 0x1000,
  T_POLLUSET  = 0x1800,

  T_STATSET   = 0x1fff,  /* end of stats cache index */

  T_HUT       = 0x2000,  /* special improvements */
  T_FORTRESS  = 0x4000,
  T_AIRBASE   = 0x6000,
  T_IMPR2SET  = 0x6000,

  T_FULLSET   = 0xffff,  /* end of full index */
  T_LAST      = T_FULLSET+1
};