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

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

On Wed, Apr 06, 2005 at 04:04:08PM -0700, Per I. Mathisen wrote:
>
> <URL: http://bugs.freeciv.org/Ticket/Display.html?id=12734 >
>
> I was tired of slow AI games, so I decided to handle the root of all evil
> - the city management code. I wrote my own CM from scratch, and stuffed it
> in the bottom of city.c. At approx 300 lines of code, it is not very big.
>
> In a very difficult, very large savegame that I used for reference, CM did
> 26% better in finding optimal solutions according to the scoring test I
> made. The greedy function was, however, 154 times faster.

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.

I wonder how your method does compared to running the current CM code as
an anytime algorithm (it's designed to be easy to do so).  Anytime
algorithms tend to be slower to get a good solution than a hand-coded
greedy search, but you can trade off time and quality quite easily.


I have a *lot* of comments from reading the code carefully enough to
understand it.  I had some trouble understanding the push_retry
mechanism (I'm still not entirely sure about it).


> Index: common/city.c
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/common/city.c,v
> retrieving revision 1.323
> diff -u -r1.323 city.c
> --- common/city.c     3 Apr 2005 20:19:51 -0000       1.323
> +++ common/city.c     6 Apr 2005 22:59:39 -0000
> @@ -1780,33 +1780,30 @@
>  /**************************************************************************
>    Create content, unhappy and angry citizens.
>  **************************************************************************/
> -static void citizen_base_mood(struct city *pcity,
> +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 like this function; it would be useful in the CM code too for much the
same reason.

> +/**************************************************************************
> +  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)

> +  The basic algorithm is as follows: Figure out (through pcity->usage[]
> +  and some luxury magic) what are needs are, and place one city at a

"what *our* needs are" ; "one *tile*"

> +  time, each aiming to produce to its share of what is necessary for
> +  the whole city's needs.
> +
> +  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" ?

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.

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

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.

> +  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?
What do you mean by "accumulation"?
What does "stable regime" mean?

> +void greedy_citizen_arrange(struct city *pcity, const struct cm_parameter 
> *cmp,
> +                            struct cm_result *cmr)

Agree with Jason that this should be in cm.c and should be based on a
new flag (bool greedy, for instance) in the cm_parameter.

> +#define GCALOG(...) if (pcity->debug) { freelog(LOG_NORMAL, __VA_ARGS__); }
> +{
> +  /* 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.

> +  /* 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.

> +  int minimum_stats[O_LAST], i, happy, content, unhappy, angry;
> +  int requirements[O_LAST][pcity->size];
> +  int sums[O_LAST];

I think you want s/O_LAST/O_COUNT
Also, the use of every variable should be indicated: what are
minimum_stats vs. requirements, why is requirements indexed by size,
what's sums?

> +  bool taken[CITY_MAP_SIZE][CITY_MAP_SIZE];

worker_positions?

> +  int rates[3];
> +  const int SCIENCE = 0, TAX = 1, LUXURY = 2;

This happens a lot in the code; presumably this should be generalized
somewhere (this isn't really a comment about your patch).

> +  struct player *pplayer = city_owner(pcity);
> +  int push_retry = 0;

What's push_retry?

> +  int tile_outputs[CITY_MAP_SIZE][CITY_MAP_SIZE][O_LAST];

Isn't this already computed, by the same name, in pcity?

> +  /*** Step one: Find minimums. ***/

Such a comment indicates you need to break up the function (it's a
couple hundred lines long!)

> [...]
> +    /* Find out how much luxuries we need to keep city content.
> +     * This ignores the fact that specialists may be taken from
> +     * unhappy citizens when we no longer have any content ones
> +     * left. We should ideally never get there. */

We get there quite often, especially on large cities and large civs.  It
may not matter.

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


> +  /* 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?

> +  /*** Step two: Try to satisfy minimums. ***/
> +
> +  /* Clear vars */

why not:
    memset(sums, 0, sizeof(sums));
    memset(cmr, 0, sizeof(*cmr));



> +  for (i = 0; i < pcity->size; i++) {
> +    int best = -1, bestx = -1, besty = -1, bestsp = -1;
> +    int best_out[O_LAST]; /* remember output in case we use them */
> +
> +    do {

This is terminated 118 lines lower.  That's... impressive.

> +      city_map_iterate(x, y) {
> +        bool satisfy_reqs = TRUE;

> +        int total = 0;
> +        int temp[O_LAST];
> +        int result[3];

Describe these variables: "tile_fitness" ; "estimated_tile_production" ;
"tile_secondary_stats" or somesuch.

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.

> +      specialist_type_iterate(sp) {
> +        if (city_can_use_specialist(pcity, sp)) {
> +          int total = 0;
> +          bool satisfy_reqs = TRUE;
> +          int temp[O_LAST];
> +          int result[3];
> [...]

You just wrote this same code twice; make a function.

> +      /* 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]

This calculation comes up several times; should be pre-computed or
turned into a function.

> +                && 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?  If
we've satisfied a requirement, though, shouldn't we immediately have its
requirements from then on be zero?

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

> +          } output_type_iterate_end;
> +          push_retry += 2; /* now don't try this next citizen */
> +          GCALOG("%s: pushed other reqs than %s ahead at %d", pcity->name,
> +                 get_output_name(chosen_req), i);
> +        } else if (repeated == 3) {
> +          minimum_stats[O_GOLD] = -1;
> +          GCALOG("%s: relaxed gold req at %d", pcity->name, i);
> +        } else if (repeated == 2) {
> +          if (food_first) {
> +            minimum_stats[O_LUXURY] = -1;
> +            GCALOG("%s: relaxed lux req at %d", pcity->name, i);
> +          } else {
> +            minimum_stats[O_FOOD] = -1;
> +            GCALOG("%s: relaxed food req at %d", pcity->name, i);
> +          }
> +        } 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.

> +struct cm_parameter;
> +struct cm_result;

should go into fc_types, right?

> @@ -86,6 +89,9 @@
>  /* Cost in luxuries to make one citizen happier by one level. */
>  #define HAPPY_COST 2
>
> +/* Cost in food to feed one citizen. */
> +#define FOOD_COST 2
> +

Probably should be ruleset-dependent but making it a #define is a good
start.  I think it shows up in cm.c as well.

> Index: server/cityturn.c
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/server/cityturn.c,v
> @@ -145,7 +146,7 @@
>    Rearrange workers according to a cm_result struct.  The caller must make
>    sure that the result is valid.
>  **************************************************************************/
> -void apply_cmresult_to_city(struct city *pcity, struct cm_result *cmr)
> +void apply_cmresult_to_city(struct city *pcity, const struct cm_result *cmr)

Yes, but seperate patch.

        -- Benoît