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 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 this. 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 round. 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. MfG Goswin _______________________________________________ Freeciv-dev mailing list Freecivemail@example.com https://mail.gna.org/listinfo/freeciv-dev