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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, May 17, 2002 at 10:42:42PM -0400, Ross W. Wetmore wrote:
> 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?

I was asking which of my interpretations matches what you said/wrote
in the last emails.

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

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

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

IMHO you can't define such standard mix.

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

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

Why should we do this for every 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
> };

Ok lets take a look at a profile (current CVS, CHECK_MAP_POS disabled):

ai_calc_*() and city_refresh()

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 13.90     19.66    19.66    36619     0.54     0.81  really_generate_warmap
  3.73     24.94     5.28 87392225     0.00     0.00  map_get_terrain
  2.71     28.77     3.83 119651675     0.00     0.00  map_get_tile
  2.49     32.29     3.52 108872377     0.00     0.00  contains_special
  2.33     35.58     3.29 52019965     0.00     0.00  unit_type_flag
  2.26     38.78     3.20 33272370     0.00     0.00  base_city_map_to_map
  2.07     41.71     2.93      342     8.57    14.17  check_fow
  2.02     44.57     2.86 51048342     0.00     0.00  normalize_map_pos
  1.92     47.28     2.71 51508440     0.00     0.00  find_genlist_position
  1.63     49.58     2.30  1233081     0.00     0.00  road_bonus
  1.62     51.87     2.29 49401402     0.00     0.00  is_valid_city_coords
  1.61     54.15     2.28 51505486     0.00     0.00  genlist_iterator_init
  1.44     56.18     2.03 49883580     0.00     0.00  city_owner
  1.43     58.20     2.02 20535573     0.00     0.00  get_from_mapqueue
  1.32     60.06     1.86 33247681     0.00     0.00  improvement_exists
  1.30     61.90     1.84 20490410     0.00     0.00  add_to_mapqueue
  1.24     63.66     1.76 29689236     0.00     0.00  map_get_city
  1.16     65.30     1.64  8926053     0.00     0.00  hash_fval_int
  1.12     66.89     1.59    10550     0.15     1.90  evaluate_improvements

  1.06     68.39     1.50  3545817     0.00     0.00  base_city_get_food_tile

  1.05     69.88     1.49 13196226     0.00     0.00  
can_player_build_unit_direct

  1.05     71.36     1.48  3789504     0.00     0.00  base_city_get_shields_tile

  1.03     72.81     1.45 49505413     0.00     0.00  unit_type
  0.98     74.20     1.39 20601311     0.00     0.00  is_tech_a_req_for_goal
  0.95     75.54     1.34  2632581     0.00     0.00  amortize
  0.86     76.76     1.22  8643925     0.00     0.00  city_affected_by_wonder

  0.85     77.96     1.20  3189181     0.00     0.00  base_city_get_trade_tile

....
  0.02    138.89     0.03   159799     0.00     0.05  generic_city_refresh


granularity: each sample hit covers 4 byte(s) for 0.01% of 141.42 seconds

index % time    self  children    called     name
....

                0.00    0.06    8935/2590914     ai_calc_transform [256]
                0.00    0.06    9818/2590914     ai_calc_mine [343]
                0.01    0.11   17828/2590914     ai_calc_railroad [297]
                0.01    0.20   31868/2590914     worst_worker_tile_value [250]
                0.02    0.42   68300/2590914     ai_calc_irrigate [154]
                0.03    0.60   97506/2590914     ai_calc_road [162]
                0.05    0.81  130303/2590914     ai_best_tile_value [145]
                0.06    1.08  173944/2590914     best_worker_tile_value [128]
                0.09    1.57  253716/2590914     ai_find_elvis_pos [69]
                0.26    4.63  748853/2590914     evaluate_improvements [15]
                0.36    6.50 1049843/2590914     worker_loop <cycle 2> [24]
[19]    12.0    0.90   16.03 2590914         city_tile_value [19]
                0.17    6.09 2590914/3191237     city_get_shields_tile [31]
                0.20    4.89 2590914/2590914     city_get_trade_tile [43]
                0.18    4.04 2590914/2947550     city_get_food_tile [50]
                0.18    0.00 2590914/5346777     food_weighting [207]
                0.11    0.00 2590914/49883580     city_owner [91]
                0.07    0.00 2590914/2811123     city_tax_bonus [355]
                0.06    0.00 2590914/2600477     city_shield_bonus [380]
                0.04    0.00 2590914/2597456     city_science_bonus [408]
....

                0.00    0.00       1/159799      reestablish_city_trade_routes 
[774]
                0.00    0.00       3/159799      really_handle_city_sell [735]
                0.00    0.00       3/159799      remove_obsolete_buildings_city 
[593]
                0.00    0.00       6/159799      handle_unit_establish_trade 
[649]
                0.00    0.00      12/159799      emergency_reallocate_workers 
[462]
                0.00    0.00      27/159799      transfer_city [316]
                0.00    0.00      27/159799      city_reduce_size [360]
                0.00    0.00      31/159799      global_city_refresh [627]
                0.00    0.00      57/159799      handle_unit_attack_request 
[281]
                0.00    0.00      75/159799      found_new_tech <cycle 4> [212]
                0.00    0.01     105/159799      create_city [288]
                0.00    0.01     145/159799      handle_unit_change_homecity 
[570]
                0.00    0.01     163/159799      update_city_tile_status_map 
[116]
                0.00    0.01     208/159799      city_build_building [335]
                0.00    0.03     524/159799      city_increase_size [271]
                0.00    0.03     603/159799      really_handle_city_buy [404]
                0.00    0.04     737/159799      create_unit_full [273]
                0.00    0.04     774/159799      server_remove_unit [292]
                0.00    0.13    2546/159799      make_scientists [310]
                0.00    0.40    7651/159799      make_taxmen [204]
                0.00    0.50    9563/159799      update_city_activity [101]
                0.00    0.52    9871/159799      auto_arrange_workers [54]
                0.00    0.99   19046/159799      send_player_cities [126]
                0.00    1.03   19728/159799      make_elvises [90]
                0.00    1.20   22896/159799      worker_loop <cycle 2> [24]
                0.00    1.49   28499/159799      ai_manage_taxes [21]
                0.00    1.90   36498/159799      ai_make_elvis [34]
[25]     5.9    0.02    8.34  159799         city_refresh [25]
                0.03    7.74  159799/159799      generic_city_refresh [30]
                0.09    0.46  159799/319598      city_corruption [134]
                0.02    0.00  159799/159799      unhappy_city_check [477]
....
                0.23    1.01  598267/3789504     set_food_trade_shields [51]
                1.25    5.40 3191237/3789504     city_get_shields_tile [31]
[29]     5.6    1.48    6.42 3789504         base_city_get_shields_tile [29]
                0.53    2.83 3789504/8643925     city_affected_by_wonder [32]
                0.19    0.75 3789504/11404098     city_map_to_map [72]
                0.72    0.00 22314616/108872377     contains_special [65]
                0.15    0.15 3789504/22578559     get_gov_pcity [97]
                0.23    0.00 3789504/87392225     map_get_terrain [39]
                0.20    0.00 3789504/12263734     map_get_special [165]
                0.17    0.00 3789504/22960366     get_government [138]
                0.16    0.00 3789504/22959425     get_gov_pplayer [140]
                0.12    0.00 3799595/19628821     get_tile_type [170]
                0.05    0.06 1071880/23115540     city_got_building [80]
                0.08    0.00 2067994/11190076     is_city_center [200]
-----------------------------------------------
                0.03    7.74  159799/159799      city_refresh [25]
[30]     5.5    0.03    7.74  159799         generic_city_refresh [30]
                0.44    4.32  159799/159799      set_food_trade_shields [51]
                0.06    0.61  159799/159799      citizen_happy_wonders [159]
                0.22    0.40  159799/159799      city_support [173]
                0.03    0.45  159799/159799      add_buildings_effect [189]
                0.09    0.31  159799/159799      set_tax_income [203]
                0.06    0.31  159799/159799      citizen_happy_buildings [211]
                0.07    0.22  159799/159799      set_pollution [227]
                0.04    0.08  159799/159799      citizen_happy_size [320]
                0.02    0.01  159799/159799      citizen_happy_luxury [447]
....
                0.23    0.74  598267/3189181     set_food_trade_shields [51]
                0.97    3.22 2590914/3189181     city_get_trade_tile [43]
[40]     3.6    1.20    3.96 3189181         base_city_get_trade_tile [40]
                0.23    1.23 1648838/8643925     city_affected_by_wonder [32]
                0.16    0.63 3189181/11404098     city_map_to_map [72]
                0.62    0.00 19063217/108872377     contains_special [65]
                0.13    0.13 3189181/22578559     get_gov_pcity [97]
                0.19    0.00 3189181/87392225     map_get_terrain [39]
                0.17    0.00 3189181/12263734     map_get_special [165]
                0.14    0.00 3189181/22960366     get_government [138]
                0.13    0.00 3189181/22959425     get_gov_pplayer [140]
                0.12    0.00 3822143/19628821     get_tile_type [170]
                0.03    0.03  600515/23115540     city_got_building [80]
....
                0.25    0.52  598267/3545817     set_food_trade_shields [51]
                1.25    2.56 2947550/3545817     city_get_food_tile [50]
[55]     3.2    1.50    3.07 3545817         base_city_get_food_tile [55]
                0.18    0.70 3545817/11404098     city_map_to_map [72]
                0.69    0.00 21258692/108872377     contains_special [65]
                0.14    0.14 3545817/22578559     get_gov_pcity [97]
                0.23    0.00 7091634/19628821     get_tile_type [170]
                0.21    0.00 3545817/87392225     map_get_terrain [39]
                0.19    0.00 3545817/12263734     map_get_special [165]
                0.16    0.00 3545817/22960366     get_government [138]
                0.15    0.00 3545817/22959425     get_gov_pplayer [140]
                0.14    0.00 3626861/11190076     is_city_center [200]
                0.05    0.06  987281/23115540     city_got_building [80]
                0.02    0.01  243929/483416      player_knows_techs_with_flag 
[390]
                0.01    0.00  243929/49883580     city_owner [91]

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

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  Microsoft does have a year 2000 problem. I'm part of it. I'm running Linux.