Cellz was a programming competition for the GECCO 2004 evolutionary computation conference. Basically the goal of the competition was to design a controller capable of getting the most points over averaged over 10 trials of 1000 time steps. The game starts with a number of food particles, and the controller must move to collect (by touching) the food particles. Once enough energy is collected by a cell it divides into two cells which then continue the process of collecting food and dividing. Each cell has the same underlying controller or state machine, and thus some some kind of competitive or cooperative strategy must be devised.
The controller is nothing more than a static directed graph structure using a few basic functions (min, max, rand, const, sum, prod, tanh). At each time step, the controller is provided with 19 inputs including an eight-dimensional directional vector for food and other cells (eight points of the compass), current x and y velocity in the two-dimensional environment and current mass (size given the amount of energy/food consumed thus far). The maximum nodes permitted in the graph is 250, thus the complexity of the controllers is low enough to have then developed by hand and or by some search strategy.
A competition page was provided with a useful introduction and an example applet demonstrating a simple cellz controller. Detailed instructions were provided for developers, as were general rules for the game environment. Controllers could be submitted online (and still can be), and a leader board was provided for bragging rights. The competition ended before the conference, and the final results are available here, here and here (I devised the winning controller).
The first few solutions involved various multilayer feed-forward artificial neural networks. The structures were fixed (designed by hand), and the weights were trained with a genetic algorithm (I used ECJ for this purpose). The network structures were provided with the food and cell sensor vectors as input and output a directional vector which was then scaled by a constant value to become velocities. Results for these initial structures were poor.
After the poor results obtained with simple structures, more complex multilayer network structures were designed and trained both with back propagation and genetic algorithms. These structures consisted of hierarchical feed-forward networks that would calculate an x velocity which was then fed into a second network to calculate the y velocity. Results for these solutions were also poor.
In the software package provided was an example greedy controller written in Java called GreedyControl. This controller worked by selecting the closest particle and outputting a velocity vector that caused the cell to head towards that particle. The strategy produced results superior to any of the structures I could come up with, so I decided to see if I could model what the greedy solution was doing using the limited directed graph representation required for the competition (the greedy controller was an example provided to test the API and was written in Java, it was not confined to the directed graph representation required for submission).
The problem of modelling the greedy controller could be broken down into two parts; 1) selecting the closest particle, 2) setting a direction and magnitude for the output velocity vector.
The first part of the problem was deceptively difficult. In code, it can be addressed using a simple search routine, though in the limited repertoire of mathematic functions, it required all kinds of transformations and scaling which ultimately ended up using nearly 130 of the 250 nodes allowed for the directed graph structure.
The second part of the problem was much simpler. After analysing the decisions made by a running greedy controller, it was determined that it made only a very limited number of decisions (output velocity vectors). Given the result of the selected direction solved in the first part of the problem, the second part of the problem was solved using two parallel network structures which took as input the selection made in the first sub problem. The weights were trained using a genetic algorithm, and the directions output matched identically those made by the hard coded greedy controller.
The submitted solution can be downloaded from the competition results website. I have provided the solution here in an excel spreadsheet in which it was developed. The spreadsheet allowed the specific graph structure to be hand coded most efficiently and permitted easy debugging. The weights evolved by the genetic algorithm were simply pasted into the appropriate constant nodes in the graph structure. Although the solution is nothing fancy, the thing I am most proud of is all the messy transformations required to get the selection sub-problem solved - the only reason I'm proud is because of the time I required to sit there with pen and paper to get it right.
The spreadsheet is available here: New_Func_v1_directed_graph.xls.