[freeciv-ai] Re: Settler fixes [Was: A better AI Eval buildings 1.1]

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

On Wed, 15 May 2002, Raimar Falke wrote:
> *looking at server/settlers.c to see what minimap really means*
> Uhh. As usual the server AI mixes things. The minimap is used as a
> fast test to see if a city is too near to another city and it acts as
> a cache for the return values of city_desirability.

Almost. The cached value is a calculation based on all the tiles within
the new potential citymap area. So each tile has a cached value which is
based on the goodness of all tiles within citymap radius. When a city is
built, tiles around it are reserved by setting them to a negative value.
So calculations for city desirability will ignore them and not count tiles
twice (for both city A and city B).

However, it is fundamentally flawed, since it never reevaluates its
minimap. That means once a value is cached, it ignores the fact that it
might build cities all around it. The minimap code works as intended only
because of the order in which spots are found is sound (find a spot,
reserve it, build a city, find a new spot, reserve it... etc expanding).
But if you start an AI game with "set settler 10" you will notice that it
settles totally different with these settlers than it does normally. This
is because minimap really is fundamentally flawed but it only shows in
situations like this. And you know what is worst? The city sprawl that
results from when minimap is _not_ working as intended (ie when you use
"set settler 10") is the most efficient, since it uses available real
estate much better.

My suggested minimap replacement (citymap) does this slightly different.
Instead it allows you to reserve individual tiles. It models how I think
when I found cities: I see a spot, then I "reserve" a few tiles (esp one
good food tile) around it in my head, and allow new settlers to grab the
remaining tiles, if another good spot is nearby. This allows cities to
"overlap", which is important for good city sprawl in the default ruleset.

I am not sure how to optimally calculate how many tiles to reserve. The AI
should try to figure out what kind of city it wants to build at a spot (ie
a city for churning out settlers, a science city, a wonder building city,
just a generic big city, or something).

> It isn't reset
> which is IMHO a bug because a different government for example should
> clear the cache.

Probably. city_desirability assumes Democracy, which is a bug, since the
AI does not get to Democracy. But city_desirability is forward-looking, so
that it assumes Harbour (and incredibly, Offshore), and it is perfectly in
line with this to assume eg Republic, when evaluating tiles. Whether such
forward-looking is the right way to do it, I am not sure. (Probably not.)
It will require quite a bit of computing to do in a generic way.

> > Can you please comment on the interface I posted, and tell me if you can
> > use such a minimap for CMA?
>
> You mean SMA?!.

Ugh. Yes.

> No. Look I already have a
>   +static int get_distance_to_nearest_city(struct player *pplayer, int x, int 
> y)
> which may be slow but if this turns out to be a problem I would want a
> generic caching function for just this problem.

See above. minimap does more than just ensure that cities are distant
enough from each other. citymap as I suggested does even more in turn,
since it allows you to reserve individual tiles for your city's expansion,
and ensures that you don't calculate in tiles that are in use by workers.

> The other thing that minimap does it to cache the return value of
> city_desirability. Unfortunately the return value of
> calc_build_city_yield isn't just an int. calc_build_city_yield fills
> parts of such a
>
> +struct sma_action_assessment {
> +  short int valid;
> +  struct sma_external_action action;
> +  struct ga_path path;
> +  short int turns_for_goto;
> +  short int needs_extra_recharge_turn;
> +  short int turns_for_preparation;
> +  short int turns_to_carry_out_action;
> +  short int turns_where_action_is_in_effect;
> +  short int final_yields[NUM_YIELDS];
> +  int fitness;
> +  struct sma_city_tiles city_tiles;
> +};

This looks very good. But in order to compare one spot with other city
spots, don't you need to reduce it to a single value somehow, anyway?

> struct. Especially final_yields and city_tiles which is
>
> +struct sma_city_tiles {
> +    int entries_used;
> +    struct {
> +      short int x, y;
> +    } entries[CITY_MAP_SIZE * CITY_MAP_SIZE];
> +};
>
> So I can later really reserve these tiles if the city build turns out
> to be the best action.

I don't understand the above. I probably need to see it in context of the
rest of the code. How many tiles do you plan on reserving? (In my own
games I usually only reserve one good food tile in addition to city
center.)

> > Of course. But what is the algorithm you suggest for amortizing the value
> > of more distant city spots? This is impossible to do comprehensively
> > (since you must calculate what you do in future turns to know how much a
> > delay early in the game will hurt you).
> >
> > Let me suggest an approximation: Take the loss of prod/tax/science from
> > the city you could have settled closer, multiply it by (the extra number
> > of moves to get to the more distant spot + 10), if this is > than the
> > prod/tax/science from the more distant city multiplied by 10, then
> > travelling further is beneficial. 10 (or whatever number is sensible, 10
> > is just a guess) is an arbitrary number, but without any arbitrary and
> > hardcoded numbers, you will create hell for the CPU and totally Syela
> > code.
>
> *taking a step back* We are discussing ways to speed things up by
> reducing the amount of tiles we consider (under the assupmtion that
> the path finding is expensive and should be avoided).

No... I'm discussing how to properly punish city spots for being distant,
so that settlers don't travel unnecessary long distances and waste lots of
valuable time to get the "best spot".

> AFAIK the current AI does this by a hardcoded move cost limit. In your
> way we need the remote city spot to carry out a caclulation. This just
> doesn't solve the problem. There is another problem. You may want to
> avoid to call city_desirability for the remove spot. But I don't see
> how you solve this.

Right. I don't either. Bad suggestion.

> It is a model. One model can be more accurate than another. One
> problem is that the exponential model needs an extra parameter and I
> still haven't seen any work to calculate the best value for this. And
> you know that a model which may be more accurate then another can be
> more bogus than another when it is supplied with incorrect parameters.

Very good point. I need to think about this some more.

Yours,
Per

"As Israeli forces pursued militants, civilians
continued getting in the way and dying as a
result." -- New York Times, April 21