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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

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:
 1) there is a list of open jobs/tasks/actions. This list is limited to
 x*number_of_cities. Where x is maybe 21.

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

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

 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.

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

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

Government change?!

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

I understand. However I would say that except possible CPU
optimization a need problem can be transformed into benefit problem
and back.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "SIGDANGER - The System is likely to crash soon"