GECCO 2008 Contest Problems

Finding a Balanced Diet in Fractal World

The goal of this competition is to evolve an agent to search a landscape and find as much as possible of two types of food. The landscape consists of a 256x256 grid. Each cell has an 'elevation' between 0 and 255 (see image below - cells in the image are shaded by elevation, brighter is lower). Two types of food are in this landscape: grain - green dots, and game - gold dots. In addition, red squares represent impassible terrain.

Sample map, brightness defines elevation, green dots represent grain,
gold dots represent game, red represents impassable areas.

The agent's goal is to find a balanced mixture of grain and game. Specifically, for the competition an individual's fitness is the amount of whichever food it finds less of, e.g. if an agent finds 35 grain and 29 game its score is 29 (and higher scores are better). Individuals are allowed 13,107 moves (20% of the total number of grid cells, thus exhaustive search will not be particularly effective).

Individuals can 'see' elevations in a 5 by 5 grid around their location (see below). They automatically pick up food if they enter a square containing it, but cannot see it. Thus, individuals must learn where to look based on elevation.

Individuals start on a random cell.

What to Submit

Contestants are required to evolve an ANSI-C function whose prototype is:
int Next_Move(int *grid, int grain, int game, int last, int time);
Grid is a pointer to an integer 1D array holding the elevations of the cells immediately around the individual. The values in the array correspond to the surrounding cells as follows:

Numbering of cells for movement
0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

e.g. the 7th element of the array stores the elevation of the cell directly North of the individual, the individual is in cell 12.

The values are in the array are between 0 and 255 (the elevation) for cells on the map and -1 for impassable cells and cells that are outside the map. The arguments grain and game are the amount of each collected so far. The argument last records what was collected on the last move: 1 if grain was collected, 2 if game was collected, and 0 if nothing was collected. The argument time is the amount of time steps remaining before the end of the test.

The function should return the individual's next move, defined according to the same image above. E.g. returning a 3 causes the individual to move two cells to the North. (Note that individuals only pick up food in cells that they move to, not in intermediate cells. Thus, if there were food in the cell labeled 8 and the individual moved to cell 3 the individual would not gather the food.) Returning a 12 would cause the agent to remain in its current location - probably not very useful.

If an individual attempts to move off the map it remains in its currently location, but this still counts as one of its allowed moves.

Contestants must submit:

their ANSII-C function
a PDF document containing a brief description of the evolutionary process used to evolve the function, including a description of the representation used, and a description of the 'original' encoding of the individual's code, e.g. the original, evolved program tree in a GP.

Sample Maps

For training files defining 10 samples maps are supplied below. Each map is represented by two files, the first is contains the elevation of each cell in the map, the second defines the location of food, 1 for grain, 2 for game, 0 for nothing.

Training maps
Elevation Map	Food Map
map 1	food map 1
map 2	food map 2
map 3	food map 3
map 4	food map 4
map 5	food map 5
map 6	food map 6
map 7	food map 7
map 8	food map 8
map 9	food map 9
map 10	food map 10

Judging

Each submission will be judged on performance and evolutionary quality. Performance will be measured on randomly generated 10 test maps (all submissions will be tested on the same test maps) with the individuals starting in random locations. Evolutionary quality will be based on the 'human independentness' of the evolutionary process. E.g. an evolutionary system that includes a human designed basic operator that systematically searches the local space will not score as a high as one in which the same behavior is evolved from more primitive operations.

Questions about these pages or the problems themselves can be sent to [Terry Soule] or [Robert Heckendorn]