[freeciv-ai] Re: (PR#9623) Re: terrain improvers (fwd)

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9623 >

On Fri, Aug 06, 2004 at 10:43:46AM -0700, Gregory Berkolaiko wrote:
>
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=9623 >
>
> Thoughts on terrain improvers:

Here's a CM-centric way of doing it.  Too expensive for now, but with
a better dynamic CM algorithm we might be able to do this:
1- compute the fitness for each city that can use the square, unimproved.
        [that is, run CM allowing it to use that square]
2- compute the fitness for each city that can use the square, improved.
        [that is, run the CM again, but increasing the square's value]
3- use the maximum difference for any city.

Probably we want to scale the CM weights so they sum to 1 so we can compare
cities directly.

The current big cost is going through all the CM's combinations and
deciding which is best.  Step (1) we can cache at the start of the turn:
every city just remembers its fitness and its best combination.  So it's
fairly cheap.

Here's an approximation that may work well enough for step (2):

If the current best combination uses the tile, then just compute the
same combination with new tile, and use the difference as our benefit

If the current best combination does not use the tile, see if you could
switch exactly one tile out of the current best to use the new tile.
That is, loop over each tile in the current best combination.  Each
time, compute the fitness if you'd used the new tile instead of this
tile.  Report the largest improvement, 0 if it's never better.


Both of these are only approximate, but very fast to compute.

The approximation comes from two things: constraints, and roundoff from
computing bonuses.  We might currently be using a 1/0/0 hill to get
enough food rather than the 0/1/6 gold mine, but when you irrigate
grasslands suddenly you have enough food to use the mine, so while
before the gold mine solution wasn't feasible, it now is.  I don't think
this source of error is bounded.

The roundoff is much less important: this is from how a change of 1
trade can be a change of 4 tax.  If the second-best combination gets
this kind of effect, but the best combination doesn't, then you miss
some of the benefit.  You can't be off by more than a little bit here
(maybe 3x the max weight?)

A note: figuring out exactly what tiles should be improved is hard,
because really you should try out all combinations of all tiles in the
country, so we're stuck approximating.


What you wrote for taking account of time seems exactly right.

If we get really fancy, we could also take account of the city growth.
Improving a tile so the city grows faster can make a big difference in
the medium to long term.

        -- Benoît