Shareware Overload/ShartewareOverload.cdr/games/ant21.zip/ANT21.INF

Text File | 1991-04-04 | 16KB | 300 lines

ANTS! ant21.exe by Rudy Rucker
Copyright (C) Autodesk 1991.

     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 thescreen 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 theant 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.