I was thinking of the possibilities of using genetic programming (
http://en.wikipedia.org/wiki/Genetic_programming) to make an AI that evolves when the player plays the game. The actions that a alien should do on his turn is represented as a tree. This tree has a root node, action nodes, condition nodes and end nodes (see picture). This tree represents the chromosome of the aliens intelligence. After a series of combats using a given chromosome this chromosome is rated. After a number of chromosomes are rated you combine the best chromosomes in hope that they will be better. These new chromosomes are now used and rated we are back to the start in the loop. This approach can be used to evolve intelligence for both aliens and civilians, and others if it is desirable. Now I will explain the tree representation and then I will go through some changes and possible solutions for this approach.
I will start with an example of a possible tree for a civilian. This is a very simple tree just for illustration. When it is the civilians turn to act we start in the "root" node. From here we go down to the "Alien in sight" condition node. If this is true then we move down to the action node "Move out of sight" and move out of sight. If it is false we move down to the "Move random" action node and move random. Both these nodes ends up in a end node, and we are finished with actions of the civilian. In an other tree might be bigger. For instance several condition nodes after each other followed by action nodes who are again followed by condition nodes and action nodes. For instance might a action node "Shoot on closest alien" be followed by a condition node "Is alien dead" node that can be followed by an other "Shoot on closest alien" node. This ordering is however up to the evolution to determine. We must provide a set of possible actions and conditions that can be used by the genetic programming algorithm. These possibilities must have corresponding function calls, and should therefore be small operations, like "shoot closest alien". It is less work to implement simple calls, and we should therefore let the evolution find the best tree. Possible actions and conditions might be:
| Actions | Conditions |
| Move to cover | Alien in sight |
| Shoot nearest alien | Alien position known by other operative |
| Shoot random alien | Can reach closest alien |
Just some examples.
There are some problems with this approach. If the tree becomes too big the algorithm becomes poor. One way of avoiding large trees is to make a penalty for it in the objective function(see next paragraph). We will often want to have a large tree because this makes a complex behavioral model of the alien. One way to make this happen is to create a predefined set of conditions and attach a chromosome to the leaf nodes of the predefined tree(see illustration). This tree might be different for aliens and civilians. This way we can rate the different chromosomes independently and evolve them independently. This improves the performace of the algorithm by making the trees smaller.
The biggest problem is how to rate the chromosomes. The common way is to have a objective function (fitness function) which is a mathematical formula. The function might look like this:
F(Aliens) = ([# of starting operatives]/[# of starting aliens])*(A*[Civilians killed] + B*[Operates killed] + C*[Turns before all aliens are dead] + D*[Aliens wins])
F(Civilans) = -E*[Civilians killed] + F*[Turns before all aliens are dead] + G*[live civilians when all aliens are dead]
Where A, B, C, D, E, F and G are positive values. The first factor is to avoid getting chromosomes that aren't any good getting good rating because there are few starting operatives. Designing this function is probably the most important factor to get the algorithm working. One might give a penalty for large complex tress, as mentioned or have a tech factor that takes the human tech level into account or other things.
The final problem is the collection of data. One have to play a combat to evaluate a given chromosome. Maybe we should let 50 aliens use the same chromosome to get a good average of the performance of the chromosome. To get all this data it's important to get as many as possible to play and test out chromosomes. Starting random chromosomes are often very poor, so there should exist a database of good chromosomes that can be included in the game to give evolution a flying start. Maybe the easiest difficulty could start with random chromosomes and more difficult difficulty could start with a set of chromosomes from a database.
I would love to hear some respones on this. What do you think? Do you have any questions? I have look in the wiki under TODO->2.3, and I see you have some ideas for AI. I could not find any information on it? I can implement the evolution framework in C, but I am afraid I can't commit to more than that.
I love the game by the way. Greate work!
