Bernd Jendrissek <> writes:

> On Mon, May 24, 2010 at 6:15 AM, Goswin von Brederlow <> 
> wrote:
>> I would also like the AI to run as seperate client (that way it can't
>> use privileged information from the server at all) or at least seperate
>> thread. In large maps the AI takes a majority of the time and nowadays
>> multi-core systems are more and more common. Freeciv would run 4 times
>> as fast here with the AIs spread over 4 cores.
> Just for the record, I'm making a bit of progress again on my
> client-side AI experiment.  I'm back to sending settlers off to found
> cities, this time in a less arbitrary and hardcoded way.  I'm somewhat
> surprised by how well it picks out city sites, given the crudeness of
> its calculation.  I'd be delighted to share patches with anyone who's
> curious, but this is really just a hacking-for-fun effort: expect no
> academic papers on it.


> I think I've chatted to you about some stuff that flew right over my
> head, some stuff about Voronoi diagrams and convex hulls.  Frankly, I
> don't understand any of it!  I like your proposal for a "wear"
> algorithm (read: I can at least understand how to implement that).

Well, a Voronoi diagramm is quite simple. For every city associate every
tile with the city nearest to it. Those tiles that have multiple nearest
cities form the lines in the Voronoi diagramm.

But you probably mean a Delaunay-Triangulation, which you can create
from a Voronoi diagramm. A triangulation means you cover the whole map
with triangles with the cities in the corners so that there are no
gaps or overlaps. The special property of a Delaunay-Triangulation is
that the inner angles of the triangles are maximised. So no thin wedges.

You could build roads along the edges of such a triangulation. That
probably gives you a good way to go from any city A to any city B by
road wich is no more than twice (pulled completly out of the air but
there is probably such a limit. Just a feeling) as long as the direct
way. And that with probably a minimum amount of road building.

But I'm wondering if that is really such a good way to build roads. The
map resolution is too small and going diagonal costs the same as
straight. The shortest path between two cities is not a line. It is a
series of left, right, up, down and across steps. And in no way is there
just ONE shortest path.

Maybe the following is more usefull and still simple to understand.
Every tile gets a "want road" count. Each time a unit wants to go from A
to B it finds shortest paths imagining there were roads everywhere. It
adds up max(0, limit - "want road"), call it penalty, for each such tile
that doesn't have roads and picks the shortest path with least penalty
(or possibly all such paths). Then along the path each "want road" count
is increased (increased by a fraction if there are multiple paths).
Building road then becomes a matter of finding tiles with high "want
road" count.

As you can see the algorithm has a feedback loop. Tiles that other units
would have used are prefered. My hope is that thereby paths would share
tiles resulting in less roads being needed. But only when it doesn't
delay the journey.

> The one thing that may (or may not, I'm not familiar with the current
> AI code) be new is that my struct strategy understands the time value
> of money.  Founding a mediocre city in 2 turns is, in some cases,
> better than founding a good one in 20.  Also, struct strategy knows
> about purposes and dependencies: it has a way of encoding that to move
> a (nonexistent) unit, you have to build it first.  Intuitively, both
> these features feel very "right".  Time will tell if they prove to be
> a lasting asset.

That is highly dependend on the level of your civilization. At the start
you want to build many small cities near each other. As time goes on you
want to have large cities with enough room inbetween. But if you don't
build cities where migration will eat them up anyway then you already do

But there is another factor. At the start you have to build where a
starting city will do great. As time goes on you learn how to transform
terrain and have the workforce to do so. At that point city placement
becomes more and more about space. Who cares if there is a desert around
the town? You just change it. At that point you have to calculate what
the city can become andhow much it is going to cost to transform the
tiles for it.

It is also highly likely that space becomes limited by either ocean or
enemies. At what point is it better not to build a city somewhere
because it would just limit the surrounding cities? Or do we build a
city in a bad spot so it can migrate into another and help it grow
beyond 8? Keeping a settler around costs every turn. Sometimes it is
better to waste it than to keep it.

> I'm not sure if the AI really needs long-range strategy.  At the
> moment everything seems okay with a stateless model, where each new
> turn starts a fresh cycle of planning.  In a sense the long-range
> state is already encoded in the consequences of choices made in the
> previous turn: another X shields have made it even cheaper to continue
> building a settler, so the algorithm doesn't "forget" that it had
> decided many turns ago to build another settler in order to build
> another city.  For coordinated attack, I can easily imagine reversing
> this opinion.

War costs money and involves risks. So one turn you move your units out
of the city and the next you see the city as purely defended and causing
unhappyness and move the units back. That easily goes into ping-pong.

But besides that deciding what to do with a unit is a costly operation.
Maybe not for one unit but civilizations grow. There are more and more
units, more and more tiles to consider and so on. It takes longer and
longer to decide what to do and you have to do it more and more
often. If you have a unit that want to go 5 rounds in one direction and
you only compute that once then it is 5 times faster than doing it every

And strategy is also about coordinating multiple units. 20 units can
decide that they should attack a city. A few take 3 turns to go there, a
few 4, a few 5 and some even 6 turns. As each wave comes it attacks the
city and wounds the defenders but by the next turn they have healed
again. If the units delay their moves so they all arrive after 6 turns
they can actually kill a defener. The AI should also see that the last
attack with 10 units wasn't enough, so bring 20 next time. Then 40, then
80. Then try attacking some weaker enemy. :)

> One thing that worries me a bit is that the client/server protocol is
> somewhat hostile to client-side AI implementations: they're almost
> forced to solve the hard problem of computer vision.  Some things
> would have been a lot easier if the protocol allowed for some sort of
> cookie to be attached to some notion of "transaction".  But so far
> that isn't a major problem; it will be ifwhen I start adding military
> action.
> Regards

You mean saving arbitrary client data on the server? It should be
possible to save extra data with tiles, units, cities and globally so
that reconnecting or saving a game does not loos the AIs internal state.
The same goes for normal clients. Things like the city governer should
be stored in a generic way. Or I would like to plant little flags on my
map saying for example: "Build city here". Purely for my human benefit.


Freeciv-dev mailing list

Reply via email to