Hello people!
Genetic Algorithms is a very new, and still grossly underappreciated part of computer science, so I thought of doing my part in changing that, by informing as many people as I can. I won't get into any specifics about how GAs work as there are already a lot of great tutorials on the net about this, I will only try to give you a brief overview and hopefully get you intrigued to do your own research.
Why learn Genetic Algorithms?Genetic Algorithms are inspired by nature's way of evolution, and contain one amazing ability: The power to solve any given problem without formulating a plan!
In other words, we can make the computer do anything we want, WITHOUT having to tell it HOW to do it. Sounds crazy? It is... But it works.
I'll give you the first example, coming from nature itself. Do you know why geese always fly in a group forming a V shape?
We found out that when geese fly this way, aerodynamic forces allows them to fly 70% further than a single bird using the same amount of energy. Now geese sure ain't the best physics in the world, but there they are, flyng in the BEST way possible.
Now we humans have great physics who can use their minds to consider all possible physic laws and come up with great formations... Did we ever came up with anything better than geese flying? No..

Didn't you ever wished you could just
tell your computer to do something, and have it do it, instead of having to instruct it, step by step by step, before you can have it get anything done? Now with GAs you can, geese style
I still get to write code, right?Obviously. Your computer only understands code, and in Gamestudio's perspective, c-script. So you will instruct gamestudio how to do the GA(or use someone else's code for that), and tell it what you want it to do. Then run the GA, and leave it to the amazing nature-inspired laws to find the optimal way for you in order to solve your problem.
Once the GA is done, you will have your solution. You won't be able to understand WHY this works, but it will.. probably better than any solution that you could ever come up with.
What do you mean when you say problems? Can GAs write code and make a game for me?Yes, but that wouldn't be very practical... Academics define problems into two categories:
easy, and
hard. Not really a scientific term... but it does the job for them..
Easy problems are said to have a polynomial complexity, which means that the candidate solutions for this problem are
trackable, or
easy to visit all of them in order to identify the best. Sorting is such a problem... Pathfinding is another..
You won't need GAs for those kind of problems. For example, if you want to have the player model to move FORWARD when you press the W key. This is an easy problem with a limited search space(all possible directions that your player can move), and there also exists a conventional algorithm that solves the problem with one line of code (make him c_move forwards...)
Hard problems are those that have an exponential complexity, and this is when GAs come in. Most real-life problems are
hard, because there are so many possible different ways to try and solve them. The geese flying with optimal speed is a hard problem. You, walking, is a hard problem. You could be crawling, hopping around, rolling over, or walking on your hands instead. Instead, you chose normal walking, probably after a
lot of
trial and error from when you were a baby. You still don't understand the fine physics and friction that allows you to walk, but you can rest assured that millions of evolutions of humans before you, has assured that the way you move now is the
best way for a human being to move.
Since we are simulating real-life a lot in games, lots of hard-problems come in our way when programming. It could be AI, hard math problems, or even simplier logic stuff that you just can't get them to work or fine tune with all those Ifs and Whiles. For these problems, forget trying to understand how to solve em, and code a GA. It will take you a day, and the results will be breathtaking.
Show us...Later today i'll post in User Contributions my take on a
hard bin packing problem using GAs, in c-script. Here's the problem description:
There are a set of N items, and each item has a given weight. Also, each item has a given type (there are T different types of item). The items have to be arranged into C containers, in such a way that the total weight of each container is as similar as possible. However there are constraints involving the types. Items of type i and i+1 (modulo T) cannot be in the same container.
The data I've used is N=1000 items, C=50 containers, T=5 different types. (from 0 to 4). So i'll have to pack these 1000 items into 50 containers, and distribute the weight the best i can. Furthermore, i have to make sure that there are no neightboring types inside the same container( types combinations (0 and 1), (1 and 2), (2 and 3), (3 and 4), (4 and 0) are forbitten).
I challenge any good mathematician or programmer to give me a good solution to this problem. You can use the same
data that I used.
How will GAs solve this?First, they'll just randomly place all items inside the containers. It doesn't matter if they don't meet the restrictions or anything. Then, by doing small changes and LOTS of
trial and error, they will eventually come to an optimal solution.
Isn't that like trying ALL possible solutions to see which one is best?Yes, but GAs don't investigate ALL candidate solutions that exist, because they are
slightly biased towards solving the problem rather than investigating the whole search space.
Investigating all candidate solutions would also work, and the result would be GUARANTEED as the best solution to this problem. I actully did the math to see how fast would c-script go through all possible solutions....
With 1000 items and 50 containers, there are 9e+1698 candidate solutions.
C-script needs 0.00378 seconds to evaluate 1 solution. So... that would take 3e+1696 seconds, or 1e+1689 years.. That's
trillions of times longer than the current age of the universe.Well, who cares about bin packing anyway?The possibilities with GAs are limitless. I urge you to continue reading to
this site, where Matt explains GAs in practise in only 3 pages. After you're through, keep what you've just learned somewhere in the corner of your mind. Next time you get stuck while trying to figure out how to do something in your game, GA might be just what you need

At some point, i intent to throw a big team deathmatch or capture the flag fight using IntenseX bots. One team would be normal IntenseX Professional bots. The other will be IntenseX GA optimized Bots. I think the results will be dramatic, and will give proof of GAs being used on a practical AI problem.
I hope this post gave you a bit of an insight to the magical world that it is Genetic Algorithms. Any comments welcome and desired.
Cheers,
Aris