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

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

> [per - Mon Sep 20 13:45:26 2004]:
> 
> On Thu, 16 Sep 2004, Benoit Hudson wrote:
> > On Thu, Sep 16, 2004 at 05:30:43AM -0700, Per I. Mathisen wrote:
> > > I am working on a different solution (a greedy worker allocation
> > > algorithm) that should be extremely fast and can be used for this
> purpose.
> > > It will not be finished in time for release, however, unless
> someone else
> > > want to take over writing it. If so, I can post the pseudo-code
> design.
> >
> > I can probably do this.
> 
> Ok, here it is:
> 
> What user input does a CM (citizen management) algorithm need?
> 
> Only two types of input:
>  - relative weights (called hereafter "weights")
>  - absolute minimums (called hereafter "conditions")
> 
> All other kinds of restrictions can be broken down into these two.
> Want no
> unrest? Find the lowest number of luxuries that we need. Want to
> celebrate? Again, find the lowest number of luxuries that we need.

Not quite: the happy/disorder constraints depend both on lux surplus 
and on the number of workers in fields.  Also, the surplus shields etc
depend on whether there's disorder.

I'm not sure if your code is taking account of effects like factories
and taxes.  How do we check what the "best" tile is?  Remember that
usually, trade has zero value -- but it produces gold and science.  So
it's not just production * factor.

Similarly, how do we check what the minimum production is to reach a
given amount of surplus?


> The rearrange function shold _only_ be called when the user or the AI
> explicitly asks for a rearrange. And don't ever "give up".

What about if we can't possibly get the targets?  If we want to never give up,
we'll have to have some kind of solution for the impossible case.


> If we use cm_parameter for input, we should be able to do very good
> comparisons between this algorithm and CMA.

By the way, somewhat sparked by this, I implemented a branch & bound
algorithm.  It's quite a bit faster on small cities, although I think I can make
the current CM get those advantages too.  It's slower on large cities to get
the optimal answer.  But, if we just choose the first feasible answer, we get
almost the algorithm you just outlined.