[freeciv-ai] a global CMA

[Benoit Hudson <bh@xxxxxxxxxxxxxxxxxxx>]

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; 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?

        -- Benoît