This is an artificial life program inspired by the notion of "an electronic ant farm." The ants are active graphics objects that are deterministic finite state machines with multiple inputs and outputs.
Numerous program parameters can be adjusted by using keyboard "hot keys."
The ants interact with the environment through a single pixel-sized read/write head. An ant's "body" is normally drawn as a single white pixel at its head location. There is also the option of showing an ant's body as a colored string of dots. In this case the string's direction is the ant's current direction of motion, and the string's color corresponds to the ant's current state. You can toggle between the two body representations with the T key.
The ants leave trails which are either a) single colored dots, or b) colored line segments connecting two successive ant positions. The I key toggles between these two trailmodes. Normally, all ant-trails "evaporate" or disappear after some fixed number of steps that is controlled by the "traillength" parameter, adjustable by using the L and Shift+L keys. One can toggle the trail-erasing feature off and back on with the Shift+T key.
With each cycle of the program each ant calculates where to move next and what kind of trail mark to leave. The ant bodies are then erased and replaced with the correct trail marks. Each ant then "looks" at the color of the pixel found at its new position. Once this information is stored in their "brains," the ants redraw their bodies onto the screen. Then the cycle repeats itself, with each ant using its new information to calculate where to move next and so on.
The ants are grouped into 1 to 6 colonies; each colony has 2 to 7 ants. At startup we have four colonies of five ants each. In EGA or VGA mode, ants in the same colony all have the same color trails, and no two colonies have the same trailcolor. In CGA mode there are only three possible trail colors, so different colonies may have the same trailcolor. In general it is better to just use three colonies in CGA mode.
An ant's calculation is really a set of lookup tables which take as input i) the ant's present state number and ii) the "readcolor", which codes the color the ant's present pixel was before the ant moved to it.
The outputs of an ant's lookup table calculations are: i) the ant's new state number, ii) the "writecolor", which is the color or trail mark which the ant will leave on its current pixel, iii) the direction change, which is an amount by which the ant changes its direction, and iv) a (positive or negative) change in the ant's running score.
The score change is a fixed function of the readcolor, and the function is the same for all ants in a given colony, so the computation of the score change is not really part of the behavior of an individual ant.
Our ants have up to 256 states, and move in up to 128 directions --- though the available number of directions N can also be set to 4, 6, 8, 12, 16, 32, or 64. If an ant has N possible directions, a "change in direction" has the form TURN LEFT 360 * I / N DEGREES, where I is a number between 0 and N-1. As our directions are given in terms of a horizontal and a vertical pixel move, the idea of degree is only a way of speaking; in fact what a change in direction really does is to move an index through two tables of possible x-changes and possible y-changes. In the 16-direction case, we tried two different pairs of tables, one of these is distiguished as the "fast 16" direction table.
If an ant is about to move onto a wall cell, then we forbid the move and make the ant bounce back to the cell it started from. In this case, however, its readcolor is set to wallcolor, so the ant knows it has bounced off a wall. In all other cases, the readcolor is based on a new cell which the ant actually moves to.
An ant distinguishes among seven kinds of readcolors: blank, its own colony's trail color, a prey colony's trail cells, a predator colony's trail cells, walls, food cells, and crap cells. It treats the trail cells of those alien ants who are not predator or prey as no different than blank.
An ant has three writecolor options: leave a blank, leave its own trailcolor, or leave a crap cell. Some design decisions that cut down on the range of possible ants are the following: if the readcolor is blank, the writecolor is always the ant's own trailcolor; if the readcolor is a predator or prey trail cell the writecolor is always blank; if the readcolor is foodcolor or crapcolor the writecolor is always crapcolor. If the readcolor happens to be the ant's own trail color, the ant has a choice of whether leave the cell alone or change it to a blank. Thus it can erase its own trails or not.
As mentioned above, we store our ants as three lookup tables that exhaustively specify an ant's output for each possible input. These tables are in effect an ant's genetic material. Two doubly indexed arrays specify the output state and the change in direction as functions of the input state and the readcolor. And for the cases where the readcolor is the ant's own trailcolor, there is a singly indexed array to specify the writecolor as a function of the input state. The array entries are (inefficiently) represented as bytes. If there are S states and C possible readcolors, this means that the an ant's genetic material consists of (2*C+1)*S bytes. In the general case, C is 7, so the gene size is 15*N, but in the cases where there are no walls, food, or crap, C is effectively 4, and the gene size is 9*N. Values of N as low as 2 (or even 1!) can give quite interesting behavior.
When you use the hot keys or the parameter control menu to change the colonies' state count, this is done with as little change in the genes as possible. In particular, when you change from N to 2*N states, this is done simply by copying the N old state behaviors into N new states. As time goes by and mutations take effect, the new states may come to act differently from the old ones. In the passage from 2*N to N states, the lookup tables for the low N states are used with all mentions of states K higher than above N replaced by K/2. Similar tricks are used when you change the direction counts --- the goal in every case is to try and preserve as much of the ants' personalities as possible. One method for evolving good ants which has worked in the past is to evolve a world at some low state count, to then double the state count, let the world re-adjust, perhaps continuing this process through several iterations. Another interesting thing to do is to cut a highly evolved many-direction world down to a low-direction world; much of the many-direction behavior will carry over, at least for a time.
The ants remember and erase their own trails. The "traillength" can be set as high as 800. After an ant has turned on 800 pixels it begins erasing the oldest of its trail dots before turning a new pixel on. Using self-erasing trails keeps the screen from getting completely covered, and has the pleasant side-effect of making an ant and its trail appear as a single entity. In the food regions of the screen the old crap cells are eventually restored to food cells, so the food never runs out. ( If you overlay food onto an ant's trail, the food will have black holes in it where the colored trail was because the trail "remembers" having been written over black cells and restores itself to that state. ) The pixel locations are integers, so the trail information uses 3200 bytes per ant.
Taken together, the gene and trail requirements come to about 7K bytes per ant. Our program allocates room for up to 42 ants, which is a net runtime memory demand of about 300K.
There are two basic kinds of "games" the ants can play: FreeForAll or EatCycle. In the FreeForAll game, each ant regards all other colonies as its prey, and its score is increased by the preyvalue for each alien trailcell it lands on. In the EatCycle game, each colony regards the trails of the colony with the next higher index number as predators, and the trails of the colony with the cyclically next lower index number as prey. Thus if you had four colonies numbered 1 through 4, colony 1 would prey on colony 4, be preyed on by colony 2, and be indifferent to colony 3. Typically the value of a prey cell is +2 and the value of a predator cell is -1, though other values can be set. It is better not to have predator and prey values equal, as the game is then "zero-sum" and dull ants who do nothing at all score as well on the average their more active colony-mates!
Additional effects on the ants can be gotten by putting food and wall cells on the screen, and assigning various score values to these kinds of cells. Note that if you turn the wrap off, then all the offscreen cells are thought of as wall cells. If an ant steps onto a wall cell, it is moved back to the position that it just stepped from, and if wallvalue is negative, then the ant has its score level reduced as well.
If you press the K key the program will draw a randomly positioned spiral maze on the screen with food cells at its center. If you press the J key the program will overlay an ellipse of food onto the screen.
The antcolonies available directions can also be varied. At present, this is changed for all the colonies at once. 1 makes all be 4 direction ants, 2 makes all be 6 direction ants, 3 for 8 direction, 4 for 12, 5 for 16, 6 for fast 16, 7 for 32, 8 for 64, 9 for 128, and 0 makes a mixture.
At startup, or after you press the Shift+X key, the ants' genetic lookup tables are randomly filled with appropriate values, each ant is set into state 0, each ant's readcolor is set to 0, each ant's current direction is randomized, and each ant is drawn on screen. Next the ants begin repeating the cycle : compute new outputs, erase self, post outputs, change location coordinates, read inputs, redraw self. After some set number of cycles, the ants of the individual colonies are ranked within the colony. (The set number, called "breedtime" starts out at 2K.)
Once the ants in each colony are scored, the ants are ranked from highest to lowest score. If all the scores are zero, then the ants' rankings are not changed. The scores displayed on the screen at this time are the average score per ant of each colony. Zero to three of three kinds of "reproduction" are then applied within each colony.
1) SEX The worst ant is replaced by a "sexual" combination of the best two ants. The sexual combination is achieved by having the child ant act like parent #1 in about half of its states, and act like parent #2 in the rest of its states.
2) CLONING The gene array of the best ant are copied into the gene array of the worst remaining ant. The cloned gene array is then MUTATED by changing a certain percentage of its entries. How big a percentage? Each colony holds a variable called "temperature". If the colony's temperature is 0, then none of the clone's entries are mutated, and if the colony temperature is 100, then all of the clone's entries are mutated. We start all colony temperatures out at 10. Whenever a colony comes in last in the overall score average it's temperature is incremented by 1 (up to a limit of 20), and if a colony comes in first in overall score its temperature is decremented by 1 (to as low as the "frozen" value 0).
3) ZAPPING The worst remaining ant has its gene tables completely rerandomized. This is effectively a 100% mutation.
If we have five or more ants, then all ants better than the third worst ant are left undisturbed. For each colony, you can select which combination of CLONING, ZAPPING, and SEX you want that colony to use in its breeding. This is done using the Shift + a number key.
We do not yet have any firm data on which combination of evolutionary methods works best. One would expect that the fastest evolution happens if you use all three, but one certainly gets more stable colonies if only SEX is used. If you find a colony whose appearance you particularly like, you can preserve it for awhile by turning all breeding methods off, thus leaving its genepool unchanged from cycle to cycle.
The ants can evolve purely according to their skill at the "game" they are presently playing, or the user can influence the ants according to personal criteria. In order to breed your own idiosyncratic strain of ants, set the values of prey, predator, food, crap and walls all to zero, using the active parameter change menu (accessed by pressing the Y key). The ants' only source of score points will now be the scores you give them. The way in which you change an ant's score is to move the mouse. Whenever you touch the mouse, the ants stop moving and a white square cursor becomes visible. You can still move the ants a step at a time by pressing the space bar. To reward or punish a particular ant, you move the mouse square until it includes the head of the ant you are after, and then you left click to add 1000 points to that ant's score, or right click to subtract 1000 points from that ant's score. If more than one ant head is in the selection square, the select operation will be disallowed. You can tell when the score changing works because the machine makes a high noise when you add score and a low noise when you subtract score. After touching the mouse, you must press ENTER or press both mouse keys at once to make the simulation start running again.
You can also use the mouse clicks to encourage or discourage individual ants even if the other scoring possibilities are active. If there are no other scoring possibilities, however, then an ant which you select at the best ant will keep its position as best ant of its colony ( and thus will keep being the ant who is mutatedly cloned ) until you change things with further selections.
You can save parameter files that include all the parameter settings, plus the value of the seed which was last fed to the randomizer, as well as the positions of any globs or mazes. These are called *.anp files. They are only about 100 bytes each. If you load the same *.anp file twice in a row, you will see the same evolution of ants.
If you have used mouse selection and have made on-the-fly changes to the running of the ants, then the only way to be sure of getting the same ants back is to save the whole ant world, meaning the parameters plus the current genetic information of the ants. We call these files *.anw files. If the ants use 8 states each, the *.anw file is about 3K. If the ants use 256 states each the *.anw file will be about 500K. If there is not enough room on your disk for an *.anw file, it is possible that the program may crash.
Note that if you have let an ant simulation run for a very long time (several days), you will also want to save the information as an *.anw file so that you can immediately come back to the point you'd evolved to.
You can go into an *.anw file with your text editor and examine the ants' gene tables, possibly also changing them by hand. When doing this, you must be sure to leave the file in the same format, not adding extra carriage returns, etc., or the program will crash when this file is reloaded.
The idea for these ANTS was arrived by applying the artificial life notion of genetic algorithm evolution to the idea of deterministic two-dimensional Turing machines (which have been called Vants by Christopher Langton and Turmites by Keewatin Dewdney). The particular design choices used here are the result of a good bit of experimentation by the author, aided by his students at San Jose State University and his colleagues at Autodesk, Inc.
