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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, May 15, 2002 at 10:21:19AM +0200, Per I. Mathisen wrote:
> 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.

So you ended up with my

+struct tile_reservation_for_city_building {
+  short int unit_id, as_center;
+};

This is attached to each tile. as_center is necessary so that we don't
found a new city too near to another planned one.

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

I also don't have to correct answer. It is the second open question I
still have with the SMA. Ideally it will need a CMA working on the
virtual city. The code currently just searchs for the best tile for a
city of size one and reservs this tile. You have to provide weights
which specify which tile is the best one. You can also specify the
minimal surplus:

+  struct {
+    int minimal_surplus[NUM_YIELDS];
+    int surplus_weights[NUM_YIELDS];
+  } city_building_assessment;

And there is also:

+  struct {
+    /*
+     * Distance of the target position from the nearest city.
+     */
+    int minimal_distance, maximal_distance;
+
+    /*
+     * Minimal defense bonus of the target position.
+     */
+    int minimal_defense_bonus;
+  } city_building_constrains;

Which remove some possible tiles very early.

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

Here I'm more pragmatic: I prefer to use the spot which is now
yielding the best output as compared to a spot which is better if we
have government foo and improvements bar on the tile A, B and C.

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

Since you now have to code take a look at allocate_action,
deallocate_action, is_tile_reserved_for_a_city and
calc_build_city_yield.

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

There is a field fitness which does this.

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

Same here. At least in the current implementation. But you see that
the code will also nicely work with more reserved tiles.

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

This is easy in my linear amortization model:
 turns_where_action_is_in_effect=turns_to_consider (which is MORT) - 
turns_for_preparation
with
 turns_for_preparation = turns_for_goto + needs_extra_recharge_turn

So if turns_where_action_is_in_effect is negative you can discard that action.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "When C++ is your hammer, everything looks like a thumb."
    -- Steven M. Haflich