On Tue, May 25, 2010 at 8:00 AM, Goswin von Brederlow <goswin-...@web.de> wrote:
> Bernd Jendrissek <bernd.jendris...@gmail.com> writes:
>> On Mon, May 24, 2010 at 6:15 AM, Goswin von Brederlow <goswin-...@web.de> 
>> 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.
> Url?

I'll try to find a place to host it.  PING: does anyone have an
up-to-date git mirror of the freeciv repository?  I don't want to just
tell repo.or.cz to suck bits from svn.gna.org; I come from a land of
scarce bandwidth where it's rude to do that without asking :)

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

Thank you for the clear summary - now I actually get what it's
supposed to be!  Yes, it's the Delaunay triangulation that I remember
being further above my head.

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

I think I'll just ask you to implement the triangulation!

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

Yes, because we don't want otherwise unused roads just waiting for
enemies to use them.

> But I'm wondering if that is really such a good way to build roads. The

I agree it does seem expensive; mentally if not algorithmically.

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

I can easily see my auction model (I forgot to mention that)
determining okayish estimates on the value of building a road that's
shorter by N moves.

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

Once you have a road, the feedback would quickly encourage building
rail there too.  But it might be a bit slower in deciding to build a
road, if it's a mountain range that causes all paths across it to be
equally expensive: you'd end up with a diffuse "want road" spread over
the whole area, instead of concentrated in a smaller number of

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

I think having a decent measure of "prevailing interest rate" would
automagically take care of this.  A big civilization would find it
hard to maintain a high interest rate: their capital investment is
high, but opportunities for further expansion are few.

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

Yes, this tension between the here-and-now (where terrain matters) and
what-it-could-be (where only the specials matter) still puzzles me.
But terraforming will have a time cost, which you can translate into

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

Military activity might need a revisit of the stateless approach I'm
using now, but if there was some incentive to move units out of the
city, then if that incentive still exists the next turn, then spending
another outside the city should be even cheaper this time round
(because you don't have to expend movement points).  One might assert
that oscillations would be only due to incomplete valuation functions
(and I realize this is a hard part of AI), or amplifier instability.

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

I specifically added penalty / bonus clauses to struct strategy to
deal with this, so that a unit would find it very unprofitable to be
at a place at the wrong time.  I would handwave a coordinated attack
with the following strategy decomposition:

STRATEGY_WIN value=inf
  STRATEGY_CONQUER_CITY pcity=London effective_hp=400
    STRATEGY_ATTACK target=London
      STRATEGY_MOVE_UNIT turn=1500AD late_cost=1000000
early_bonus=-1000000 punit=catapult[17]
    STRATEGY_ATTACK target=London
      STRATEGY_MOVE_UNIT turn=1500AD late_cost=1000000
early_bonus=-1000000 punit=catapult[17]
    STRATEGY_MOVE_UNIT turn=1500AD late_cost=1000000
early_bonus=-1000000 punit=musketeers[42]

Indentation denotes dependency, and the negative early_bonus makes it
expensive to arrive early: for settlers, early_bonus would normally be

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

It is possible to save arbitrary data, but I meant arbitrary data
attached to a specific *action*, not a *place*.  It would be
convenient to know that a particular unit-killed message from the
server is somehow related to an earlier attack message from the

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

I think the city governor does store something on the server.  I'm not
sure what exactly.  Unfortunately the data is (or was, or I'm
mistaken) endianness/alignment-sensitive.

I would love to see flags like you describe.  I often forget where I
had decided earlier I wanted to build a good city, but only after I
had done at least some terraforming.

Freeciv-dev mailing list

Reply via email to