[freeciv-ai] Re: (PR#10203) Greedy CM algorithm

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

On Thu, Nov 18, 2004 at 05:19:50PM -0800, Jason Short wrote:
> It is close to a linear programming problem, which is easy.  However 
> it's actually an integer programming problem, which is hard.

LP is easy; IP in general is hard; but some IP problems are easy.
Integer network flow, for instance, is O(n^2 lg n) or somesuch
(certainly it's O(n^4); can't remember the current state of the art).

I suspect that the constraint structure of our problem makes it hard,
but I'm not sure.

I wonder if any conference would take a paper on solving the Freeciv
Tile Assignment Problem.  :)


> > Things we can do to speed up the CM:
> - Call it less in the client.  This is an alternative to moving it 
> entirely to the server that should be feasible for 2.0.

Sending the parameters server-side is very sensical.  I can see at least
one place you'd probably want the CM to be run client-side: when you set
the parameter.  No point transmitting that to the server until you're
done setting.

We're already doing the CM server-side, so this seems like it should
save on total CM time, and as you point out, be far better for the
latency the user sees.

I am a strong supporter of this idea.  Doubt it'll happen for 2.0 though.

> we have to decide what to do if the CM can't meet the requirements by 
> placing just once citizen: does it run from scratch or give up?

There are all sorts of policy questions that I've considered:
- when to run place-one versus full
        Perhaps: if the user put down the citizens, we should run 
        place-one ; if the user asked for the CM, we should run full.
        But what do we do under place-one if the city shrank?
- under full, what if we can't meet the requirements
      * just maximize the weights, ignore the requirements
      * relax the requirements until we can meet them (how?)
            one way: violating a constraint by x gives a charge of x^2;
              you're required to minimize charge, and among solutions of
              min charge, maximize fitness.  (a solution that has food
              surplus -2 and requirement +1 has a charge of 9, so it's
              worse than a solution that has food -1 and shields
              -1 [charge 5].  But maybe this isn't the best idea.
              But in practice it works pretty well.  Another question:
              how to deal with the happy requirement?)
      * maybe we have a list of CM params; pick the first that we can
            meet (like in auto_arrange_workers)
- under place-one, what if we can't meet the requirements
      * same options as under full
      * or, run full

        -- Benoît