The Great Apple
Big Cheese
Actually, just going there would be best as I can't sort it out unless you do what it says there...Lord Olleus said:
The Civilization IV AI mod project
- Thread starter Brain
- Start date
The Great Apple
Big Cheese
It stands for "Comminity Core Project". Basically the idea is that we use the SDK to mod the game to quite specific targets with the aim of making the game more moddable, allow more gameplay and interface options, and improving the AI... as well as killing bugs, and trying to improve the performance.
Most of the progress so far has gone towards bug stomping and modding functions.
Most of the progress so far has gone towards bug stomping and modding functions.
Zombie69
Emperor
- Joined
- Nov 22, 2005
- Messages
- 1,902
Well, i have zero interest in making the game more moddable (since i hate mods to begin with) and allowing more gameplay and interface options (since i like games to be as standard as possible), but if there's anything happening regarding the AI, i wouldn't mind contributing. I'll check it out after the weekend as i'm pretty busy right now.
The Great Apple
Big Cheese
At the moment I don't think anybody has actually done anything to change the AI. I'm planning on having a fairly good attack at the city AI when I return from university in a few weeks, and there has been talk of changing the way the AI decides which action a particular unit does.
Same here, I'm not interested in modding the game, but I surely am interested in upgrading the AI. I read some different opinions about upgrading it throughout the forum, but they were all talking about setting different modes. Wouldn't it be possible to create a genetic algorithm for Civ IV?
The Great Apple
Big Cheese
I don't have much experience with genetic algorithms, but I have poked around a bit with the AI, and I think I could program one. However, I have no idea at the sort of timescale it would have to run for to produce meaningful results.
A complete AI vs AI game takes about 10 minutes to run through (all settings stanard). I'd guees that there are perhaps 1000-1500 linear variables in the code for the AI, which would be the best ones for the tweak factor. Anybody any idea of the timescale of such a problem?
It seems to me that an AI vs AI games, while not ideal, would probably be sufficeint in calculating these factors. We could, given enough players willing to help, run the same sort of algorithm for Human vs AI games, with the results being sent off by the user to a database, where they would be compiled together, filtered, and be used to make the next batch, but the timescales involved for this would be far greater than for just AI vs AI games.
A complete AI vs AI game takes about 10 minutes to run through (all settings stanard). I'd guees that there are perhaps 1000-1500 linear variables in the code for the AI, which would be the best ones for the tweak factor. Anybody any idea of the timescale of such a problem?
It seems to me that an AI vs AI games, while not ideal, would probably be sufficeint in calculating these factors. We could, given enough players willing to help, run the same sort of algorithm for Human vs AI games, with the results being sent off by the user to a database, where they would be compiled together, filtered, and be used to make the next batch, but the timescales involved for this would be far greater than for just AI vs AI games.
Fast explenation of genetic programming:
With a genetic algorithm, you don't have to program the AI. You need to program a random-AI-generator. The only problem is that the complexity will go through the roof (most of the time such algorithms are used to <a href="http://www.erachampion.com/ai/"> evolve virtual robots</a> or <a href="http://algoval.essex.ac.uk/rep/games/CigPacReady.pdf"> learn a pc to play pacman </a>).
For example, with the robots they start with a box and grow short random testikels on it (they create hundreds of unique robots). Then the robots have to try to move. The most succesfull ones survive and are used to create the next generation of robots, the robots are mixed together and create mutated (evolved) babies. Again the most succesfull ones are paired together,...
The outcome are robots who can walk a pretty distance on the most bizarre ways.
Now in Civ IV it's a bit harsh. You need to summarize everything that defines the AI in a simple decision-tree. It's difficult, but not impossible.
With a genetic algorithm, you don't have to program the AI. You need to program a random-AI-generator. The only problem is that the complexity will go through the roof (most of the time such algorithms are used to <a href="http://www.erachampion.com/ai/"> evolve virtual robots</a> or <a href="http://algoval.essex.ac.uk/rep/games/CigPacReady.pdf"> learn a pc to play pacman </a>).
For example, with the robots they start with a box and grow short random testikels on it (they create hundreds of unique robots). Then the robots have to try to move. The most succesfull ones survive and are used to create the next generation of robots, the robots are mixed together and create mutated (evolved) babies. Again the most succesfull ones are paired together,...
The outcome are robots who can walk a pretty distance on the most bizarre ways.
Now in Civ IV it's a bit harsh. You need to summarize everything that defines the AI in a simple decision-tree. It's difficult, but not impossible.
The Great Apple
Big Cheese
Yeah - I know what I genetic algorithm is (that's not to say I think I could code a good one - I could code one, but it might not be good!), I just have no idea how much time it would take to actually produce any results for the Civ AI.
Using genetic algorithms is not at all straightforward for a game like Civ that has many different components of decision-making (diplomacy, spending, unit movement, etc.). I don't think genetic algorithms will be of much use except possibly for certain limited problems (unit movement). More importantly, focusing on the type of algorithm completely misses the point.
Part of the problem is that GAs search in hypothesis space. You perform "crossover" & "mutation" operators on solutions H(1)...H(n), with the hidden assumption that these hypothetical plans have components, which when recombined & altered via mutation, can be composed into higher order plans, and that randomly combining arbitrary components will yield a useable plan. Also, you have then the problem of computing fitness function F(i) for each population member H(i). How do you do that? How do you know that a plan H(i) ("make peace with Alex, war on Monty") is better than plan H(j) ("make peace with Monty, war on Alex")? You have to convert these plans into a scalar quantity F that lets you know which solution is more "fit" and therefore has more representation in the next iteration of the population of solutions H. The problem isn't coding the GA--that's trivial to do in C++ or Lisp. The far harder part is computing fitness, and that in turn will depend on knowledge representation.
If you do enough work in AI, you'll discover that one of the key things is knowledge representation--how to represent AI plans as objects that can be stored & analyzed. After that, deciding a scheme to search the space of AI plans becomes much easier.
I suppose, you could take the several hundred or thousand variables in C++ from the AI module, build a GA engine around it, and start off by saying, "well let's concatenate the variables into linear strings H, generate a population of them, & begin performing crossover & mutation operations on it." Then you take those "plans" and somehow magically derive fitness values without actually simulating gameplay (because that would basically be cheating by running a saved game repeatedly into the future to try different strategies). I think you can see that this would be difficult.
Part of the problem is that GAs search in hypothesis space. You perform "crossover" & "mutation" operators on solutions H(1)...H(n), with the hidden assumption that these hypothetical plans have components, which when recombined & altered via mutation, can be composed into higher order plans, and that randomly combining arbitrary components will yield a useable plan. Also, you have then the problem of computing fitness function F(i) for each population member H(i). How do you do that? How do you know that a plan H(i) ("make peace with Alex, war on Monty") is better than plan H(j) ("make peace with Monty, war on Alex")? You have to convert these plans into a scalar quantity F that lets you know which solution is more "fit" and therefore has more representation in the next iteration of the population of solutions H. The problem isn't coding the GA--that's trivial to do in C++ or Lisp. The far harder part is computing fitness, and that in turn will depend on knowledge representation.
If you do enough work in AI, you'll discover that one of the key things is knowledge representation--how to represent AI plans as objects that can be stored & analyzed. After that, deciding a scheme to search the space of AI plans becomes much easier.
I suppose, you could take the several hundred or thousand variables in C++ from the AI module, build a GA engine around it, and start off by saying, "well let's concatenate the variables into linear strings H, generate a population of them, & begin performing crossover & mutation operations on it." Then you take those "plans" and somehow magically derive fitness values without actually simulating gameplay (because that would basically be cheating by running a saved game repeatedly into the future to try different strategies). I think you can see that this would be difficult.
The Great Apple
Big Cheese
Actually, my fitness function would be based on the end result of the game - a combination of the score, power, whether the AI actually won or not, and how well it played to the AI flavour values (otherwise we might end up with boring AIs who are all the same). Remember that I'm talking about AI vs AI games here - these can be conducted without user intervention in a matter of minutes.
The sort of numbers I'm suggesting on changing would be the ones that determine how much the AI values a tech which gives a free engineer, or the likelyhood of building a granary... or the likelyhood of declaring war given relative strengths.
I agree that analysing individual events would be next to impossible, as, as you said, it's very hard to say which event is better identifying and improving the factors which made that decision bad, if it was.
Analysing the whole game and leading it back to changes in these factors is problematic as well though - who is to say that the reason a particular AI did so well is because it built more graneries? Would you crossover & mutate after each game, once every 10, or maybe even once every 100? Personally, I'm not sure which would be more effective. One would save time by running far less tests per branch, the other would ensure that the fitness function is valid, making the results at each brach closer to the optimum.
Another trouble with this is that you are optimising the AI to defeat other AIs. Now, I think this should be alright, however it could all go wrong if the variables that cause the AIs to declare war on each other sink quite low, hence causing the amount of units they build to sink, and causing the AI to be hideously weak in wars against humans. It's something which is very hard to predict without trying it.
The sort of numbers I'm suggesting on changing would be the ones that determine how much the AI values a tech which gives a free engineer, or the likelyhood of building a granary... or the likelyhood of declaring war given relative strengths.
I agree that analysing individual events would be next to impossible, as, as you said, it's very hard to say which event is better identifying and improving the factors which made that decision bad, if it was.
Analysing the whole game and leading it back to changes in these factors is problematic as well though - who is to say that the reason a particular AI did so well is because it built more graneries? Would you crossover & mutate after each game, once every 10, or maybe even once every 100? Personally, I'm not sure which would be more effective. One would save time by running far less tests per branch, the other would ensure that the fitness function is valid, making the results at each brach closer to the optimum.
Another trouble with this is that you are optimising the AI to defeat other AIs. Now, I think this should be alright, however it could all go wrong if the variables that cause the AIs to declare war on each other sink quite low, hence causing the amount of units they build to sink, and causing the AI to be hideously weak in wars against humans. It's something which is very hard to predict without trying it.
Sorry, I didn't realize you were talking about AI vs AI games as the substrate, with population members being AI plans that do not change for the scope of the entire game. That makes the problem more tractable in some ways....and as you point out very interesting and hard in other ways. Just deciding the representation of the "gene" structure of the plans would be interesting. And you're definitely right, many variables (map size? # of opponents?) could have far-reaching effects. You could certainly develop optimized AI plans that are unduly adapted to just the parameters of the games you ran to evaluate fitness, even ignoring the whole can-it-beat-the-human question.
Similar threads
