Re: [Freeciv-Dev] AI Documentation Tips
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
Re: [Freeciv-Dev] AI Documentation Tips
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 corridors. 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
Re: [Freeciv-Dev] AI Documentation Tips
On 25 May 2010 17:29, Bernd Jendrissek bernd.jendris...@gmail.com wrote: 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. CMA saves settings for each city. Player attribute packets are used for this (saving arbitrary client data). See doc/README.attributes. For a long time attributes are considered overkill, and there has been plans to remove them completely. Only because nobody has found time to actually remove them, have they survived. If you *do* need them, be sure to make that known by everyone who might otherwise remove them. I have never thought of endianness issue, but now you mention it... network code handles attributes as byte arrays, so yes, endianness issues of 16, 32, and 64 bit values must be handled in such a code part that knows what attribute block actually contains. - ML ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
Re: [Freeciv-Dev] AI Documentation Tips
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. 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). 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. 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. 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 ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] AI Documentation Tips
Hello, I am interested in working on FreeCiv AI, and would like to know if there is any documentation or begin reading this doc to help me. It's my first contact with the freeciv code, so maybe I should start from something more general than the AI itself. I have already downloaded the source code (altough not compiled it yet) and read these wiki articles: http://freeciv.wikia.com/wiki/AI_Documentation http://freeciv.wikia.com/wiki/AI_Plans I'm a brazilian civ fanatic (but no relation with civfanatics.com) and actually studying in a Master in Computer Science course. I have some ideas that may improve freecivs' AI global decisions, more specifically what each city will build in a turn. But first I would like to understand better how it is done today, so I can evaluate if my idea makes sense or not. If the results are good I plan to use them on my final work and, of course, make it part of the main freeciv code (if it is good to the project too). Thanks for any help Israel ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
Re: [Freeciv-Dev] AI Documentation Tips
Israel israel_...@yahoo.com.br writes: Hello, I am interested in working on FreeCiv AI, and would like to know if there is any documentation or begin reading this doc to help me. It's my first contact with the freeciv code, so maybe I should start from something more general than the AI itself. I have already downloaded the source code (altough not compiled it yet) and read these wiki articles: http://freeciv.wikia.com/wiki/AI_Documentation http://freeciv.wikia.com/wiki/AI_Plans I'm a brazilian civ fanatic (but no relation with civfanatics.com) and actually studying in a Master in Computer Science course. I have some ideas that may improve freecivs' AI global decisions, more specifically what each city will build in a turn. But first I would like to understand better how it is done today, so I can evaluate if my idea makes sense or not. If the results are good I plan to use them on my final work and, of course, make it part of the main freeciv code (if it is good to the project too). Thanks for any help Israel Personally I think it would be a good idea to scrap the AI and start again. The code has so much bitrot in it and the rest of freeciv has changed so much that bringing it up to date might just be more work. 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. An argument for seperate AI clients would also be that it makes developing the AI more fun. You can start your game and play it a bit and when you notice something off you kill the AI, fix the issue and restart the AI all without stopping the game. Or when the AI crashes the game continous. Or you can easily play different versions of the AI against each other. As to what is wrong with the AI here are a few things: - road/rail building Road/raid is build by looking at a tile and its neighbours. Building a road/rail when two neighbours have one connects them so it gives that a big bonus. Apart from that it looks where roads would be beneficial to a city. More or less. Here one could do 3 thinks to improve this: 1) plan to connect 2 cities with a road/rail, find a good route for the road/rail and then send worker to the affected tiles. Also consider road/rails to future cities. 2) keep track of where units move. Tiles that units cross a lot need road/rail first. 3) If you are a worker and you are on a tile without road/rail then build one before doing whatever you were doing. - Explore near your land Explorers move in a way that discovers the most hidden tiles. But what use it discovering a hidden tile at the other end of the earth if there is one right next to your city? The score for tiles should be weight by the distance from the border. Also, with fog of war, the time since a tile was visible last should be considered. Have the exporers revisit tiles to see if maybe someone moved in. In effect, after an initial time of discovering hidden tiles, the explorers should become a border patrol. - Pick a job and stick with it Often you see units move towards A and the next turn they all move back again. That easily repeats. That is just a collosal waste of time. If you decide to attack with an unit then stick with it for a while. Rember that you were going to attack something across turns. - Pick a target and coordinate attacks This would massively improve the AI, possible to the point where it becomes anoyingly hard to beat. Currently afaik each unit on its own decides wether to atack something and if so then what. Instead it should find something to attack and then gather a force by finding idle units near it. If a sufficient force is ready then units should be moved so they all end up attacking the target at the same turn with a full move left. Since stacking units too deep is dangerous they could also come in waves. And don't forget to put a good defensive unit in each stack that won't attak (so it keeps up its strength). Building a road/rail towards the target can also help greatly. MfG Goswin ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
