[Freeciv-Dev] Re: auto settlers rework

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Jan 22, 2002 at 04:06:20AM -0500, Jason Short wrote:
> Raimar Falke wrote:
> 
> > On Mon, Jan 21, 2002 at 01:05:10PM -0500, Ashley Penney wrote:
> > 
> >>On Mon, Jan 21, 2002 at 11:54:27AM -0500, pc-freeciv1@xxxxxxxxxxxxxx said:
> >>
> >>>In playing Freeciv, I've run into one thing that I think really should be
> >>>reworked: The auto-settler code.  Looking at the current code, each settler
> >>>looks for work to do.  I think that it would make more sense to instead
> >>>have each city create a list of work that needs to be done, and the
> >>>settlers could seek a city that has work to be done.
> >>>
> >>>So each city would have a map of what its terrain should look like, given
> >>>unlimited settler time.  It could then assign a value to each change.  The
> >>>overall value for the city would be largest such individual value.  This
> >>>value would need to be recomputed anytime a settler begins work in the
> >>>city.
> >>>
> >>>Similarly, there would be a value for connecting a city to its neighbors
> >>>with roads or railroads.
> >>>
> >>>Once the initial change has been made, a new tab could be added to the city
> >>>window showing the goals for the city.  This would be a view of the city
> >>>with all worklist items completed, all settler activity completed, and the
> >>>population maximized (up to a zero or negative one food value).  From here,
> >>>the player could make changes to the goals.  For example, a plains could be
> >>>changed to a grassland to stabilize the population (food value of zero at
> >>>max population), avoid pollution from overproduction, or such.  If the
> >>>worklist includes the construction of units, those units could be given
> >>>orders to sentry, fortify, or auto-attack.
> >>>
> >>>Eventually, default goals could be created, much like worklists today.  The
> >>>default goals would include things like what to do with swamps (irrigate to
> >>>grasslands or transform to ocean), taking into account specails, such as
> >>>never transforming an oasis.
> >>>
> >>>The goal should be to be able to create a city and never have to look at it
> >>>again, provided that it is not involved in combat, and yet have the city do
> >>>pretty much exactly what you want it to do.
> >>>
> >>One thing to also add is to take in account the distance the settler has to
> >>travel in order to perform the work.  Nothing like a new city requiring some
> >>work half way across the map, then having the settler move all the way back.
> >>
> > 
> > The current server auto-settler code and also the
> > settler-management-agent (SMA) takes this into account.
> > 
> > 
> >>Trouble with that is that settlers are liable to get stuck in small sections
> >>of the map, due to the distance required to travel elsewhere. :/ 
> >>
> > 
> > The only way AFAIK is to increase the time horizon of the
> > calculation. The current server auto-settler code is based on 24 turns
> > (the famous MORT constant). This means that the action which would
> > yield the most benefit in the next 24 turns is considered.
> > 
> > Example:
> >  build a rail at the current tile:
> >    - time to move to the target: 0 turns
> >    - time to create the improvement: 3 turns
> >    - benefit per turn: 1 trade
> >    - number of effective turns: 24-0-3=21
> >    - total benefit: 21*1 trade=21 trades
> > 
> >  build a mine some distance away:
> >    - time to move to the target: 10 turns
> >    - time to create the improvement: 10 turns
> >    - benefit per turn: 3 shields
> >    - number of effective turns: 24-10-10=4
> >    - total benefit: 4*3 shield=12 shields
> > 
> > So the total benefit of the second will increase with a larger time
> > horizon.
> 
> This is a bad algorithm, regardless of the number of turns that it 
> covers.  Although it accounts for the work time in calculating the 
> *benefit* from the work, it doesn't allow for the fact that "time is 
> money" (i.e. that the settlers can do other work once they finish with 
> the current job).

Ack. Problem how do you weight the time? I see no problems for a
solution where the SMA will just offer an extra weight (in addition to
the current 6) for the time the settler uses. This will leave this
problem to the layer above.

> So if you increase the timeframe enough, this 
> algorithm may tell you that it is worthwhile for the settlers to travel 
> all the way across the continent to build a mine - but not that they 
> should build a road every step of the way (which is beneficial 
> independently of the timeframe).

I know that increasing the time horizon isn't the solution. Sorry I
forgot to mention this.

> The ideal benefit calculation would calculate all the benefit over all 
> the possible choices of work the settlers could do: i.e.
> 
>    build a rail at the current tile: 1 trade per turn, 3 turns delayed
>    then move and build a mine: 3 shields per turn, 23 turns delayed
>    then ...
> 
> would be one possible choice.  As the number of turns considered (N) 
> gets larger, it'll look further and further into the future.  This will 
> allow far-away things to be taken into account, but will not 
> fundamentally change the ordering the calculation will produce.  That 
> is, with N=12 we won't even realize that we should build a mine.  With 
> N=24, we'll realize we should build the mine and that we should build 
> the road first.  With N=infinity, we'll still know that we should build 
> the road and then move to build the mine.

> This calculation still leaves some things uncovered.  For instance, it 
> is difficult (though perhaps not impossible) to account for city 
> population growth in determining *when* a certain enhancement will 
> become viable.  

Ack.

> It also doesn't account for the goodness of building a 
> city (although it could try, if we can somehow assign a "benefit" value 
> to the city).

The current SMA code has this. It will build cities like mad. It is
just the best choice if you have the tiles available. Even if you
account the shields you loss if you disband the settler.

> Finally, it doesn't account for different resources having different
> values; everything is heaped into one "benefit" value (although this
> could be changed).

The user of the the current SMA has to provide weights for this.

> It is also extraordinarily difficult to account for dependencies among 
> improvements.  For instance, you have to do primary irrigation before 
> you can do secondary irrigation.  Also a railroad and a mine may have 
> cumulative effects.  For now, I'll ignore these problems (the irrigation 
> thing should just go away since it's always better to do primary 
> irrigation first, and the railroad thing can be approximated).

Ack.

> Our problem then becomes:
> - For each map tile, we have a list of possible jobs.  Each of these has 
> a time to completion t, and a benefit b.

> - It takes 1 turn to move between adjacent map tiles (accounting for 
> engineers fast movement probably isn't worth it, but should be a fairly 
> easy addition).

Road/Railroad. You also want to consider settler which doesn't have
full move points.

> - We are given a timeframe N.
> - So, if it takes us t0 turns to get to a job site (including 
> intermediate jobs) plus t turns to complete the job, the benefit within 
> the next N turns is b*(N-t-t0).
> - Once we finish with one job, we can go on to another.
> - We want to calculate the path that will maximize our total benefit 
> over the next N turns.  (Again note that as N increases the path will 
> change, but will generally be stable.)

Roughly yes. Problem: you have to reserve actions (you want to avoid
that two settler go to the same spot and work at the same very good
action) and you have to recalculate this at every new turn, every time
a tile changes and every time your path to the destination may have
changed (enemy, ZOC,...).

> This is a pretty standard AI-type search; the problem is coming up with 
> a practical algorithm to find the best path.  I think we can build a 
> "work map" that should allow us to calculate *all* work paths for *all* 
> of our settlers/engineers [1] in O(M*N*N) time and with O(M*N) memory 
> usage, where M is the size of the map (or whatever subset we happen to 
> know about).
> 
> Here's a general approximation of the algorithm.  Note the 
> implementation will probably be quite ugly.
> 
> - Assemble a worklist for each tile.  This worklist holds the order in 
> which jobs should be done in that tile, and allows us to easily 
> calculate the benefit from that worklist.
> - Merging the worklist of an adjacent tile into the current worklist 
> should be an O(N) proposition.  We will then have the order of which 
> jobs should be done over these 2 tiles, given that we start at this tile.
> - For every tile on the map (that we know of), merge the adjacent tile's 
> worklist.
> - Repeat up to N times.
> - For every settler on the map, the worklist at that tile will become 
> their ideal path.

You have to allow actions which doesn't lay at such a contiguous
path. Example: you build your first settler in your first city. The
best solution is to access the tile around and search for a good spot
for a new city and then move there. How will this be expressed in your
model?

> [1] Engineers work twice as fast as settlers.  They also move twice as 
> fast (although this is not really linear).  Different rulesets may 
> specify units that move at different speeds.  We could build a different 
> work map for each different type of unit, but it's probably better just 
> to build one for "settlers" and count the rest as acceptable 
> approximations.  Under SMAC-type rules this won't work, though, since 
> different former-type units actually have different capabilities.

Current algo for the SMA (if I remember correctly):
 if settler runs out of work:
   generate actions (limited by the continent and the turns to consider)
   for each action:
     calculate turns to go there
     calculate benefit per turn
     calculate total benefit
   choose best action
   reserve this action
 // settler has now work
 if settler hasn't started going:
   goto destination (goto agent)
 if settler is on it's way:
   // nothing (goto agent will do the work)
 if settler arrived at destination
   if activity is idle:
     if flag set:
        undo the reservation
        // goto to first if
     else:
       issue activity request to server
       set flag     
   else:
     // wait

This is asynchronously so the first settler available will get the
sweet action. It also doesn't recalculated every turn (it would be
easy to change but it would also be costly).

Managing the settlers as a whole may get better results. But I see an
drastic increase in CPU time.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "USENET is *not* the non-clickable part of WWW!"