Genetic Algorithms

There is a lot of talk about methods that evolve to change(and improve), however, how does one go about building such a model.

For example, if there is a zero sum game, then, one would hope that starting with a random strategy, the algorithm will work itself to the optimal strategy. Say for the example of nim, or similar games, is it possible to write an algorithm that can figure out the best strategy using the principles of evolution?

I found a paper that offers a method for nim, can someone explain what the paper is saying or guide me to references that will make it easier to understand the paper, and how one can go about building such an algorithm.

-
You edited the question so my answer looks incomplete, so I'll delete it. –  Douglas Zare Apr 6 '11 at 4:19
I'll be interested in knowing the mathematical basics needed to even think about such a thing. Hasn't this to do with Machine Learning? –  Amit L Apr 6 '11 at 5:56

The most basic Evolutionary algorithm is probably a binary encoded genetic algorithm.

Its fairly simple to understand.

Say you are looking to find out what the maximum value of a 4 bit binary number is. Yes a silly question its obvious but it makes it easier to follow than using a game like nim or a lot of other things

First you create a population of solutions at random for example
0001
0010
0000
1110
0111
1001

then you would run them through a simulation that finds the fitness of each individual. Basically you are assessing each solution to see how good it is. In this case its simply adding up the binary values.
0001 = 1
0010 = 2
0000 = 0
1110 = 14
0111 = 7
1001 = 9

So here the strongest individuals are the last 3

Next you want to select the strongest via some selection process. There are many different ones for different styles of problems the most basic is elitism which is basically pick the best. These will be used for breeding to gain the next population

so lets pick
1110 and 1001
for a start

with these we now do crossover. Again there is lots of different techniques for different problem encodings but for this we will simply break them into 2 parts and stick them together again.

so we can pick a random location on in the 2 individuals for simplicity lets pick to split in the middle

parents
1110 -> 11 | 10
1001 -> 10 | 01

then swap them to get 2 new individuals
offspring
1101
1010

we now do this a few more times to get a new population. Again for simplicity lets make the population the same size.
parents
1001 -> 10 | 01
0111 -> 01 | 11

offspring
1011
0101

parents
1110 -> 11 | 10
0111 -> 01 | 11

offspring
1111
0110

so our new population is
1101
1010
1011
0101
1111
0110

the next part is random mutation. Basically you change something randomly. It has a low frequency of occurrence but is essential to making an effective evolutionary strategy.

so lets pick the 4th individuals highest bit. so the 4th individual is 0101. the highest bit is a 0 so we just swap it to a 1. so the 4th individual is now 1101 and the population becomes
1101
1010
1011
1101
1111
0110

the final stage in the loop is the stopping criteria. Again lots of ways of doing this depending what your doing. A simple one is to have a stopping criteria when the fitness of an individual is strong enough. So all we do is again assess the fitness of each individual
1101 = 13
1010 = 10
1011 = 11
1101 = 13
1111 = 15
0110 = 6

so our strongest individual by chance (honestly it was by chance) has reached the maximum value of a 4 bit binary number. Our stopping criteria could have been to reach some number or higher. Important to note is the average fitness of the population in the 2nd generation is much higher than the 1st.
If we did not get the stopping criteria we would continue the loop of select -> crossover-> mutate -> evaluate -> check stopping criteria.

I have no idea if this answers your question but this is about as basic an evolutionary algorithm as you can get there are a lot of different problem encodings, selection methods, crossover methods, mutation methods and stopping criteria. Further than that is multiobjective optimisation where multiple goals are trying to be solved. That is pretty much where the field is right now. These algorithms are pretty bad if you can model the situation well enough to find a solution yourself. They are very good at finding a solution when you know what a good solution is but not how to get there. They are insanely computationally expensive.

If you want to know more start on the basics of genetic algorithms they are the simplest and easiest to understand evolutionary strategies. like said its a form of machine learning and falls under computer science although a number of mathematicians have taken up the subject.

-
Note that the choice of fitness criterium is essential for EA's performance. There is a multitude of functions that are maximal in $1^n$ but expected runtime varies a lot. Also, mutation is usually done by flipping every bit with probability $p$ (often $1/n$). –  Raphael Apr 10 '11 at 10:18
I found this to be the clearest introductory definition of a genetic algorithm I've seen, thanks! –  Danny King Apr 12 '11 at 8:22
The next step will be to choose something you want to encode for the algorithm to work with. The two most obvious (only?) things you can model (or use to model) are actions to take within the game, and current/previous game state/actions. One way to handle it could be to use your genetic sequence to weight how important information is about current/previous game states and previous moves, then use some type of weighted sum to determine future moves. The paper you linked to probably describes the encoding they used. –  Brian Vandenberg Apr 12 '11 at 16:53