fogus/gist:6986facef31512cef4eb

## gistfile1.txt
Genetic Algorithms for the PAC-world

PAC-world is inhabited by several species of tiny creatures called PAC-mites, all of which are engaged in a constant struggle for survival with every other species. Each individual mite lives out its short lifetime by following a small set of deterministic rules and interacting only with its immediate surroundings. However, in large numbers, the PAC-mites of a species combine to form complex patterns of behavior which enable them to compete with PAC-mites of other species. Your goal is to design a species that will annihilate every other species in this world in a one-on-one duel.

The laws of PAC-world:

PAC-world consists of a grid of discrete cells measuring 21 cells horizontally by 11 cells vertically. The world is completely surrounded by insurmountable barriers that occupy the outermost cells. Therefore, the actual world measures 19 cells by 9 cells. (In the simulator the barriers are not displayed so only the 19x9 region is visible.)
Each cell may be occupied by either a barrier, a blob (which is an empty cell) or a PAC-mite. The PAC-mites are represented by pacman-like symbols facing in any of the four directions. Each PAC-mite has an age (represented by the number of rings at its center) and is colored according the the species to which it belongs (in the simulator this is either blue or red.)
Each PAC-mite may face in any of the four directions. Direction 0 is udes to indicate a right-facing mite, 1 indicates an upward-facing mite, 2 indicates a left-facing mite, and 3 indicates a down-facing mite. In addition, each mite is 0, 1, 2, or 3 rounds old, independently of direction. Thus, there are sixteen possible configurations for a PAC-mite of a given species.
The contents of PAC-world changes deterministically in discrete steps of time called rounds. This transition function is completely local -- tat is, the contents of a cell at time t + 1 depends only upon the content of that cell and its four neighbouring cells at time t. In this transition, which is described in item 7 below, each mite ages, possibly changes direction, possibly causes a baby mite to be born in the cell that it was facing, possibly dies, or is replaced by a mite of opposite species.
The number of rings in a PAC-mite corresponds to both the age of the mite and its power. A ringless mite has just been born while a mite with three rings has been around for the past three rounds. All mites die after four time rounds so no mite has more than three rings.
Each PAC-mite of a given species shares a common genetic code, which determines its behavior in the transition function. This genetic code consists of 50 genes, each of which may be 0, 1, 2, or 3. Thus there are 4^{50} possible species of PAC-mites. (In this discussion, a turn is a rotation of 90 degrees counter-clockwise; l represents an age between 0 and 3, e is the difference between directions of mites A and B (in the number of turns it takes A to face B's direction) and k is an age between 0 and 2. The genes and their general functions are:
U : If an empty cell has exactly 1 oldest mite facing it, a new baby of that species is born there, U l turns from the direction its mother is facing, where l is the age of the mother.
V : If a mite (she) is facing an enemy mite (he) and is the single strongest mite facing him, he is replaced with a baby of her species, V$el$ turns from the direction she is facing, where e is the difference between his and her directions and her age is l.
W : If a mite survives this round and is facing the barrier, it turns W k times, where k is the age of the mite.
X : If a mite survives this round and is facing a blob, it turns X k times, where k is the age of the mite.
Y : If a mite survives this round and is facing a friendly mite it turns Y ek times, where e is the difference between the mite's and his friend's directions and k is the mite's age.
Z : If a mite survives this round and is facing an enemy mite it turns Z ek times where e is the difference between the mite and his enemy's directions and k is the mite's age.
The transition function can be determined as follows:
A cell containing a barrier at time t also contains a barrier at time t + 1
A cell containing a blob at time $t$ also contains a blob at time t + 1, unless there is a birth into that cell (see U above)
A cell containing a k-ringed PAC-mite at time t will normally contain a k+1 ringed PAC-mite of the same species at time t + 1. There are two exceptions to this rule: (a) if the PAC-mite already has 3 rings at time t, it dies of old age and will normally revert to a blob at time t + 1. (b) if the cell which the PAC-mite inhabits is being attacked by hostile PAC-mites, the normal aging process may be overridden, as bellow.
A cell containing a PAC-mite is being attacked by one or more PAC-mites of a different species at time t is determined as follows:
If all of the most powerful attackers are friendly, the PAC-mite in the cell ages normally, as described above.
If there is a unique most powerful attacker which is of a different species, the baby is replaced by a baby enemy mite (see V above).
Otherwise, the cell is being attacked by at least two different equally powerful PAC-mites, at least one of which is hostile. In this case, the competition for the cell is so intense that the PAC-mite is destroyed, leaving only a blob behind.
Here are a few examples to aid in the understanding of the PAC-world.
Two PAC-mites A and B both face a certain cell, but A has more rings than B does. If the cell contains another mite of A's species, this mite will age normally. If instead it contains a blob or mite of some other species, it will now contain a baby mite of A's species. Simultaneously A and B change direction and age, or they are consumed by some other mite attacking them.
Four PAC-mites, A, B, C, and D aim at the same cell. A and B both have three rings, and C and D have two or fewer rings. If both A and B are of the same species, and the cell also contains a mite of this species, the mite will be allowed to age normally. Otherwise, the cell will contain a blob at the next time step.
Two adjacent PAC-mites A and B of different species face each other. Assuming they are isolated from other attacking mites, they will cause baby mites b and a to occupy the previous sites of A and B respectively. These newborn mites might possibly be attacking each other as well.
The Simulator

The simulator is located in /u/shandy/AI/PacWar. The simulator is executed with the command pacwar.
The Display menu controls the display of the simulation. You have three choices: small, medium, and large, which controls the size of the simulation display.
The Test and Duel buttons allow you to switch between the two modes of the simulation. Test mode allows you to study the behavior of a single species in isolation (e.g., its growth patterns and gross behavior changes upon perturbing sets of genes. Duel mode allows you to run a duel between two species; you can specify the candidate species by selecting from the pop-up menu that appears when you click on one or the other's name.
The Step button advances the current simulation by one round.
A running count of the population of the species is provided in the simulation display. The file {\tt PacWarGuts.c} has the simulator functions you need to write the GA program. The display is set up to help you design appropriate representations for the GA and for you to develop a qualitative understanding of the interactions between the various parts of the genetic code of a species.
The rules for scoring duels between species are explained below. Duels will be help only between pairs of species. Duels will continue until one species has been completely eliminated, or until 500 time units have passed. If neither species has won after 500 time units, the relative populations of the two species will be used to determine the score of the duel. Each duel is worth a total of 20 points. These 20 points will be divided as follows:

20-0 for destroying the opposite species in under 100 rounds
19-1 for destroying the opposite species in 100-199 rounds
18-2 for destroying the opposite species in 200-299 rounds
17-3 for destroying the opposite species in 300-500 rounds
13-7 for outnumbering the opponent by at least 10:1 after 500 rounds
12-8 for outnumbering the opponent by between 3:1 and 10:1 after 500 rounds
11-9 for outnumbering the opponent by between 1.5:1 and 3:1 after 500 rounds
10-10 if neither species outnumbers the other by more than 1.5:1 and 500 rounds
Observe that this scoring system gives significant advantage to species that actually destroy the opposite species rather than just outnumbering them. This is the recommended fitness function for your GA species designer. You can experiment with other scores though.
	Genetic Algorithms for the PAC-world

	PAC-world is inhabited by several species of tiny creatures called PAC-mites, all of which are engaged in a constant struggle for survival with every other species. Each individual mite lives out its short lifetime by following a small set of deterministic rules and interacting only with its immediate surroundings. However, in large numbers, the PAC-mites of a species combine to form complex patterns of behavior which enable them to compete with PAC-mites of other species. Your goal is to design a species that will annihilate every other species in this world in a one-on-one duel.

	The laws of PAC-world:

	PAC-world consists of a grid of discrete cells measuring 21 cells horizontally by 11 cells vertically. The world is completely surrounded by insurmountable barriers that occupy the outermost cells. Therefore, the actual world measures 19 cells by 9 cells. (In the simulator the barriers are not displayed so only the 19x9 region is visible.)
	Each cell may be occupied by either a barrier, a blob (which is an empty cell) or a PAC-mite. The PAC-mites are represented by pacman-like symbols facing in any of the four directions. Each PAC-mite has an age (represented by the number of rings at its center) and is colored according the the species to which it belongs (in the simulator this is either blue or red.)
	Each PAC-mite may face in any of the four directions. Direction 0 is udes to indicate a right-facing mite, 1 indicates an upward-facing mite, 2 indicates a left-facing mite, and 3 indicates a down-facing mite. In addition, each mite is 0, 1, 2, or 3 rounds old, independently of direction. Thus, there are sixteen possible configurations for a PAC-mite of a given species.
	The contents of PAC-world changes deterministically in discrete steps of time called rounds. This transition function is completely local -- tat is, the contents of a cell at time t + 1 depends only upon the content of that cell and its four neighbouring cells at time t. In this transition, which is described in item 7 below, each mite ages, possibly changes direction, possibly causes a baby mite to be born in the cell that it was facing, possibly dies, or is replaced by a mite of opposite species.
	The number of rings in a PAC-mite corresponds to both the age of the mite and its power. A ringless mite has just been born while a mite with three rings has been around for the past three rounds. All mites die after four time rounds so no mite has more than three rings.
	Each PAC-mite of a given species shares a common genetic code, which determines its behavior in the transition function. This genetic code consists of 50 genes, each of which may be 0, 1, 2, or 3. Thus there are 4^{50} possible species of PAC-mites. (In this discussion, a turn is a rotation of 90 degrees counter-clockwise; l represents an age between 0 and 3, e is the difference between directions of mites A and B (in the number of turns it takes A to face B's direction) and k is an age between 0 and 2. The genes and their general functions are:
	U : If an empty cell has exactly 1 oldest mite facing it, a new baby of that species is born there, U l turns from the direction its mother is facing, where l is the age of the mother.
	V : If a mite (she) is facing an enemy mite (he) and is the single strongest mite facing him, he is replaced with a baby of her species, V$el$ turns from the direction she is facing, where e is the difference between his and her directions and her age is l.
	W : If a mite survives this round and is facing the barrier, it turns W k times, where k is the age of the mite.
	X : If a mite survives this round and is facing a blob, it turns X k times, where k is the age of the mite.
	Y : If a mite survives this round and is facing a friendly mite it turns Y ek times, where e is the difference between the mite's and his friend's directions and k is the mite's age.
	Z : If a mite survives this round and is facing an enemy mite it turns Z ek times where e is the difference between the mite and his enemy's directions and k is the mite's age.
	The transition function can be determined as follows:
	A cell containing a barrier at time t also contains a barrier at time t + 1
	A cell containing a blob at time $t$ also contains a blob at time t + 1, unless there is a birth into that cell (see U above)
	A cell containing a k-ringed PAC-mite at time t will normally contain a k+1 ringed PAC-mite of the same species at time t + 1. There are two exceptions to this rule: (a) if the PAC-mite already has 3 rings at time t, it dies of old age and will normally revert to a blob at time t + 1. (b) if the cell which the PAC-mite inhabits is being attacked by hostile PAC-mites, the normal aging process may be overridden, as bellow.
	A cell containing a PAC-mite is being attacked by one or more PAC-mites of a different species at time t is determined as follows:
	If all of the most powerful attackers are friendly, the PAC-mite in the cell ages normally, as described above.
	If there is a unique most powerful attacker which is of a different species, the baby is replaced by a baby enemy mite (see V above).
	Otherwise, the cell is being attacked by at least two different equally powerful PAC-mites, at least one of which is hostile. In this case, the competition for the cell is so intense that the PAC-mite is destroyed, leaving only a blob behind.
	Here are a few examples to aid in the understanding of the PAC-world.
	Two PAC-mites A and B both face a certain cell, but A has more rings than B does. If the cell contains another mite of A's species, this mite will age normally. If instead it contains a blob or mite of some other species, it will now contain a baby mite of A's species. Simultaneously A and B change direction and age, or they are consumed by some other mite attacking them.
	Four PAC-mites, A, B, C, and D aim at the same cell. A and B both have three rings, and C and D have two or fewer rings. If both A and B are of the same species, and the cell also contains a mite of this species, the mite will be allowed to age normally. Otherwise, the cell will contain a blob at the next time step.
	Two adjacent PAC-mites A and B of different species face each other. Assuming they are isolated from other attacking mites, they will cause baby mites b and a to occupy the previous sites of A and B respectively. These newborn mites might possibly be attacking each other as well.
	The Simulator

	The simulator is located in /u/shandy/AI/PacWar. The simulator is executed with the command pacwar.
	The Display menu controls the display of the simulation. You have three choices: small, medium, and large, which controls the size of the simulation display.
	The Test and Duel buttons allow you to switch between the two modes of the simulation. Test mode allows you to study the behavior of a single species in isolation (e.g., its growth patterns and gross behavior changes upon perturbing sets of genes. Duel mode allows you to run a duel between two species; you can specify the candidate species by selecting from the pop-up menu that appears when you click on one or the other's name.
	The Step button advances the current simulation by one round.
	A running count of the population of the species is provided in the simulation display. The file {\tt PacWarGuts.c} has the simulator functions you need to write the GA program. The display is set up to help you design appropriate representations for the GA and for you to develop a qualitative understanding of the interactions between the various parts of the genetic code of a species.
	The rules for scoring duels between species are explained below. Duels will be help only between pairs of species. Duels will continue until one species has been completely eliminated, or until 500 time units have passed. If neither species has won after 500 time units, the relative populations of the two species will be used to determine the score of the duel. Each duel is worth a total of 20 points. These 20 points will be divided as follows:

	20-0 for destroying the opposite species in under 100 rounds
	19-1 for destroying the opposite species in 100-199 rounds
	18-2 for destroying the opposite species in 200-299 rounds
	17-3 for destroying the opposite species in 300-500 rounds
	13-7 for outnumbering the opponent by at least 10:1 after 500 rounds
	12-8 for outnumbering the opponent by between 3:1 and 10:1 after 500 rounds
	11-9 for outnumbering the opponent by between 1.5:1 and 3:1 after 500 rounds
	10-10 if neither species outnumbers the other by more than 1.5:1 and 500 rounds
	Observe that this scoring system gives significant advantage to species that actually destroy the opposite species rather than just outnumbering them. This is the recommended fitness function for your GA species designer. You can experiment with other scores though.