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

["Per I. Mathisen" <per@xxxxxxxxxxx>]

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

On Thu, 23 Sep 2004, Benoit Hudson wrote:
> > 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.

Do you mean units in the field and size of city here? In either case, we
can precalculate the number of luxuries needed before starting the
algorithm.

> Also, the surplus shields etc depend on whether there's disorder.

I do not see this as a problem. In the algorithm, we ignore disorder, and
hope that the calling code has managed to give us a luxury minimum that
ensures order. All that we need to care about is meeting the given
minimums.

> 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.

Take a look at how this has been done in ai/aicity.c for general effects
evaluation in the AI. Basically, calling the city.c functions ensures that
tile based effects are counted, then we multiply the results by any other
effects that exist.

Doing trade efficiently is more difficult. In aicity.c, we call
distribute() to ensure our picture of the result is correct. This may be
too expensive to do after adding each tile, so a faster approximation
might be needed. I have not though about this carefully. Good question.

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

The algorithm does not care about surplus. It only cares about minimum
production and weights. The calling code checks what our upkeep is before
entering the algorithm, and passes minimums that are relative to upkeep.

> > 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.

We try to meet the targets as best as we can.

> > 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 thealgorithm you just outlined.

I will look at it.

  - Per