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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, May 15, 2002 at 12:25:44AM +0200, Per I. Mathisen wrote:
> On Tue, 14 May 2002, Raimar Falke wrote:
> > > I don't think that is a good idea. I'd rather make a minimap
> > > implementation in common code. That way the server-side AI can use it,
> > > too. I gave this a few thoughts while cleaning up settlers.c
> >
> > But this would need a lot of extra work (packets, savegame, ...) with
> > no benefit.
> 
> No. The idea is that each AI has its own implementation of the citymap
> (minimap). They do not communicate their citymaps with anyone else. You
> should not put caches in savegames. When you load a game, you can just
> recalculate the citymap. So no new packets.
> 
> (Of course, that means all server-side AIs will share one citymap since
> they have one instance of common/ in common. But it also means this new
> minimap is a mere plugin replacement for the existing minimap.)
> 
> (Yes, this will lead to autogame differences pre and post saving and
> loading a game, but I see this as unavoidable for more advanced AIs,
> unless we save complete state in the savegame, which to me sounds like
> total and unfeasible overkill. We also already have this problem. Eg
> existing minimap is not saved to savegame. Remember, these caches can be
> very big.)

*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. It isn't reset
which is IMHO a bug because a different government for example should
clear the cache.

> > And attributes are invented for this kind of stuff.
> 
> The server does not have attributes. I also want to fix server-side AI.
> 
> > There are two attributes are attached to each tile:
> 
> I'm only talking about a minimap for cities now. I think we can and should
> keep the two separate.

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

You mean SMA?!. 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. 

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;
+};

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.

> > > Why not? Take a desert world. We find our two starting positions, but
> > > nothing more, for a long while. Then we find a crap place. We evaluate it
> > > and store the want value, finding it wanting (pun). Then even later we
> > > find a good place, evaluate it, store and send out a settler.
> >
> > I was refereeing to "Because the cost of travelling across a larger
> > distance than that to settle in a slight better spot is much higher
> > than the benefit.". The problem here is "a larger distance" and
> > "slight better spot". You just can't hardcode these values (as the
> > current AI does) because they depend on the ruleset.
> 
> 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). 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.

> > Linear amortization is on the list of things which have to
> > reconsidered. However it is a very nice and easy model.
> 
> Yes, it is nice, easy, and wrong :-)

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.

> > > Also, how do you solve island-hopping (settling new continents)?
> >
> > I don't. One agent for one purpose. It is the same reason that the CMA
> > don't do multi city optimization.
> 
> Ok. You intend to do this on a higher level, I suppose.

We will see how the remaining open tasks can be divided into agents.

> > It was posted 20 Oct 2001 under the subject "[Patch] Map
> > decoration". You see this patch also needs an update.
> 
> The mail archive keeps giving me 404s on everything I try to read from
> that time period, including the SMA and map decoration patches.
> 
> Raimar, can you resend both to the list, please?

Sure.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Transported to a surreal landscape, a young girl kills the first woman
  she meets and then teams up with three complete strangers to kill again."
    -- TV listing for the Wizard of Oz in the Marin Independent Journal

map_deco2.diff.bz2
Description: BZip2 compressed data