[Freeciv-Dev] (PR#6595) Optimize/reimplement CM

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

This issues is to track all efforts to optimize the existing CM
(common/aicore/cm.h) and/or reimplement it. It is not about finding
the best parameters nor about the best usage of CM.

The discussion so far:

Jason wrote:

  The way the CM should be implemented is with integer linear
  programming via simplexes.  If it's currently done another way
  (brute-force?) we can probably speed things up immensely with a
  correct implementation (linear programming should be linear in time
  rather than exponential).  Of course this is likely to make the code
  even less approachable.

Raimar wrote:

  I think that you can only optimize the optimization of the primary
  stats (food, production and shield). Because the other secondary
  stats depend on a lot of other things (government, happy, rapture,
  city buildings and so on). This will get even worse with gen
  effects. Solution here is to try-and-test. Note that also the
  primary stats may not simply the sum of all tiles. A factory for
  example can increase the production output. However currently there
  is no effect which reduce the primary stats. This makes the
  implementation simpler. This may also change with gen. effects. So
  when the current implementation is adapted to gen effect you can
  expect a slowdown.

Gregory wrote:

  The biggest problem is that this is "discrete" linear programming
  and not continuous.  I was reading a bit on the continuous linear
  programming in the hope that I'd be able to improve CM.  But then I
  realised the methods are not applicable.

Jason wrote:

  Integer programming is pretty easy.  Once you have your linear
  programming solution you just look at all of the adjacent integer
  nodes to find the best one.  Or something like that (I learned this
  a while ago).

  The real issue is that the problem is not linear.  Corruption and
  waste get in the way.  Without ignoring these I don't see how it can
  be done.

Gregory wrote:

  Waste is linear, corruption is almost linear (depending on tradesize
  options).

Mike wrote:

  I wonder if a marquardt type minimization would be faster than
  iterating through each solution.

Per wrote:

  Usually what we want to do is to reallocate _one_ worker. Either a
  worker gets displaced or added (+1 worker) or we need to remove a
  worker somewhere (-1 worker). This we can do by simple iteration to
  see which configuration of current + 1 worker fits the criteria
  best.

Jason wrote:

  But sometimes just moving that worker around won't give you the
  optimal solution.  I don't know how often this occurrs, though.
  auto_arrange_workers could probably log it.

Per wrote:

  However, it has the added advantage of preserving as much as
  possible of the user's configuration. The current
  auto_arrange_workers() rearranges everything, which can be annoying
  if you try to govern a city manually and it frequently changes (due
  to enemy units moving around it, eg).

Gregory wrote:

  This is right.  This is precisely the difference between integer and
  continuous linear programming: the best solution for 2 workers might
  be disjoint from the best solution for 1 worker

  An example: 4 tiles available:  1f/0t, 5f/0t, 3f/3t, 0f/5t
  condition: city doesn't starve + maximize trade

  for 1 citizen 3f/3t tile is the best option
  for 2 citizens 5f/0t + 0f/5t is the best

  so incrementing one citizen leads to a displacement of the first.

Jason wrote:

  Thanks for the example.  I think I agree with Per that the
  advantages (doesn't overwrite current player preferences) outweigh
  the disadvantages (sometimes gives unoptimized output).  Remember
  that the server is optimizing according to its standards, not the
  players.

So you see there are two ways proposed:
 1) reimplment CM with classical optimization techniques
 2) exploit the fact that in the server in some/most/all cases (this
 has still to be measured) only the size of the city changes by one
 (+1 or -1).

My opinion about the first way: I would like to see this but there are
non-linear effects (corruption and the tradesize option) which may be
a problem. Note that gen effects _MAY_ add additional non-linear rules
(I really don't know this). The latter may also be a problem for the
current implementation.

My opinion about the second way: currently you are advised that you
clear the cache of the city you want to query if this city has changed
in any way or was effected in any way (global tax rate change for
example). It is possible that if the city has changed only in size
this can be exploited. However before this is implmented the frequency
of such events should be measured.

Side note: there is the possibility of a larger speed gain by not
clearing the CM caches. However auto_arrange_worker (the current
caller in the server) doesn't know if the city has changed or not. So
it can only play defensive and clear the caches.

Side note 2: I don't like the idea of fast but not optimal result
generation. Here you have to define how much difference from the
optimal result you can accept. Another problem is that in this case
the implementation has to measure this at runtime. So if this is
needed something of the low complexity of the old
server-implementation (or lower) is needed.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  The Software is not designed or licensed for use in on-line control
  equipment in hazardous environments, such as operation of nuclear
  facilities, aircraft navigation or control, or direct life support
  machines. 
    -- Java Compiler Compiler Download and License Agreement