I have been looking at the AI a bit and it seems that, although it is quite good, it lacks cohesion.
This is how I understand the CvUnitAI.cpp to work.

1) A unit is allocated 'tasks' (ie airbomb) based on its UNITAI_, chance and circumstances

2) The unit then iterates through all the squares in which the task (airbomb) can be done.

3) It then does that task on the most suitable square

4) Moves on to next unit


ATM the weakness of the AI is in the small amount of circumstances which it takes into account, having looked briefly at the code I could only see pCity->isDanger() and pCity->numPotentialAttackers(), we need a lot more.
If we could give the AI a general plan which it could stick to for a few turns, then it would also greatly improve. Maybe, when it declares war it could spot a weakly defended enemy city, and select that as its target. For the next few turns any units which are not on 'critical' duty (defending cities/key resources) are saved. When the stockpiled units gain x times the strenght of the units in the defending city, it moves onto the attack, and will only back away if it is obvious which it is loosing.

The other way to make it better would be to have feedback. In the top example, the unit has already decided that it will airbomb, even though it hasn't even looked at the different targets possible. This means that x% of the bombers will reduce the defences of a pointless tundra city, instead of attacking that nice, juicy SOD. A way of changing this would be to evaluate the effectiveness of airbomb and airstrike and only after decide which one to do.


Yet another way of improving the AI is in the order in which it does things. I propose this. It iterates through all the units once. If a unit can do an action which it rates to be 'very good' then it does it, otherwise it waits. Once it has looked through all the units once, it has another look. This time it will be satisfied with anything ranks 'Good'. Repeat.

Is this feasible?

I haven't really looked at the unit AI, but I'll try and comment.

Maybe, when it declares war it could spot a weakly defended enemy city, and select that as its target. For the next few turns any units which are not on 'critical' duty (defending cities/key resources) are saved.This may sound good, but may fail against humans. The human would deliberately leave a city very weak, the AI would build up units, go after it, and then get torn to piece by units behind the lines. In Civ 3 the AI would usually always go for the weakest city, and as it cheated and could see the entire map, leaving an undefended but good city in a really safe place would draw the AI in to be slaughted. The case here is less severe, but I can see it being easily exploitable (the AI, for example, can't always see all the cities, so you just control it's knowledge a bit and trap it... over and over again!).

A way of changing this would be to evaluate the effectiveness of airbomb and airstrike and only after decide which one to do.
Sounds good. The only issue would be that to check all the possiblilites for all the actions would take considerably longer to process. I'm not sure what order of magnetude we're talking, but too many of such changes might make a significant difference to the speed at which the AI plays.

Although we could argue that since the release of the game the average computer spec has gone up, so we can take a few liberties with degrading performance...


Yet another way of improving the AI is in the order in which it does things. I propose this. It iterates through all the units once. If a unit can do an action which it rates to be 'very good' then it does it, otherwise it waits. Once it has looked through all the units once, it has another look. This time it will be satisfied with anything ranks 'Good'. Repeat.
I really really like this idea. The trouble, as you have identified, is that the situation often changes throughout the turn, meaning that the unit order is quite important.

I might write a bit more after I've eaten - can't think properly on empty stomach!

This may sound good, but may fail against humans. The human would deliberately leave a city very weak, the AI would build up units, go after it, and then get torn to piece by units behind the lines. In Civ 3 the AI would usually always go for the weakest city, and as it cheated and could see the entire map, leaving an undefended but good city in a really safe place would draw the AI in to be slaughted. The case here is less severe, but I can see it being easily exploitable (the AI, for example, can't always see all the cities, so you just control it's knowledge a bit and trap it... over and over again!).


Hadn't thought about that. Maybe have the AI go for an important city rather than a weak city, or have it retreat as soon as it becomes unlikely that it will capture that city.


Sounds good. The only issue would be that to check all the possiblilites for all the actions would take considerably longer to process. I'm not sure what order of magnetude we're talking, but too many of such changes might make a significant difference to the speed at which the AI plays.
Although we could argue that since the release of the game the average computer spec has gone up, so we can take a few liberties with degrading performance...
I really really like this idea. The trouble, as you have identified, is that the situation often changes throughout the turn, meaning that the unit order is quite important.


I don't think that the performance hit will be that big. I guess there's no way of knowing until we try it though. If it does end up slowing down the system than maybe we could add a slider saying how much time you are willing to let the AI spend per turn or something.

Hadn't thought about that. Maybe have the AI go for an important city rather than a weak city, or have it retreat as soon as it becomes unlikely that it will capture that city.
That would be even worse. You could keep AI stacks confused for ages by moving defenders in and out of cities.

If you were to make it sufficiently complicated it would be hard to exploit, but complicated things often don't work very well for the function they were orignally designed.

I don't think that the performance hit will be that big.I'm pretty sure it'll be a drop in the ocean... however lets compare what it is doing now with what it could possibly do under the system you are proposing.

Before:

Unit --> Airbomb --> Get best plot --> Bomb

After:

Unit --> Airbomb --> Get best plot --> Airstrike --> Get best plot --> No very good missions --> <Cycle rest of units> --> No good missions --> <Cycle rest of units> --> Average mission found --> Do mission

Now I'd guess that the bit where the best plot is found would take the longest (scanning lots of plots and analysing them), so we probably have a scale-up in time of maybe 2 or 3. If something similer were run for ground units as well the the times could add up to something meaningful - espcially in the late-game of a large map.

If it does end up slowing down the system than maybe we could add a slider saying how much time you are willing to let the AI spend per turn or something.To be honest the time in between turns is on the short side at the moment - the only thing that seems to take the time is animations, so we could probably get away without this. People might not even notice.

Even if it doesn't take years for the computer to do this, it will take years for us to write this. CvUnitAI.cpp is about 10 000 lines long. Is it really worth it?

We wouldn't have to re-write the whole thing. I think the improved decision making idea you are suggesting could probably be slotted into the current system quite easily.

We'll see what the others have to say about this before we dive in though. I have to say that I am suprised that they did not use a system like this when programming the AI in the first place, unless I missed it.

That would be even worse. You could keep AI stacks confused for ages by moving defenders in and out of cities.

If you were to make it sufficiently complicated it would be hard to exploit, but complicated things often don't work very well for the function they were orignally designed.


I like that idea of giving the AI a mid term target. To prevent that the strategy is to predictable by humans we may have to add some random factors. The AI then can randomly choose one of them and go for it. Example:

create a ranking of the cites for each of the following parameters :
- culture,
- production
- defense
- ressources
- .... and whatever else

Next is to have different weighting of those single parameters by random factors (x, y, z, v, ....)
- culture * x
- production * y
- defense * z
- ressources * v
- ....

sum up those factors and go for the city with the highest one. Once a city is selected the mid term target is created and the AI tries to fullfill it. By another random factor the spontaneity of the AI is set, to cancel that goal. A higher factor means the target is followed more strictly, a lower factor the opposite.

We also can combine those random factors with the leader or civ attributes. This should add another element.

12m

Good idea. That way Montezuma would be suicidal on the battlefield as well as in diplomacy. Would require a hell of a lot of balancing, but if we can pull it off, it would be truly amazing.

I have not read any comment as im a bit short of time but the AI does war in several steps.

A it nearly constanly is in a kind of war, but most wars do not break out. Why? very often the AI selects that int wants to do war. It then switches to a preparing WARPLAN against one enemy. After 10 Turns it begins evaluating its power and the enemy power. If it is stronger than the enemy it declares. If it has not gotten stronger within 20 Turns it switches back to peacefull and starts the cycle again.

Now war itself. The AI evaluated each Area (=continent) which kind of war it wants to do. If it has a lot of troops it changes the AREA_AI to ASSAULT.
The other AREA_AIs are not to interesting.

At this step (ARIAAI_ASSAULT) it select one city and all offensive units on the continent are set to attack this city. The city is at the moment primarily selected by how far it is to the AIs lands (way/path wise).

The next step is the movement of the troops themself. This is primarily dictated by the UNIT_AI.
There are some things that seem noteworthy.
- The unitais seem to work ok. Keep in mind that the AI very often groups its offensive units so therer seldom is one lone attacker.
- The UNIT_AI is decided on built time and never changed. This means once city defender, always city defender.
- The way goups are built by the AI. Its simply if an UNITAI_ATTACK unit sees anotehr UNITAI_ATTACK unit it runs therer and attaches itself to the stack. There is a limit to the stack size dependend on the exact UNITAI of the stack and sme random numbers. Now these staks start running around and do whatever the head unit (which defined the UNITAI) would do. Only for attacking all units are considered.

what i do not yet understand at all is the way sea-war works.

I hope this small overview helps. Now i have to go back to my mages and to understand all this indepth (especially the Selection Group things and sea warfare)... or kael bites me. ;)

P.s. doing what monkey proposes should need only a change in the selection of the city to attack, so it is a very localized change.

Thanks Chalid - good info there.

Having read that, I still think the action filtering method based on the value of the action would work, with units with very good actions go first in the hopes that they improve the action value of the units with less good actions at present.

About city selection - I agree that the nearest city isn't optimal, but it's a pretty good approximation to what the best city is... it's usally my tactic except in very specific circumstances.

Thinking about it, always going for the nearest city is as exploitable as always going for the weakest. However I suppose there are other unitAIs to stop you from just protecting the nearest city. The pillage AI tends to wander about a bit and attack if it thinks it can win, and the naval AI likes doing flanking manouvers.

Out of interest, does anybody know the difference between the ATTACK_CITY AI, and the ATTACK AI? I guess I could look it up, but I'm feeling lazy.

Let me think about it.
ATTACK joins stacks (of doom).
ATTACK CITY does not join stacks.

ATTACK CITY does collateral attack and bombard
ATTACK does those two things not.

We could use influence maps to help out with this goal. That way it keeps is out of the realm of a static formula.

Static formulas are bad. :(

Dale

static formulas are easy though.

Static formulas are predictable and easy for a human to work around. :)

The Civ 4 AI doesn't come with many static formulas - pretty much all of them have some potential for variablilty based on events other than the main one. Some of them don't have very much potential for variablility, but it's still there. Something to work on.

Are you planning on having an attempt at coding this LO?

I will start work on this in a few weeks. I am making a Air and Sea mod at the moment and then I would like to play a game.

Comments about the unit AI - specifically naval attacks: http://forums.civfanatics.com/showthread.php?t=173250

Been getting quite a few new people interested in editting the AI apply to join the group since that really old thread about it was bumped in GD (this one (http://forums.civfanatics.com/showthread.php?t=119963&page=6) - some interesting discussion about genetic algorithms). Please feel free to contribute anyway you like guys! I'd love to see some good AI upgrades make it into the next version.

The AI test framework will be a must.

The test cases required to assure this is an improvement are very numerous!

These are AI options right? Not replacements?

I think just one global switch for the new AI should do it. We shouldn't have to have swithes to enable/disable every part of it.

Personaly I dont see a need for that, people universaly want strong AI's. Theirs are also going to be lots of AI changes that just involve it understanding/using a new feature and having these turned off could cause problems when the new feature is used.

I think such a global switch is recommended. I want strong AIs as well, but in case it gets to strong I would like to make it weak somehow.

12m

Why not just add a dropdown menu for an AI option instead of just a checkbox. That way we can have easy, medium, hard, and impossible settings in one switch. When an option is selected it sets a different set of algorithms that the AI runs from.

The new features could be just a simple (!ModElement) so if the python elements are not there, the AI does not take that section of code into account, thus reducing the chance for errors and improving modability.

If the AI were made dramaticaly smarter wouldn't you just drop down a difficulty level? The difficulty levels all work by giving the AI artificialy bonus || penenlty under all of them the AI "thinks" in adsactly the same way (dumb).

Now I know their was some though about alowing AIs to be instantiated and played against each other to compare their effectivness. That seems a better strategy so you could play a regular Firaxian AI against a supped up AI and see how decisivly or consistently you could win.

It definately doens't need a drop-down. Either on or off should do.

I would suggest having the on/off switch as there may be some mods for which our the deafault AI may be better - especially if we optimise our AI to default game... though I supose if we do it right there shouldn't be.

One switch sounds good for general use.
But I think AI modules should be individually switchable from Python.
This is only from the "We are making a mod for modders" and the "AI is a pain in the south end of a north bound unit to do and test properly" points of view.
Of course, defining modules, dependancies, and so forth may be a nightmare of its own. So take this with a grain of salt.

Sorry for being so inactive in the here, having a huge project at school and exams as well. However when it is finished (around next week), I will be able to contribute more.

About genetic algorithms is an interesting approach. Having a huge interest in artificial life my self and a bit experience with this. However it might be a bit overkill to have an exact GA. Maybe we should drive toward some dynamic programming instead, or EP, maybe GP, or even a neural network :crazyeye: however it is not important what we end up with, as long as the AI becomes 500½ % better at decision making and playing the game, so you, as a human player, would get an equal match, without the AI cheating by getting unfair help (practicallymaking multiplayer obsolete;)).

Back to main point:the AI needs major rework on all areas. And I think could be a way to go is a top-down approach on this.

(OBS.: he is generic for both he/she/it ;))

I mean that the AI need to make high level (long term) decisions, and going down the levels/layers, down to simple direct decision like unit movement and city production/specialist etc. For example the AI decides that (Overall goal) "I should dominate this continent by 1500 AD", then at the immediate goal layer it decides "I will build up my army so I can attack Ceasar", then at city level it should ask the question "What should I produce in this city if, I would like to fulfill my immediate goal, giving the situation my: empire is in and the city itself is in." etc. etc. down to unit level.

The Overall goal and immediate goal should not be revised, unless something drastic happens, like the finding of a new uninhabited continent (maybe overall goal here) or someone is near completion of the spaceship (both overall and immediate goal), or declaration of war (immediate goal changes). We can make as many layers as we think is needed. The low levels, should be revised, not necessarily changed, but evaluated again, each turn or every second turn. Very lowlevel may need to be evaluted more than once, each turn (as stated in above posts).

General:
The higher the decision level is, the more abstract it is in terms of actions, and is more influenced by the leader. And vice versa. The lower the level, the more concrete it is, in terms of actions, meaning it can be directly translated into an action in the game (move unit from x to y for example), while this is more influenced by higher levels, other decisions, the world around it etc.

It is important with the top-down approach, that information, decisions and factors propagate up and down in the system. So another players city placement (losing a valuable resource for instance), would propagate up to the war decision layer(and thereby the immediate goal layer or something), and instead of a purely random factor decides war or peace, it should incorporate much more factors, so it would seem both more realistic, but also unpredictable, so exploits would be rare or extremely hard for the player to take advantage of (applies to all layers).

A comment on war:
Instead of just having the AI going toward the nearest city in war, it could do several things instead, based on a lot of factors. Like: if the AI determines that a defensive war is better (because conquering cities, having better defensive units, technology level etc.) then it would not attack, may at the most probing with a few units. Based on leader personality, he could move all his offensive units through the land and pillage all he can, or he could go against the nearest city, or split his army in two, attacking two different targets, and/or use sea transporters to sail around and attack from the rear (and not only 2 units...), eventually the AI could scout with spies, missionaries etc. before declaring war and determine his attack plan. And I could go on and on.

In addition the AI needs to know when he is heavily losing. Right now only success is record for the player and the AI, so having a success of 0, doesn’t really meaning that it goes decent, and likewise with a success of 50 or 100, if the AI have lost all but one city, then he still thinks has some kind of success.
(Check AI_endWarVal in CvTeamAI)


I know this post is a bit ...Random?? and hard to understand, however I am very busy and only wanted to comment quick.
I will try to come up with a more concrete system later. Please comment if you understand my post :D

(Edited for clarification, spelling mistakes and random babble)

I agree with you completely NikG. To make the AI better, we need to make it more 'human'.

All of the best civ players are human (obviously) so the AI needs to think more like a human. I know that this is impossible as AI's can think in the true sence of the word, but we can get close to this by having it mimic the style of play of a human.

The best way to do this is to play a game very carefuly and write down every descison that you make and why you made it. For example, "Moved a longbowman from Paris to Orlean as I think that it is in danger". You can then go in even more in detail and say "Orlean is in danger because war with China is iminent". Then you can say "I think that because they have an SoD on our border.

I know that this would take ages but it would help us understand how the human player thinks. By knowing this, we can rebuild the AI to copy it.

Glad you like my ideas Lord Olleus.

And I think that it would be absolute amazing if someone would do the experiment you are proposing (which I really like). Actually it could just be a small map with 3 or 4 civs, with the quick option. The posting in, we could analyze this together.

It'd probably be best to get a player from the Stratagy forums where they are all good. One slight trouble would be that the humans would probably be playing against the AI - and so some of their actoins might be justified by predicing AI behaviour... which obviously doesn't help if we're changing that behaviour.

Sounds like quite a boring job.

About genetics - you've kinda lost me with EP and GP. What are they? I just did a quick poke through wikipedia and couldn't find anything that they might stand for.

EP is evolutionary programming and GP is genetic programming. We even have EA, evolutionary algorithm. Computer scientist just love acronyms... :)

But about the boring job. Well it might not be so boring. Actually it would just be like written one of those stories, just more precise and detailed... :crazyeye:

But I don't think it matter if it comes down to preceding AI behavior. I mean what a human determines to do of actions is based on the AI's actions, not how the AI decides the action, so in the end it really doesn't matter. Of course when the AI changes, the AI would make more complex analyze of the situation at hand, and then make better decisions, which in the end corresponds to better actions, if I might say so. In the end making the AI a better player. So a human may be more careful with a new AI, compared to the old one. And as such the human doesnt really alter the decisions of his own because the actions of the AI gets better.

Btw if we get a good AI working, we could end up with a AI that doesnt need 75.000 units. And thus making it even better in the tech race and other areas as well.

Slightly confused.

What is the difference between a GA and GP. Seems a GA is GP isn't it. EP is like GP, but doesn't have crossovers, right?

Why would an Evolutionary algorithm be better than a Genetic one? From what I can gather it is similar, but doens't involve crossovers, which seem to me to be good things.

Most of the field in artificial life is largely somewhat interchangeable.
Originally they had distinct meanings and uses, however with all the progress in the field, it became similar, and the even the real difference is hard to tell (actually I cannot categorize one precisely).
Most often though the following apply:
(anyone with a degree in Artificial Life should correct me if I am wrong, until I get my own degree ;))
Trying to avoid technical stuff, all uses genetic operators in varying degree. How the next generation is chosen, which to use compared to the fitness landscape etc.
- EA, is often used as a generic term of all different kinds of algorithms and more, that uses evolutionary processes.
- GA, use most often a static highly specialized fitness function, with a static representation, and fixed length (not always). The population is often also static and there is no environment as such, and therefore no interactions between the agents. Mostly used for optimization. The representation are often highly abstract.
- GP, are in theory computer programs themselves. Often written in a pseudo implementation specific programming language (but not always), running in a virtual computer, which is just a piece of software mimicking a computer. (Or it could be said it is a kind of interpreter instead). The fitness function are still specialized, while the representation is concrete, and it is variable in length. Most often used with the LISP programming language.
- EP, much like GP and GA, but without getting to technical it would be a waste of time to describe the real differences.

And there is much more.
But there is another kind, which all out from the normal category. Namely software like Tierra and Avida. Here the fitness function are more abstract, and living entities co-evolve with the environment around them. The representation is like computer programs (hence it can be said it is a specialized form of GP). There is even one AL software without any form of fitness function. DarwinBots (which I am my self a member of, this is an open source program, which is developed by people who love AL). The fitness function is not in anyway coded in the program, and the function is only true darwinan selection, ie. survival of the fittest.

For more information check the net, and wikipedia isn’t the best source, there are many great sites out there…

Links:
Tierra (http://www.his.atr.jp/~ray/tierra/) (AL software)
Avida (http://dllab.caltech.edu/avida/) (AL software)
DarwinBots (http://www.darwinbots.com) (AL software, large community)
GreyThumb Blog (http://www.greythumb.org//blog/index.php) (Nice blog about Artificial Life)
EvoWeb (http://evonet.lri.fr/) (Not updated :sad: )

A side note:
It is hard to find very good sites describing AL in detail. The best would be to buy some books (Amazon have plenty), and/or program some youself.

My knowledge about the field, mostly come from books I have bought and by programming a wide range myself (however only at hobby level, so nothing serious and therefore only for my own amusement).
I study computer science (or I hate that word) at the university of Copenhagen, and intenting to take a degree in AL. However there is no courses in AL in my country(at all, Denmark only have 5 mill. inhabitants), so either I just (re-)invent the field myself or go study abroad. ;)

Is this actualy feasible for a program as complex as Civ4?
Having a fully genetic AI would require millions of generations before we see a significant improvement compared to what we have now. It would also be a phenomonal amount of work as we would have to write a program which says which AI did better in a particular zone (combat, city location, ect...) to take the best bit of each AI and combine them, if we didn't do this then our final AI could be very good in one feel and awefull in another.

The only way we could do this is to create very specific senarios and have the AI play against each other in it. I am talking about something like they both start with x warriors, y archers and z axemen. This way we could perfetionate the AI bit by bit, and then combine it manualy to create a super-AI. This way should make it faster and easier to test, and it would allow us to have AI vs Human games, which is the ultimate test.

I think this could have some potential as a method to make AI's smarter but it requires a good deal of foundational work before it could even begin, fortunatly we already had plans for a lot of that work and it would be fruitfull even without the extra Genetic stuff.

We would need a means of creating an AI instance so each AI player in the game would actualy do things differently. This goes beyond the parameters on the Leaderhead which from what I understand just effect the AI's diplomacy not their internal managment or warfighting tactics. We would need to expose as much as possible the parameters outside the game preferably in XML, it might even be possible to get some kind of genetic Nodebased logic encoded their. Ofcorse their would need to be a lot of compartmentalization as Olleus points out, a little sub-AI to evaluate a particular desision that needs to be made.

This is all VERY VERY ambitous at this point we should look to doing things that are within our imediate grasp or are a slight stretch (I find that gives me imediate gratification and builds skill to extend my reach without getting bogged down in a project you never finish).

Is this actualy feasible for a program as complex as Civ4?
Having a fully genetic AI would require millions of generations before we see a significant improvement compared to what we have now. It would also be a phenomonal amount of work as we would have to write a program which says which AI did better in a particular zone (combat, city location, ect...) to take the best bit of each AI and combine them, if we didn't do this then our final AI could be very good in one feel and awefull in another.
Yes, I think it probably is. Either it could be oursourced to many computers, or it could be run for several months on one... this is assuming that Civ doesn't crash while you're doing it of course. The amount of generations needed would depend on the generation size.

Determining the fitness function is definately the hardest part. If this were to be done I would suggest basing it mainly on the outcome of the game rather than individual actions, and then averaging the result over 10 or so games.

I think a full 10 games would take about 20 minutes per AI (remember we are running many at once), so generation sizes of 40 would take about half a day per generation. The question really is, how many such generations would you need for meaningful results? I don't really know, but I want to have a go at finding out!

It's not even that large of a project, is it? The basic mutation & combination algorithm should be possible to write in a few hours, and then you just have to track down all the variables you want to change, feed them in, and do a little fiddling to get the computer to repeatedly play games against itself.

Well okay, I may have started something that I shouldn’t have done... :blush:

I can't quite follow you here TGA, do you mind explain it more detail?

(I refer to genome as an AI that needs to be evaluated/tested)

1 game with 18 different genomes(or AI players) takes how long?

We assume we have 1 computer, 1440 minutes a day ;)

In each game we could test 18 different genomes, if a game takes (guess?) 20 minutes, we could have 72 games a day, which equals to 1296 different genomes, however the important stuff is not to evaluate as many as possible, but to evolve successful strategies, so they actually become better. If we say each game is a generation, we could have 72 generations each day, so roughly we need around 20 weeks to get a generation count of 10.000, which is very low (possible we should aim for 50.000). 10.000 generations equals 720.000 genomes evaluations, which is modest. But remember many genetic algorithms have 1000s (if not more) in population size, running for 10.000s generation (which have a really concrete representation compared to what we are going to have, and still evolution is slow, on some super computers they even have population sizes in the 100.000s).

However all this is only of secondary importance. The fitness function and the representation is a very important aspect of the model we are trying to construct.
A fitness function of the outcome of the game is easy, but very narrow, and there are so many factors that influence a game, but still it will roughly split the genomes that can't even do some good at all (like not settling at all, or not researching, not building any units etc.), but it could be discussed.

The representation is very important. TGA you are talking about having variables, which is just like optimizing a differential equation. But this is much more than that. This isn't optimizing, the AI have algorithms to determine what to do, yes based on numbers, but the AI is more than the sum of its parts ;). It is the algorithms we need to represent.

So without sounding too discouraging, this is just a huge undertaking. No one it the field of AL has every tried such an ambitious project, as this is.

Sorry.

Why do I get the feeling the AI will be the biggest, hardest, most time consuming part of this upgrade. If we are going to do this right, we will need a large group of programmers dedicated to the AI alone to get it out in a reasonable amount of time.

Somehow I do not think SourceForge is going to handel this type of development to well. This portion is going to change VERY often and will require a much more powerful and user friendly interface.

If the only purpose of having a genetic AI is to decide the size of a certain variable, wouldn't we be better off using human experience by doing the experiment I described above, where you note down everything you do and why?

But turning every experience into a number, or a combination of numbers based on different things is rather hard...

But at least it gives a starting point on what the structure of the code should be...

But turning every experience into a number, or a combination of numbers based on different things is rather hard...

My idea was, as you say, to optimise the values (such as build values) for each factor within the AI. Main reason for this is that it isn't such a big project. It seems to me that while the algorithms can't really be simplified to the numbers that define them, optimising these numbers will produce a better AI, even if we don't change the way it "thinks". Would the fact that we're starting from a pretty good AI help cut down the number of generations needed?

Well I still believe we should try and implement a hierarchical layered AI. But the problem with optimizing pure numbers, is that it can get stuck at a local optimum. Of course having a good AI should (in theory) be better than having a less good one. The problem is still just that these numbers in the end corrospond to direct action, which is factored by so many different things, that in some games it is better to build cottage, while i others in would be better to build workshops.
So by having a fitness function of the outcome, would not really say something general about the AI (ie. "this is better than others"), and poor startpositions could well turn a perfectly turned AI into the bad one, quickly getting wiped off by a less perfect, simply becuase of startpositions.

AI will always be an extreme undertaking, but if we use a hierarchical layered and change the way the AI "thinks", we might well create a very powerful and much better AI, coupled with a kind of simple learning neural net, which learns the values of these variables we are taking about (often more effective when many factors are in play, and have the ability to learn under the game to).

Well I still believe we should try and implement a hierarchical layered AI. But the problem with optimizing pure numbers, is that it can get stuck at a local optimum. Of course having a good AI should (in theory) be better than having a less good one. The problem is still just that these numbers in the end corrospond to direct action, which is factored by so many different things, that in some games it is better to build cottage, while i others in would be better to build workshops.
You are correct. The numerical factors are there to decide this, but they don't cover everything.

However...

I'm planning on writing a genetic one anway based on the idea I suggested above :D. While it may not give any good results, I think it would be quite a fun thing to do. I could leave it running in the background of my computer when I'm not using it, and I'd quite like to see what results it does come out with.

So by having a fitness function of the outcome, would not really say something general about the AI (ie. "this is better than others"), and poor startpositions could well turn a perfectly turned AI into the bad one, quickly getting wiped off by a less perfect, simply becuase of startpositions. This is why I would run each AI through several different games. This will mean that the fitness determined will be for the good starts, and the bad. 10 may not be enough - it'd have to be tested by applying the fitness function to a load of default AIs and seeing what the variation after every few games is.

AI will always be an extreme undertaking, but if we use a hierarchical layered and change the way the AI "thinks", we might well create a very powerful and much better AI, coupled with a kind of simple learning neural net, which learns the values of these variables we are taking about (often more effective when many factors are in play, and have the ability to learn under the game to).How would we teach it? Would this be another case of AIs bashing their heads against each other?

Well a quick comment: Yes, a neural network could be used. An experiment where only AI vs. AI, no human involvement. It would be an unsupervised learning algorithm of some sort. Maybe we should even have more than one. Actually one for each of the layer of the hierarchical layered AI, because after all if we should only have one, it would get so generalized that it wouldn’t help, or it would take to long to learn it anything, or even takes to much time to compute.

However modeling this neural net, would be just as hard as a modeling a genetic algorithm (I am talking about the representation),
but it would certainly be more doable, and it would even learn after the mod has been released (don’t be afraid about contamination ;))
My project is due to be finished to night (wooh 7 weeks in row of writing docs and programming), so I will try getting a design document of the AI by Monday afternoon, including both the hierarchical layered AI and aspects of the neural net. I will not dig to much into the genetic algorithm, unless people want it.

Btw TGA you are more than welcome to program a genetic algorithm, which will be very interesting, and it could turn out to our favor anyway, which will be a good thing. And if not you have learned something in the process (never to old to learn something).

NikG has the right idea in my opinion. The AI is best organized as a military organization:
The King has Generals have Captains have Lieutenants have Sergeants

All current CivIV game AI functionality is the peasants.

The depth of this layering should be easily changeable and variable to functionality area of coverage.
The AI that is a pseudo-recursive agent (becomes many sub AIs) down to the lowest layer.
The recursion then bubbles appropriate data back up the layers as each recursion cycle finishes.
Each cycle uses data from the previous cycle (or from several cycles derives an average, median, or some other algorithmic value).

Each possible action is the responsibility of the Sergeants, obeying the orders of his superiors in the context of the current situation; no other level has direct control of the CivIV game. The Sergeants place local, action related / situational data on a whiteboard data object.

Each Lieutenant is concerned with his orders to pass on to his Sergeants; these orders are affected by the data his Sergeants have gathered. The Lieutenant puts a summery of the data on the white board.

Each Captain is concerned with his orders to pass on to his Lieutenants; these orders are affected by the data his Lieutenants have gathered. The Captain puts a summery of the data on the white board.

The Generals do the same.

The King takes in the whole picture, as summarized by his Generals, and gives new orders.

I havn't follow this thread very deeply, but are you all sure that this became a bit to much for that project? The plans you have will have to much impact to the SDK that it could be done between two releases. That makes it hard to organize. Also I think that this is an complete own project. Maybe its even an own project to create the concept without an SDK. I have my doubts that we are able to manage that.

I see no reason why there should be any problem with spreading changes over two, or more, releases.

Another thing I randomly read:
Watching the AI is really an eye opening experience ... you quickly understand why giving the computer players all those bonuses on higher levels isn't really cheating ... they're not really intelligent! The AI disbands a lot of units because of financial problems ... waste waste waste! Financial issues and planning are the biggest problem IMO, followed by an inability to defend against barb units. These are related, as the barb units walk in and destroy cottage after cottage. They AI doesn't set up a perimeter or even attack them most of the time (seems to only attack with charriots or horse archers).

I like chrusion's description and had some thoughts to add.

Each of the Entities he describes could hold "priorites" which are basicaly the goals its striving for. The King AI takes a broad overview of the game state and takes input from the Leadhead flavor tags and sets himself priorites that are apropriate. Priorities can be have a weight (vHigh to vLow)and a time frame (Imediatly to Eventualy). At times when the kind changes his priorities he may instantiate or destroy minister AI's, or re-alocate assets to them. The kind dose not tell them how to complete their tasks or set their internal priorites other then through the timeframe value.

Minister AI's fall under 2 loose catagories Military (called a General and is focused on miliary campaigns) and Domestic (called a Govenor which focuses on Cities and workers) the naming is purely symantical as any asset can be controled by any Govenor. Different types of Ministers are generated acording to the kings priorites and it then generates its own set of priorites based on the time frame value and Asset array passed to it by the King using its internal logic. These priorites are updated each turn to see they are apropriate, so for example if the King sets "MORE GOLD" as a Priority its instantiates the "Greedy Govenor" and passes it the timeFrame and control of some Assets with which to achive the goal. A "Greedy Govenor" could be given several Cities to run and some workers with whitch to build improvments. The Govenor might instantiate additional sub AI's to control individual units or Cities. The King would personaly control Research as this so heavily impacts every aspect of the game and needs to be cordinated with all his priorites.

When the King desides to end a priority the minister is terminated and its Assets reassigned to other ministers. If the King desides to change the Weight of a priority it will re-assin Assets to reflect this change in Weight. So for example if "Milirary Buildup" Weight goes from low to High several additional cities would likly get re-assigned to reflect that. A change in timeframe is passed directly to the minister so that it may re-evaluate its own priorites. When new Assets (Units and Cities) are created they get assigned to the govenor that can make the best use of them. Periodicaly the King (or any AI) will re-allocate assets based on a "desirability" value that the sub-ministers will report back when ased to evaluate the desirability of an asset. So for example the "Offensive Warfare" general will report that it more highly desires a unit that has a CityRaider promotion then one with a City Garrison promotion, the "City Defence" general would do just the opposite.

The King owns all assets and can ask any of his sub ministers to evaluate the assets they currently control along with any other asset he might wish to querry them about. He will frequently (idealy at the start of every turn and durring key parts of turn processing) ask them to give a desirability for an asset they dont control. The King takes all this under advisment and re-assignes accordingly. So for example the "Protect the Workers" minister could beseach the king that he should be alowed to take control of a threatened worker away from the "Build Growth Improvments" minister that currently controls it, it could also grab an archer from a nearby city (if "Defend Cities" minister dosn't need it too badly) and move both units into a forest for defence. Once the threat passed the Protector reports low desirability for its assets and they will get re-assigned. The now assetless Protector would hang around and each turn the King would ask it if feels any of the workers are threatened. A "Protect Improvments" general would likewise be responsible for prevent pillaging. Map plots within the players Cultural borders are also evaluated and assigned as assets both for the purposes of determining which city will work any overlapping City plots and for desiding what type of Improvments will be built.

Desirability serves as the primary means to make shure the AI "stays the course" and finishes doing what it starts and dosn't flit between half finished tasks. For example a City govenors would take into account the current progress of buildings at a City so if a Wonder is a few turns from completion the govenor will report very high desirability to control the Cities build quee so that it may complete the wonder. The "Defend Cities" general would have to deside the city was in such iminent danger with no possibility of outside reinforcments ariving in time to beat out the domestic govenor for control of the queue and change to building a defender.

Such compartmentalization means each minister can be very narrowly focused on its area of expertease, by writing minister Instantiations, weights and timeframes to a log file the Kings behavior could be interprited and tweaked. Ministers would log their desirability allocations to see if they are making poor choices.

Bravo Impaler! Very nice analysis and extension! I like the narrowly focused ministers! Puts a very nice parallel algorithm into effect with tension(Desirability). A sort of fuzzy matrix if you will :)

Yes, this is a big project but it CAN be broken up into several steps. Lets finish brainstorming out our ideas and come to a consensus on a plan. Only then can we see the steps we have to take and how we should break them up into sub projects.

The options will be clearer then!

Some thoughts on combining above system with Genetic fitness functions.

We could use the above plan in combination with traditionaly programed ministers and it would likly work fine and be a huge improvment on the AI. but seeing as everything is naturaly encaplusated its should be possible for some or all ministers to be created or tested in non traditional ways.

I remember reading some interesting stuff about node based genetic algorithms being used to teach little "bots" to fight a shooter game (wish I could remember that link). The little bots take a set of simple inputs "angle of nearest enemy", "range of nearest enemy" "is enemy in crosshairs" and output simple things like "move forward", "rotate clocwise", "shoot". If we have an automated play system then we can set up AI vs AI games and use the loging feature of the King combined with a fitness function we give him to record an evaluation of the ministers he used.

Different Civs in the game would be instructed to use different minister Instances for the same Kingly Priority. Each game would test only a single priority/minister pairing so all other factors remain constant and the only differences in AI logic will be the effectivness of that particular minister type. After the game ends the Kings evaluation log could be digested by an outside program (or better yet the Python layer outside the game instance). Said program tabulates scores for the various ministers types taking into account the Kings performance evaluation AND an evaluation of the Kings game score. This way we catch and penalize ministers that achive their goals by screwing the rest of the Civ (for example a "Get Gold" minister that neglected food and starved his cities). Once sufficient tabulations have been gathered the mutations are made and another round of testing begins.

It would likly be nessary to build up the minister tree from the bottom up, At first the King would be an almost wholey automated pice of code that just switched priorites at random. Once the ministers are developed to the point of basic competency you could begin developing a thinking King which would start to set priorities based onthe game state. A cycle between minister improvment and King improvment would then commence and each generation the King would be taught to recognize the improving skill of the ministers and comensuratly call upon them more often.

Further Musings...

Their are likly going to be a lot of 3 way tug of wars between ministers and these need to be handled well or the AI could end up doing su-optimal things for example when say the Sciene, Culture and Gold ministers all want to have a Harbor built in the City to boost Commerce but the Military general wants a Barracks.

If the King allocates resorces based soley on the minister with the highest desire for the asset (after taking Priorities into acount ofcorse) then you have the potential for mis-alocation. The simplest solution would be for the King to ask each minister what they intend to do with an Asset and votes are talleyed by camps of usage rather then individual ministers. The highest camp then gets the resorce with the highest priority minister actualy being assigned the asset. The king only runs this kind of check if their is no clearly dominant minister.

A whole class of "Efficiency" ministers would exists as well, they would aim for overall efficiency in the economy and act to give balance to the very narrow views of most other ministers.

Lastly another minister type, the "Advisor", these can be though of as the Power behind the throne. Advisors would be persistent and instantiated at the start of the gamem, they never control assets. Under this new interpritation the King acts like on Operating System Kernel, the only thing he dose it ask for the advise of advisors and apoints/removes minister and alocates assets. His only memory is the Priority list, the minister lists and the asset list of each. Advisors tell the King what Priorities to set and then he passes thouse Priorities to other advisors who tell him what generals and govenors to apoint and what assets to give them. This further compartmentalizes the AI logic and makes it easy to understand the Kings desisions and modify them by use of different Advisor types. It also allows us to write a small and efficinent King who's code will be stable and completle very quickly before trying to build upon it with minsters and advisors.

I am not realy shure I like the many layered military hierarchy chrusion layed out. One of the AI's current problems is lack of cordination between units. I think it would be best if the lowest level of minister was more of a Luitenent comanding a whole stack or group of units tasked with achiving an objective, this would allow good cordination of forces at the critial tactical level. Luitenents would have types such as "Besige City", "Pillage Countryside", "Take City", "Amphibius Landing". As Lord Olleus pointed out the AI dosn't re-evaluate desisions as the units are moved, we would allow the Luitent to re-asses after each unit movment/attack as the turn is exicuted. Above the Luietenent is a General who as you know is reporting to the King, the General will usualy only comand 2-4 Luietenants, often just 1 in the early game, Generals will usualy comand an entire war-front with a designated enemy player to wage it against, multiple wars on multiple fronts will nessesitate multiple generals in addition to the Homeland Defense General. Generals instantiate and delete Luitenents to activate campagins, for example removing a "Besige City" Luitenent who just bombards the City and re-assigning the assets to the "Take City" Luitenent which actualy performs the attack. Another point in the context of military units the timeframe parameter basicaly equates to expendability, short timefram leads to rekless suicidal behavior, long to cautiosness and defensiveness.

The Advisor Concept can be extended to the Military level ware they become "Strategists", again the Generals and Luitenents become kernel like as they have no real internal logic. (On the Domestic level you have Staff for the Govenors, remember this is all just symantical nonsense at the code level their no domestic/military split and only only modest functional difference between ministers and advisors). The Luitenent could themselves have Strategists (perhaps we can call these by a different name to do destinguish them from thouse at the General level).

NikG && TGA what do guys think?

Sorry, been busy lately with end of exams, and having far too much fun ;)

I'm concerned about time. We don't have to just create a good AI, we need to create a good AI which will be able to do all it's calculations in a reasonably small timescale so that the player(s) don't get bored. While this may sound good on paper, I'm worried that it might not be possible to do all the calculations neccessary in an appropriate timescale. At the moment each city only really runs one minister, and the king has very little impact on the decisions. Running 5 ministers and evaluating their choices to find which is the best is going to take longer.

At the moment the time is about right. At the start of the game it isn't really noticable, however, once we get to the latter stages with hundreds of units each, it starts to become noticable. We may be able to get away with allowing the AI a bit more time, as the turns progress pretty quickly at the moment, but not too much.

To keep this idea from swallowing time might be rather hard, although I'm sure there are solutions which hopefully can be implemented without degrading the AI skill too much.

one possible way of saving time is for the AI to do its calculations while the human is playing. This would not work during war, for obvious reasons, but during peace there is no way (or very little) in which the human player can affect the best improvement for a tile in a distant continent.

This might be very difficult to implement though.

I had a brief discussion with Rhye about something similar to what you just proposed LO. I'm not certain, but I think it may be just about doable. Given that decisions are processed at the end of turns, rather than the start of turns we could do as much work as possible during the player's turn, and then check to see if anything has been changed which may invalidate the decsions (declaration of war, important tech trade, contact with a new civ etc.)

You'd almost certainly have to restrict it to decisions not relating to unit movement, but that shouldn't be a problem.

Good one LO! I was going to suggest along those lines.
Also, some decisions do not need to be made every turn so the work can be spread over several turns.

I've pretty much got most of the genetic AI stuff nailed (for value tweaking, nothing more complicated). I just need to traul through the SDK finding values.

Then I need to find a way to get the game to keep running games with no interferance needed.

If the warlords expansion comes out before you get the auto AI working, you should take a look at the Genghis Kahn scenario Firaxis is making. It sounds to me like they are having the AI play a lot of turns before you enter into the world.

When I get Warlords I'm going to start work in earnest on the genetic AI. It's going to be quite a chore going through all the variables adding tags for them... I might just identify a few important looking ones to start off with, and optimise them first.

Anybody got any suggestions for key variables? Values of food/commerce/hammers for cities seems like a pretty key one to me. Also might filddle with the tech decisions, and war decisions.

Right. Well I found a quicker way of adding the AI variables (wrote a program to do it for me), so that's done now. I'm starting to run some tests, but I think I will have to put some major in work on my fitness function - final score, while it may be a good representation of how the AI has done in a particualar game only gives me one value per AI, per game... which is not only slow, but fairly dependant on starting positions.

I'm getting times ranging between 30mins and 1 hour for a 6 player standard map game... so that's between 5 and 10 mins per AI per map, which, with a generation size of 50, and 10 games per AI gives generations lasting 2.5 days. Perhaps a bit too long. I need to find some way of speeding this up. I have ~ 1500 variables, and I have a strange feeling to get results I'm looking at a massive amount of time.

I think my next task will be to generate/try to find a map script which will give each AI a fair starting position, to remove that element of randomness. I'm not too sure though - would this not eliminate AIs which were particularily good in poor starting positions, or which could maximise good starting positions? I'm still undecided about this.

BTW - I decided not to work on Warlords for a few months until it seems that they have stopped patching it. While the new method of adding variables is quciker, it's still slow.

EDIT: On further investigation it would seem that the changes I made had more of an influence on the game speed then I thought they had. Quite some slowdown going on. Going to have to a trim removing python events/callbacks and suchlike.

Yes I'm thinking all the Python callbacks that we have in the project are a major source of slowdown, I think we should drop them as their not currently being used for any mod. I'm im the middle of porting all my XML mods into Warlords, I'm droping all the Python stuff and will make the new sourcecode avalible for mod makers to use without having to worry about Python memory leaks or crashes.

TGA I recomend you develop your code in isolation on a virgin SDK thus removing any conflicts with the rest of the project, it can be merged into Warlords when ready and or patching is done.

I use one or two of them in the 40k mod. I'm really not sure how much of a slowdown they cause as I'm hardly being very scientific with my tests (just have Civ slowly bashing through while I do other thigns on the computer).

EDIT: I think I'd get a big kick in speed if I could lower the MAX_PLAYERS variable... unfortunetly it doesn't seem to like going below 18. Might test it a bit more... unfortuently it needs a full re-compile every time I change it.

Right. Turns out much of the speed issues was stuff in the background. It turns out Civ goes to "Below Normal" priority when alt-tabbed.

I've pretty much got everything strapped down and ready to go. I'll post up a few screenies tomorrow - I might even upload a working copy if tonight's test goes well. I'm having a slight problem with some AIs not building anything at all, which is a bit awkward... I think I might have to manually dive in and fix that variable, although tracking it down is going to be fun! (Current plan is to write a program to look for similar variables in AIs which don't build units)

Currently all I'm doing is fiddling with the fudge values in pretty much all of the AI calcualtions. I've decided against creating fair maps for the AI to play on. Next task is to write some test algorithms which will either be enabled or disabled in each AI, and hopefully it'll migrate to them.

Fitness is still based soley on end score, although I'm recording some other stuff alongside score... currently just for the purposes of cool stats. This end score takes into account the early victory bonus, so that should push the victories to be more likely.

I'm also contemplating releasing it to the public. I think I'll wait until I get the "no-units bug" squished, but I think it would market fairly well without the AI improvement aspect as a way to make the AI more variable.

If you need more computer power then feel free to ask me. My computer is pretty fast (2GB of ram, 256MB video card, 3.14GHz processor), so I should be able to get a few games ran for you.

A screenshot of the UI I bodged together. The idea is to allow users to play with their AIs a bit.

http://img153.imageshack.us/img153/7348/genetics1eg4.th.jpg (http://img153.imageshack.us/my.php?image=genetics1eg4.jpg)

How it works:

During each game the score, as well as some other stats relating to the AI's characteristics (shown by the bars), as well as the game info, are recorded and appended to the AI's data file. Currently the score is used for fitness, although I've come up with some other criteria for letting an AI continue to either breed, or stay unchanged for the next generation.

I'm probably going to go for generation sizes of 18, so that a full sized game can be played with all the AIs at once, and so that they don't take too long. These packs of 18 AIs will be downloadable from somewhere (not sure where to put them yet), and people will be able test them, and then send the results back to me for proceesing. Each AI has to play a minimum of 10 games for it to be eligable for proccessing, although they will be able to play more. Once all of a user's AIs have played AI games a prompt will come up when they load a game reminding them to send the AIs back to me.

The track AI feature allows users to select an AI to follow the progress of. This doesn't really have any effect on the algorithm, however is quite a nice tool to play with. I'll probably add a few more features in this direction such as more detailed stats on tracked AIs, or on-screen updates as the game is running.

The little +/- buttons by the AI don't do anything at the moment, and might never. The idea was to class AIs based on these factors and from that determine which alterations increase that factor. By using the +/- buttons it would be possible for the user to enhance that factor (although it's more then likely this would degrade other factors).

It's also possible for the human to play against the AIs. The screen above lets you pick specific opponents to play against which should not only provide a slightly more unpredicable AI then people are used to, but also hopefully a better one.

I'll probably make a post in main C&C about this later on today. Might be tomorrow if something comes up.

Wicked :goodjob:

I'm looking forward to contributing my un-used cycles to beefing up the AI's. Might I recomend that "Team Firaxis" be the name for the default game AI and that it is always sticked to the top of the list so it can be easily useded as a standard for guaging the overall improvment in the AI.

Good idea. I'll implement that.

I still can't get SC's event manager to work when I place it in my Program Files directory which is a pain - especially with the logging that I have to do. I'll have to ask people to stick it in the My Documents folder.

http://forums.civfanatics.com/showthread.php?p=4463294

If you havent already, read this paper on the NERO evolving nural network.
http://nn.cs.utexas.edu/downloads/papers/stanley.ieeetec05.pdf
Many good principles are elaborated on, the genetic encoding of the Nural network looked very interesting and the concept of "total population fitness" could also be key to modularizing the AI as I had sugjested.

Their code is also avalible for download and could probably be put directly into the SDK which might also have the advantage of speeding things up as it would reduce Python calls, the current system only changes weights, but perhaps we could even do away with Firaxis code and use the dynamic nural nets.

This may be off topic now (though it wouldn't have been if I was here to post for the first page)...

Concerning Ai target priorities during war:
Would it be possible for the AI to target an enemy city based (or at least have it as a higher factor) on the value of attacker culture (either in the enemy square or surrounding squares)?

If above a certain threshold value this could allow the ai to attack multiple targets and/or keep the war close to there border to increase the likelyhood of second wavve forces reaching the target to be of use.

While not necessarily helpful for long distance wars - it could be of use in border squirmish wars