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

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

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.

A perfectionist would want at least worked tiles to be 100% improved,
while an environmentalist would want none.

>Do you know that you speak here about a list of multiple 1000s
>elements in a midgame?!

A running total might be 4 numbers {combined,shield,food,trade}. Add
21*4 everytime you build a new city, and update 2 of the 4 everytime
a worker completes a task.

Even if you reset, the reset might be 20 cities x 21 tiles per city for
a reasonably large sized Civ.

The server could actually build the initial values for all tiles at the
start of the game and update them anytime an improvement is completed, 
and a data query per city-sized chunk would be a reasonable way for a
client to get such info if it didn't want to cache its own computations.

It is certainly possible to come up with an incredibly expensive and
extensive methodology to do such things, but in general I would assume
one wanted to cache static values, update them only as needed and do
computations based on running totals and changes, not blindly from 
scratch everytime a lookup is requested.

>> Actually, you really don't need the kinds of details in eval_city_building.
>> 
>> All cities will essentially follow the same growth and lifecycle pattern
>> so you don't need to keep recalculating this constant base over and over 
>> again in excrutiating detail.
>> 
>> What changes are the strategic effects and the deviation of resources
>> from the norm, none of which are really looked at currently.
>> 
>> For example, doing an average and RMS average of each tile resource 
>> with a *_WEIGHTING version of the total over the city_map will tell 
>> you immediately if it is above or below average, with the RMS values 
>> telling you how diverse it is, i.e. if there are some large key
>> resources.
>> 
>> Doing the same for the best 5 food, 4 shields and 3 trade tiles will tell
>> you if it has good startup potential or a solid core resource base that
>> allows for flexible worker allocations. You might do this as both the 
>> minimum (undeveloped) and maximum (fully developed). The former will be 
>> more appropriate for the early game, while the latter applies to the mid 
>> and end game where you have an existing worker pool that can keep ahead 
>> of the city development.
>> 
>> Over time the weighting function can be adjusted to recognize a good
>> balance of startup growth, mix of terrain/resource types and maximum
>> potential.
>> 
>> To this you can add "bonuses" like river connectivity, sea access,
>> protective mountain or hilly terrain, new continent beachhead, or
>> "negative bonuses" too much improvement required (swamps/jungles), 
>> bad packing, far from core Civ base.
>
>Nice ideas.
>
>> None of this takes a lot of CPU either.
>
>No but a lot of parameters or a callback function which does all the
>calculations.

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.

Most of the elements should be statistics data retrieved by lookup.
The weighting function then combines this data, adding dynamic 
instance data to it if necessary to produce a weight/want value.

This is what happens in the current code, except the statistics are 
typically recomputed on the fly, often not particularly appropriate 
or useful for the real purpose, and the separation of statistics and 
weighting parameters or functional decision making is not clean, so
what is really being done is pretty obscure.

The first stage is breaking some of the current code down into smaller
routines that lookup stats, produce stats and massage stats data. The
next, or as part of this, is to separate the instance from the static 
components. Note GB was looking at methods for caching and updating
these sorts of things. Combined with a cleaner separation of the
cachable and the require-dynamic-compute would be a good step in this
direction.

>> For worker management in the CMA, you can really evaluate every
>> tile improvement benefit for the city once and store it as a list
>> of tasks sorted by weight. The benefit is a delta resource times
>> some sort of *_WEIGHTING factor, amortized if you can't live 
>> without this, but it really isn't that important.
>> 
>> When it comes time to allocate a new worker task, you can pick the 
>> highest benefit task for "currently" worked tiles, and the highest
>> benefit task for unworked tiles that would improve the tile to a level
>> at or above the next best unworked tile (in at least one capacity).
>
>I agree that something like this is needed for a (very) good
>AI. However I think that to get a manageable (at the code base) AI we
>have to seperate areas. So I'm pleased with the current first version
>of CMA. It may have to be extended at some later point to collaborate
>with other agents to be more efficient. The current SMA solves this
>problem by this code:
>
>+  if (is_currently_used_by_a_city(x, y))
>+    /* the city WOULD benefit fully */
>+    effective_percent = 100;
>+  else
>+    /* the city COULD benefit from it if the city grows or changes
>+       its distribution of workers */
>+    effective_percent = parameter->unused_tile_percent;
>
>So there is a chance that a settler improves the tile and a turn
>latter the CMA uses it.

This is fine as well. This is one way to merge the above two lists 
into something based on a common weight scale. And since I like to 
sort all list elements by weight then do a biased random pick as a 
way to introduce flexibility and unpredictability into the AI actions, 
something like this would be a good extension to the basic computation
and/or selection process.

>> You might try adding in improvement effects, but I suspect that over
>> the long haul they won't be half as useful as say a city need effect
>> weighting, i.e. need more food, or need more shields. The improvement
>> effect will be taken into account by how much it diminishes need and
>> thus the time until this need resurfaces, i.e. indirectly over a 
>> series of improvement tasks, this will deal with amortize as well,
>> as a big long time effect, will presumably keep the city content in
>> that need category for a longer time until the need resurfaces.
>
>I don't understand this.

Tactically, need is a better driver than benefit. Need is typically a 
negative feedback parameter that prevents bad things from happening and 
corrects them. Benefit ignores the bad side and concentrates maximizing 
the potential good, but can die in the process. Benefit tends to be a 
positive feedback effect that can spiral out of control.

If the Civ-wide mandate is to grow, or a city is facing shortages, i.e.
there is a food need, then any "small" benefit food improvement is worth 
far more than a "big" benefit production scaled by Factory and PowerPlant. 
Once the food situation is under control, the production improvement can 
take place.

If need is the constant driver, then when the production need arises, 
the big benefit will insure it is a long time until the next need hits
here. You don't actually require a major improvement calculation to
determine which is the big production benefit, as improvement effects
will apply proportionately to all production tasks. 

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.

>       Raimar

Cheers,
RossW
=====