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. 

Modules and Events

I've never really considered the implications of what object-oriented programming means before. Now, I'm considering the fact that because object-oriented allows for various divide and conquer techniques. When I wrote a simple 2D graphics program, I hard codded classes with no regard to the actual structure of the code. Since then, I've rewritten the code to take advantage of the two design patterns; the mediator pattern, and the observer pattern.

In my code, I have a single main class, the game class, that runs all the other parts of the program. Below that I have three classes; an input class, a sprite manager, and a physics manager. Within the sprite manager, I also have a sprite class. Basically, the input class generates a event whenever the left or right keys are pressed. The physics manager, in tern, is set to watch the input class for that event. When it sees that input has generated an event, it increases its velocity value in the direction of motion. If it does not see a event, it decreases the velocity by one percent. Then, if velocity is not zero, the physics manager generates a movement event. While that's going on, each member of the sprite class has been observing the physics manager, waiting to receive a movement event. Once that event is generated, the sprite class modifies its position by using the current velocity.

By using a pattern, by dividing and conquering, my code is easier to understand, simpler, and much more easy to modify. The lesson learned here is that its better to create classes and functions with one specific goal in mind, instead of trying to create a class or function that does multiple things.

Hello world!

Well, here is the obligatory first post. This blog is a place for me to put down my thoughts on various coding challenges I encounter from my classes at Champlain College, as I work towards my game programming major.