Evolution Algorithms - My Explination

              Evolution algorithms are one of the two A.I. techniques that I find most interesting. An evolution is a type of A.I. learning algorithm, that also acts kind of like a random generator. Basically, it takes a generation of various states, each with a unique combination of certain genes, and evaluates them biased on a fitness function. An example might be the classic BoxCar2D , that evaluates cars on how far the move along a random track. After evaluation each states fitness, the function then creates the next generation of states by basically breeding the prior generation. Parents are selected at random, but more fit states have a higher chance of being picked. Evolution algorithms must also include a small chance of mutations occurring, to produce change in the overall population, as well as stimulate the development of new behaviors.

             One of the best uses of evolutionary algorithms is when combined with another A.I. technique; neural networks. Neural networks basically try and emulate how the human mind works. The network is composed of various nodes (neurons). Each node is only capable of doing one action, input nodes take some data, output nodes do some action, and logical nodes process data received from other nodes. For example, a network consists of two input nodes, one logical node, and an output. One input node is triggered, the logical node process the data, 0 from one input, 1 from the other, and sends a 1 to the output node, which then does something. The advantage of a neural network, is its capacity to learn how to do specific tasks over time, with the aid of a learning algorithm. A Google tech talk; Polyworld: UsingEvolution to Design Artificial Intelligence, goes into this subject in more detail. Basically, evolution algorithms treat the nodes in a neural network as genes. Given a pool of genes, and a fitness function, an evolution algorithm can be used to create a viable solution.

              The downside of evolution algorithms is that they take a considerable amount of time to run before showing results. As such, they may not be a viable for use in finished games. On the development side of things, its another story. Provided that a game is simple enough, using a evolution algorithm is a viable solution for play testing. In the game City Conquest, the creator, Paul Tozour, used an evolution algorithm to test the games balance, and also to see how the A.I. was playing the game. In his interview with aigamedev.com, he mentions how the A.I. was able to find exploits in the game, that a normal human tester would have been unable to find. While impressive, this method still isn't universal. In City Conquest, the genetics of each A.I. was basically a specific order of what units to build, and where to build them. Basically, the values being tested by the A.I., game balance and strategy, must be independent from the A.I. genetics. For any game where A.I. behavior may not effect actual game-play, or where the A.I. behavior is to complex, evolution algorithms may be unusable. As such, I believe that strategy games without random chance will benefit the most from these techniques.

              The two methods above are applications of specific aspects of evolution algorithms. Neural networks use the genes to produce interesting results. The testing method, uses the algorithm to evaluate the fitness function itself, finding weaknesses. So, what methods could utilize the third aspect, generation? A potential use for genetic algorithms is to use them in a way similar to random number generators. With a high enough mutation rate, one could apply an evolution algorithm to a rogue-like game, using the evolution algorithm to produce a level that is more balanced than a truly random one. This method could also be applied to a MMO games dungeons. This could allow levels to adapt to the player base, and maintain set difficulty levels. Unfortunately, this method has not been utilized yet, so I'm uncertain if it could actually be used.
              As an example of how evolutionary algorithms work, I've linked (link) to a small little program that I've wiped up. basically, the program evolves a population of strings, until one of the strings reaches the desired conclusion, Hello_World. The code take a while to run, but the "results.txt" file holds the results of every x*250 generation, and the final generation, so you can just skip ahead to the results.