[freeciv-ai] Re: a global CMA

[Raimar Falke <i-freeciv-lists@xxxxxxxxxxxxx>]

On Wed, Jan 21, 2004 at 09:49:18PM -0500, Benoit Hudson wrote:
> The current CMA optimizes each city locally.  However, this can be
> suboptimal globally: for instance, one city might have two equal-value
> tiles (say, two irrigated plains), and so the optimizer will take an
> arbitrary one without regard to whether that impinges upon a
> neighbouring city that might want to use that tile.
> 
> There's also a problem when a tile become unavailable (because an enemy
> unit is in it), and then when it becomes available again (unit was
> killed), if the city (A) that had that tile before gets optimized after
> another city (B) that can use that tile, A loses the tile to B.
> 
> This is especially annoying when, say, A has all the science wonders and
> a library and university.
> 
> I see a couple ways of dealing with the issue.  One is to write up a big
> huge optimization problem.  It seems unlikely that we could solve it
> optimally anywhere near fast enough, but maybe we can solve it
> approximately and make it fast for updates (tiles getting added/removed
> as units move). 

> After all, the current approach is an approximation;

That is incorrect if you look only at one city. However if you look at
all cities you are correct.

> we only need to do better than it.

> Another approach is to do as we currently do, plus hill-climbing.
> Periodically (how often?), city B would see if the country would be
> better off if it gave up a tile that city A might be able to use.
> City B would surrender the tile if it gives more benefit to city A than
> to city B, and if without the tile, city B still satisfies its
> constraints.  (If you felt like it, you could think of this as a market:
> city B "sells" the tile to city A because city A is willing to pay more
> for it than city B thinks the tile is worth).
> 
> In the hill-climbing case, we have to ask about the policy for trading
> tiles.  One solution to the same problem is to only go for
> pareto-optimality.  That is, only trade tiles between cities if it
> benefits the recipient and doesn't harm the donor (because the donor can
> now work a different tile, or use the worker as a specialist).
> 
> Another solution is to decide that we use the same objective function
> that the CMA uses.  That is, if city B has fitness 56 with the tile, and
> fitness 53 without; and city A has fitness 70 without, and 80 with, then
> we should transfer the tile over to A with a net gain of 7 fitness.
> Possibly problem with this: a city whose CMA has weights of 1 for
> everything will always lose out to a city whose CMA has weights of 2.
> If that's not what we want, then we can normalize the CMA weights to sum
> to 1 when we compute the fitness, and multiply by a city weight that the
> user sets, just to make it more explicit.
> 
> 
> 
> Either approach is going to require being clever about updates to the
> world state in order to be computationally feasible.  I have lots of
> ideas on the hill-climbing end of things, fewer on the global optimizer
> part.
> 
> Comments?

From

Date: Mon, 8 Oct 2001 23:32:41 +0200
From: Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>
To: Christian Knoke <ChrisK@xxxxxxxx>
Cc: freeciv development list <freeciv-dev@xxxxxxxxxxx>
Subject: [Freeciv-Dev] Re: [Patch] CMA 2.2
...
> Maybe you touch the limits of the agent model here.

I know that the CMA will only manage one city and that the behavior in
such cases as mentioned above is undefined. The settler management
agent does do a global allocation of tasks. The question is (if a tile
has become "free" and two CMA-cities want to use it) which city should
get the tile? And another questions is: should it be possible that a
CMA-city gives a tile away if another CMA-city needs it more? The
natural way would be to measure the change of the fitness
method. However there is a problem: the re-calculation of a set of
overlapping cities can be without limit. Another solution which has
nicer properties is:
 - each city has a level
 - in a given set of overlapping cities there no two cities which have
 the same level
 - the allocation of tiles is based on the level

Look at the thread for further discussions.

My current position is that the solution is either:
 - too cpu expensive or
 - too much an approximation or
 - too much micro-mangement is required from the user.

Sadly I don't see a nice solution.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  This customer comes into the computer store. "I'm looking for a mystery
  Adventure Game with lots of graphics. You know, something realy
  challenging". "Well," replied the clerk, "have you tried Windows 98 ?"