[Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation

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

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=12734 >

On Wed, 6 Apr 2005, Benoit Hudson wrote:
> Interesting.26% is pretty large; I wonder if we can trade time for
> quality a bit better; say, instead of considering single tiles, consider
> pairs or n-tuples.

Thanks a lot for the helpful comments. I will make a new patch soonish to
make things more clear.

> > +static void citizen_base_mood(struct player *pplayer, int specialists,
> >                           int *happy, int *content,
> > -                       int *unhappy, int *angry)
> > +                       int *unhappy, int *angry, int size)
>
> I'd list the arguments as pplayer, size, specialists, then a struct
> {happy,content,unhappy,angry} rather than four int*.

I'll separate out this some other stuff as a patch on its own; however, I
am just following the way the other functions have been changed here. So
if you want this to be a struct, it is a bigger effort that will change
several functions in city.c. I'm not doing this now.

> > +/**************************************************************************
> > +This function implements a greedy citizen allocation algorithm. It
> > +is meant to be ultrafast, somewhat but not completely optimal.
>
> "good but not optimal" ("somewhat optimal" gives me goosebumps)

True ;)

> > +We employ a number of tricks to make this work. First we try to delay
> > +the necessary picks, so that perhaps picks by desire that are done
> > +first may solve our needs by accident. Second, if we cannot find all
> > +the requirements for a placement, we try to swap out requirements
> > +for this placement with that of the next (push_retry). This solves
> > +a number of 'deadlock'-like situations. Third, we drop requirements
> > +as we detect situations we cannot handle, starting with gold, then
> > +either food or luxuries, and lastly just dropping all requirements.
>
> What are the requirements for a placement?What are "necessary picks"
> and "picks by desire" ?

Necessary picks are guided by requirements. Picks by desire are only
guided by factor multipliers (cmp->factors).

> The idea of soft failing is something I've been wondering how to
> implement in the CM.If you can, then it'd be better to have the
> constraints not go from hard to none, but instead to have some penalty
> (probably quadratic, maybe weighted) as you start violating them.So
> it's better to miss both food and gold by 1 than to miss food by 2.

I thought about passing in a prioritized list of outputs for soft failing,
but I tried to make it simple instead.

> > +It is crucial to note that we do _not_ attempt to find a solution
> > +where we end up with negative shields. The human user is expected
> > +to solve these himself, and by throwing the city into disorder, this
> > +problem is made patently obvious. Similarly for the AI, its emergency
> > +management code is meant to solve situations like this, which can
> > +try to solve it by rehoming units, for example.
>
> This should be part of the API.

I found it hard to use the existing API and make the code lean and fast. I
was trying hard to avoid the 'I need to be called multiple times with
various parameters to work' mess of CM.

> Note: "throwing the city into disorder" is often not what's going to
> happen -- there once were comments to that effect in the
> auto_arrange_workers code too, but it's inaccurate.You can have a city
> that is unable to manage its units, for instance when you switch
> governments, but that is easily able to keep everyone happy.Disorder
> isn't the last resort; it's often impossible, in fact.

Ah, right. However, in my experience this is not common, at least in
default. Usually sudden causes for 'no longer has shields enough to
upkeep' is due to having to use more citizens for elvises or food.

> > +There are some problems with this approach, however. First, we treat
> > +the secondary outputs (gold, science, luxuries) as a linear
> > +accumulation, which they are not. Second, our calculation of city
> > +effects on outputs is done on the gradual accumulation of outputs,
> > +which is also not precise. Third, in some pathological cases,
> > +especially where we can only get a stable regime by _not_ picking
> > +the mest desirable tiles first, get us in trouble we cannot solve.
>
> G/S/L are treated as being linear in what?

We run distribute() on each tile/specialist, instead of on the total sum.
This is not correct, but I do not see a way around that.

> What do you mean by "accumulation"?

We multiply the gradually accumulated results (in sum[]) with the city's
output-multiplier effects; for the early picks, this will be rather off
(by rounding) but for the later picks this should be more correct.

> What does "stable regime" mean?

City order ;)

> > +/* We would rather have food than luxuries; this is not always true,
> > + * we may want to starve the city rather than let it continue to riot.
> > + * This does not hold true for shields, though, since we are no more
> > + * likely to be able to carry the upkeep if we shrink. */
> > +bool food_first = FALSE; /* DEBUG ... set to TRUE for normal cmp */
>
> I don't understand the meaning of food_first from either the comment or
> the variable name.

Whether we should soft fail for food or luxuries first. I don't know how
to improve the comments or variable name here. Probably should be removed
in favour of a better API, though.

> > +/* If we fail to satisfy all our minimums, we try to drop O_GOLD and
> > + * try again. Then we try to drop either O_FOOD or O_TRADE, depending
> > + * on above variable, and try again. If that fails, we give up. At
> > + * repeated == 0, we no longer look at minimums. */
> > +int repeated = 3;
>
> To implement this, I'd be happier with:
>   bool ignore_min[O_COUNT];
>   int  ignore_index = 0;
> and a function to map ignore_index into a ignore_min vector; eventually,
> ignore_min will be all false.

Perhaps. I'll look into it.

> > +if (cmp->require_happy) {
> > +  /* Find out how much extra luxuries we will need to make enough
> > +   * citizens happy that we can celebrate. */
> > +  GCALOG("%s: wants to celebrate, needs %d luxuries extra",
> > +         pcity->name, ((pcity->size + 1) / 2) * HAPPY_COST);
> > +  minimum_stats[O_LUXURY] += ((pcity->size + 1) / 2) * HAPPY_COST;
>
> Will this work?You need to get rid of all unhappy citizens too, which
> is often the hard part.

Notice that if we try to celebrate, we will also assume that we will make
citizens content first in the code above this. So we have already done
that hard part. Notice the += too.

> > +/* Distribute workload among citizens. We try to put off most of the
> > + * work as late as possible (for last citizens considered) in the hope
> > + * that earlier labour will give us what we want anyway. */
> > +memset(requirements, 0, sizeof(requirements));
> > +output_type_iterate(o) {
> > +  int load = minimum_stats[o];
> > +
> > +  while (load > 0) {
> > +    for (i = pcity->size - 1; i >= 0 && load > 0; i--) {
> > +      requirements[o][i]++;
> > +      load--;
> > +    }
>
> I'm betting this means you never end up using gold mines: your food
> usage is 2n, so every requirements[O_FOOD][i] == 2.Where does my logic
> break down?

You are correct in that the first picks are nearly always food, due to the
logic you describe. However, since there are usually some quite good food
picks to be had (and food is rated quite high in cmp->factors,
incidentially...), we satisfy our food requirements early, and our later
picks can then get the mines.

(What if food isn't rated high in cmp->factors? We have a problem. But
this is a managable problem, which can be in the function's description.)

> Seems like you should be able to use the cm_tile_type infrastructure
> here to speed things up further, at the cost of some pre-processing.At
> the moment, the pre-processing is an insignificant part of CM so it's
> not written for speed; if it becomes a bottleneck for this code, it
> should be trivial to speed up building the lattice by a factor of 2 and
> probably even 10.

I'll look at it.

> > +              && sums[o] * pcity->bonus[o] / 100 < minimum_stats[o]
>
> This calculation comes up several times; should be pre-computed or
> turned into a function.

We can't precompute it - sums[o] changes for every tile.

> > +    /* Now we may or may not have a best candidate. If we don't, see
> > +     * if we can relax the requirements a bit and try again. Do not
> > +     * push twice in a row, though. */
> > +    if (best == -1) {
> > +      if (push_retry == 0 && i < pcity->size - 1) {
> > +        /* Try to push all other requirements ahead of us if we can,
> > +         * this solves some deadlock situations. We push our req from
> > +         * the next requirements level back, though, to avoid it next
> > +         * time. */
> > +        enum output_type chosen_req = O_LAST;
> > +        output_type_iterate(o) {
> > +          if (requirements[o][i] > 0
> > +              && sums[o] * pcity->bonus[o] / 100 < minimum_stats[o]
> > +              && chosen_req == O_LAST) {
> > +            chosen_req = o;
> > +            requirements[o][i] += requirements[o][i + 1];
> > +            requirements[o][i + 1] = 0;
> > +          } else if (requirements[o][i] > 0) {
> > +            requirements[o][i + 1] += requirements[o][i];
> > +          requirements[o][i] = 0;
> > +          }
>
> I don't think I understand the effect of this: we're finding that there
> is no tile that satisfies the distributed requirements, so we're putting
> off every requirement except the ones that we haven't satisfied?

No, we are choosing one requirement (by random) and putting off all the
others until next citizen pick. Then we remove the chosen requirement from
the next citizen pick so that we don't end up with the same problem there.

> If we've satisfied a requirement, though, shouldn't we immediately have
> its requirements from then on be zero?

Ideally, yeah. But here it makes no difference - we always check directly
whether this is the case (against sums[]).

> In fact, this raises a bigger question: why is it that requirements
> appears not to

?

> > +      } else if (repeated == 1) {
> > +        /* Set repeated to zero, this shorts out any attempt to fulfill
> > +         * our obligations. */
>
> Comment is wrong: we don't set repeated to zero here.

We will, a couple of lines down ;)

  - Per