[Freeciv-Dev] Re: auto settlers rework

[Jason Short <vze2zq63@xxxxxxxxxxx>]

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

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

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

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.

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

jason