Genetic Algorithm

Download this game. Build it (by running the build.bash script, or by doing "javac *.java"). Run it ("java Game"). You will see two teams of robots battle to destroy the other team's flag. The blue team will win.

The blue team is powered by a "reflex agent". That means it contains a bunch of hard-coded human intelligence. The red team is powered by a "neural agent". That means an artificial neural network directs its behavior at a high level. (At a low level, both agents use reflex logic.)

Your task in this assignment will be to make the neural agent better. When you are successful, it should beat the reflex agent.

Become familiar enough with the code that you get the general idea of what's going on. The code for the reflex agent is found in the file ReflexAgent.java. This code should be fairly easy for you to understand. The code for the neural agent is found in the file NeuralAgent.java. It would be a good idea to "diff" these two files, to see how they differ. The file Game.java contains starts the game. This is where you will put your code. In this assignment, you do not need to worry about the other files, but you are welcome to examine them if you are curious. I will also introduce this code to you in class.

Learn about genetic algorithms. I will go over them in class. If you would like some more detail, Section 4.1.6 of this book talks about them. Wikipedia has an article about them. There are also many tutorials on the web that you could Google for.

Implement a genetic algorithm. Here is some basic pseudo-code for a genetic algorithm:
```
Initialize a population of virtual chromosomes.
do for a long time:
	(1) Promote diversity within the population.
	(2) Select the "more fit" chromosomes to survive. Kill the "less fit" ones.
	(3) Replenish the population.
```
The Matrix class is a good data structure for representing a population of chromosomes. I would use each row to represent one chromosome.

(1) For promoting diversity, please implement mutation. For each member of the population, choose some probability that it will be mutated. To mutate a chromosome, draw a random value from a Gaussian distribution, multiply it by some deviation, and add it to a random element of the chromosome.

(2) For natural selection, choose several pairs of chromosomes and call Controller.doBattleNoGui to make them fight. With some probability greater than 50% let the winner of the battle survive and kill the loser, else let the loser survive and kill the winner.

(3) For replenishing the population, please implement cross-over to produce new chromosomes that replace the dead ones. Randomly choose the first parent. Randomly choose a few chandidates for the other parent. Pick the one most similar to the first parent. For each element in the child chromosome, randomly pick one of the two parents to supply its value.

This algorithm requires several meta-parameters (such as the mutation rate, the average deviation of each mutation, the number of tournaments to conduct, the probability that the winner survives, and the number of candidate mates that are evaluated for cross-over). Use your intuition to determine some good initial values for these meta-parameters. Add some additional elements to your chromosomes to encode these meta-parameters, and adjust your code to get them from the chromosome. (This way, the meta-parameter values can evolve with the population.) You will need to cut off these extra values before you return the weights for the neural network.

(There are many other operations that you may optionally implement if you want to make your genetic algorithm a little bit stronger. Some of these include: cloning, interpolation, extrapolation, catastrophic mutation events, speciation, continental separation, multiple-point cross-over, and fitness-proportionate selection. It is perfectly acceptable to make up your own operations too.)

Evolve a set of weights that will cause the red team to win. You may decide how many generations are necessary to evolve a good population. You should be able to beat the reflex agent. When you achieve that, comment out the line that calls your genetic algorithm, and hard-code the weights that you evolved, so your program can begin the tournament immediately.

Make a chart that shows progress over time. Be sure to use some continuous measure of fitness so that it can continue to improve after it barely achieves the goal. (For example, you might consider the amount of time your agent takes to beat its opponent in your evaluation of fitness.) At regular intervals during the evolution of your population, print the fitness value of the most fit member of your population to the console. Or, alternatively, you may want to plot the percentage of the population that can beat the reflex agent. Any measurement of fitness will be fine for this assignment. Use these values to make a chart showing fitness over time. (For example, you might paste them into a spreadsheet program to do this.) Save your chart with the filename "chart.png" and include it in your submission.

Zip or tarball your source code in the usual manner. Don't include any generated binary files in your archive. Your build script should build, but not execute the tournament. When your code is executed, the game should begin immediately, without doing any evolution, and the neural agent should prevail. Click on the "Project submission" link on the main class page to submit your archive file. If you have any difficulties with the submission server, please e-mail your submission directly to the grader.