Evolving Digital Warriors

I. Problem:

In my experiment, I intend to explore the field of Artificial Life or more particularly Binary Biology, or Binology. The only distinction between the two is that I am not going to attempt to recreate organisms that already exist in a real environment. I will evolve digital organisms that are meant to be in their native environment of the computer. I will use the computer model of Corewars for this experiment (more on that in Research section) Using Corewars, I will attempt to "evolve" digital warriors in an attempt to answer the whether evolving digital organisms is possible. Hopefully, I will find that I can start with randomly created code and produce warriors that can defeat man-made warriors.

II. Research:

Artificial Life may be seem to be a foreign field to some people. You most likely have seen the product of Artificial Life if you have seen many movies in that past few years. Artificial Life algorithms have been used to produce animal flocking scenes in Batman, Jurrasic Park and the Lion King to name a few.

Put simply Artificial Life is the study of man-made life in computers and other mediums such as robotics. Generally these man-made organisms are reproductions of organisms that already exist in a real environment. This is so that scientists may better understand how organism work neurologically.

Artificial Intelligence may be something that most people are much more familiar with. If you have ever played a video game against a computer opponent than you have met an Artificial Intelligence algorithm. There are many similarities between AI and AL but the biggest difference between them is that AI is working toward machines that in effect act like intelligent beings. AL works toward what makes organism, intelligent or not, tick and how can that be reproduced on the computer.

My first encounter with Corewar was in the book Thinking Machines that I found at the library. It was discussing artificial life simulators such as Corewars. I found this somewhat interesting and then forgot all about it. Then, months later while on the Internet, I found PMARS which suddenly refreshed my memory about what it was and I downloaded it along with every paper, tutorial and utility I could find. I played with Corewar for a while again losing interest but not before I read a paper by John Perry, a UCLA student of Computer Science, who had "evolved" Corewarriors in an attempt to simulate life.

When I started thinking about science fair projects earlier this year, I knew I wanted to do something in Computer Science. Computers fascinate me and since not many people do computer science fair projects, there was a lot of opportunity out there for good, new projects. Corewars seemed like a perfect choice for a science fair project.

Corewars is a type of artificial intelligence game popularized by a man named A.K. Dewdney. After its introduction in a 1984 Scientific American article, it gained interest from all over the world. The original game called 'Darwin' was actually developed by Victor Vyssotsky, Robert Morris Sr. and Dennis Ritchie in the early 1960's. Even after almost 2 decades, the game is still played, studied and modified.

Corewars basically consists of two computer programs loaded into a "virtual computer". Like computer viruses, these computer programs fight for control of the "Core" or system resources and memory. These programs are written by programmers in a language named RedCode.This language is not unlike the complicated Assembly language that almost directly talks to the processor of a computer. These commands are interpreted by the "virtual computer" called MARS which stands for "Memory Array Redcode Simulator". MARS acts like a processor and keeps the programs from actually damaging the real computer.

Traditionally the computer warriors of Corewar are written by programmers. These programs are internationally fought against each other and monitored by a organization called KOTH (King of the Hill). As time progresses, the programs grow in complication. No longer are there KOTH winners of 5 or 6 commands. Now these programs are up to 100 commands long.

III. Hypothesis:

If I randomly create warriors, battle them and breed the winners then eventually more advanced warriors will evolve which will be able to defeat man made warriors.

IV. Materials:

V. Procedure

Simply put, my procedure would be about four steps. First, generation 0 would be ranomly created. They would then be fitness tested. The most fit of the population would then be allowed to propagate resulting in the next generation of warriors. They would then be fitness tested, etc. The procedure in detail is much more complicated.

The first thing to do in beginning this experiment is to learn about pMARS options so that I may adjust the environment my warriors will compete in. I learn the redcode syntax so that my random warrior program will make warriors with legal instructions and find warriors to fitness test my evolved warriors against. All this is accomplished by looking though the wealth of information about Corewars on the Internet. I found multiple tutorials on redcode and Corewars in general.

Next would be the actual development of the software for random warrior creation and breeding. This I did in Turbo Pascal. After debugging and multiple revisions, they are ready for the actual experiment.

  1. First in the actual experiment, I would start up Turbo Pascal and have RandRed and BreedWar loaded. I do this instead of actually compiling the programs because having the source code open like that allows me to adjust things like number of commands, range of arguments, mix of commands, number of warriors and names of warriors for archiving.
  2. After loading up the programs I shell back to DOS so that I can switch back to the Corewar directory. I make a work directory called Breedwar that I actually do all the work in. While in this directory, I exit back to TP and run the RandRed program which produced 50 randomly created warriors for the 0 generation. This takes just a few seconds and then I shell back to DOS. I then create a file that contains all the names of the warriors (example: WAR01.RED, WAR02.RED, DWARF.RED etc.) this is so that it is not required that I type in the names of the warriors each time I evoke MTS (tournament scheduler)
  3. I set the pMARS environment as -r 3 ( 3 rounds) and -c 30000 (30000 processor cycles until tie). This keeps the average battle time to around 15 minutes depending on number of ties which take longer. Then MTS is run and the warriors battle it out.
  4. After MTS finishes the battle, I read the scores file (SCORES.MTS) and look to see what the results are. Typically, the man-made warrior will be on top, almost always never losing but sometimes tieing. I take the two warriors under that even though most of the time the top 15 or so are tied so any of those 15 would at least phenotypically be the same.
  5. I zip up all the warriors and scores into one singe file in case I wish to go back to them later and put them in a different directory. I then delete all the *.RED files except the two that I choose to keep and the man-made warrior. I then rename the two warriors as WAR01 and WAR02 because I designed BREEDWAR to breed those two file names.
  6. I then exit back to Turbo Pascal, run Breedwar and then shell back to DOS. I now have 52 warriors in the directory now including the two of the original generation. I run MTS and watch while the new warriors battle it out.
  7. I repeat processes1-6 for about 4 generations depending on the number of ties at top. If all of the warriors are tieing but none are touching the man-made warrior then I usually start over.

VI. Observations & Results:

2/16

Sheets 5&6 both war4 generation. Experiments in cause of multiple tieing and no real winners. Probable cause: warriors just sit there not moving. hence tie. The ones they beat lose because they kill themselves-illegal operations like DAT statements.

Sheet 4 - first winner! sometimes ties tornado.

possible solution to tie problem: change random generation code to allow for controlled mixture of instructions less NOP etc.

First vs. all rank almost irrelevant, scoring unbalanced

New Instr. Mix

Mov25%<=25
Add5%>25<= 30
Sub5%>30<=35
Jmp20%>35<= 55
Jmz15%>55<= 70
Jmg15%>70<= 85
Djz5%>85<=90
Cmp5%>90<= 95
Dat2%>95<= 97
Nop3%>97<=100

1st of new generations (sheet 8) no improvement

2/22

Change in Pmars command line options 30000 cycles till tie. This Decreases battle time. More generations per hour possible.

New experiment: 8 instructions fight against: Dwarf, AAimp, imp & Antimp.
War16 is first
War17 promising results
Breed War17 #34 and 05

gen. 2 or war17 14 warriors beat them all

gen. 3 made of 1 & 104

gen. 3 - 35 ahead of A.K.'s

Experiment success!!!!
warriors have evolved to beat a man-made warriors. Extremely simple warriors however.
Try breeding previous attempts

40 and 03 or war 13 against tornado

result - 46 way tie. Conclusion: not good features of 40 and 03 passed on ability to do nothing.

W2- try 01 from war6 and 40 from 4
Interesting 2-9 tie. Tornado was tied a few times. 01 and 02 are not among the winners. They & everybody below 9 is tied.

W3 - 3rd generation will be 102 & 112
Top 25 tie (except for Tornado) w ho tied 49%.

W4- Try again with gen3 01 & 101
top 20 tie Tornado score 39% tie

W5- Try again with 01 &01
top 30 tie . Tornado 59% tie

W6 use 02 & 103 gen. 5
2 through 37 tie 100% of time
01 is #38 2% lose - bulk of population better than parents.

W7 - 02 & 102

!!!! Big blunder, finally realized that past 6 generation useless. Never remodified Breedwar to do more than 8 instructions. Start over.

W2 - 01 from War6 40 from war4
2-12 tie 100% 1&2 not among all rest tie with 48 pts.

W3- 101 & 106
2-26 tie 98% tie
01 & 02 below 26 107 lost 100%

W4- 101 and 103
2-28 tie with 100 tie 02 has 98

W5 - 01 and 102
2-29 tie with 100 tie
01 and 02 are tied 98%

W6 101 and 102
2-20 tie with 100 tie
No progress with this generation 01 and 02 are at top.

Try new population now. Will add mutation to Breed War also reduce instruction to 15. {Mutation never accomplished}

W1 - 2 -18 tie 64 -2 -34 breed with 03 & 04

3/1

Another stupid Mistake !!! Breeding program flawed. Only copied beginning of warriors, end ignored. Start over again

New environment settings: -b -r 100 -c 30000

Gen. 1 against tornado
No good, top 20 tie. Take to long change to -r 25

Gen. 1 Top 20 score 2550
try 01 and 07
2-42 tie Try new generation, again
Try #40 and 03 or gen. 13

Gen. 1 no improvement 01 and 02 at top. Try again with tem.

Gen2 top 43 tie. This is going nowhere.

Gen1 1 from war6 40 from war4 - only real progress came from this
5 way tie. 1 and 2 not at top. Will try next with 102 and 113

Gen2 4 way tie at top with 100% ties.
Try again with 111 and 112

Gen. 3 5 way tie. 01 and 02 not at top. Try again with 124 and 126

3/2 gen4 top 9 tie with 100% tie all ahead of 01 and 02

Try attacks on Dwarf again now with fixed breedwar.

gen1 - Top 13 tie 74 0 26
next gen. with 01 and 06

gen. 2 Top 40 tie 20 0 80
Stop here. Traits to tie Dwarf are only things being passed on. Start with new P generation.

Gen1 Top 18 tie with Dwarf suspect tie syndrome again. I'll try a few more generations
01 and 04

Gen. 2 Top 49 tie. How boring. Definitely tie syndrome. Perhaps dwarf is a bad choice to evolve against. A better choice would be to evolve my own anti-imp. (to beat Imp)

VII. Conclusion:

The result of my experiments were in agreement with my hypothesis. However the out come was not as good, clean or easy as I had hoped. It did not work out exactly as I had guessed but technically, my hypothesis was correct.

The most successful of the generations was the generation against Dewney's simple example warriors. They include Dwarf, Anti-anti-imp, anti-imp and imp. At the end of the 3 generations of warriors, I did have 35 warriors ahead of the man-made warriors. These warriors were extremely simple and short, not meant to be true warriors but examples. This was the only real success. I had hoped to beat the warrior named Tornado, a much more worthy opponent.

The reason for success of the above generation is that the warriors were so simple. They did not have advanced strategies. The limited number of generations I produced was still enough to produce a few that had the traits to defeat the other warriors. These traits however existed from the start. The parent generation had the genetics to make such a breed of warriors possible. The success of this generation is not on the evolving of the warriors but on the parent generation that starts the cycle. It is the most important generation of them all because this is where all the code originates that will continue throughout more generations of warriors.

The most important thing the evolution of the warriors did was make a more successful breed of warriors. It started out with only a few good warriors and grew that into a large family of 35 good warriors. This is a significant find because it proves that the phenotypic traits were passed on to other warriors. Most likely in a environment were these warriors were able to reproduce huge numbers of warriors and have the possibility in genetic mutation more powerful warriors could be produced.

I would certainly like to further experiment with these digital warriors. There is so much more that can be done. The problem is that each generation of only 50 takes 15 minutes. The kind of improvements on the experiment could easily take 24 hours a generation. Perhaps I would be able to run these simulations on a more powerful machine. That would greatly increase the amount of generations that I could run through.

One of the most important of the improvements on the experiments would be to increase the amount of warriors in each generation. A population of 200 warriors would greatly increase the chance for success over that of a mere 50 that I was doing the experiment with. The possibilities of warriors could be better exploited. With so many possibilities for warriors, taking 50 out of the billions of possibilities is hardly fair. Even 200 is a small amount but it would greatly improve the experiment.

Another improvement would be to add a mutation factor to the experiment. During every breeding, I should add a 5% or so chance of a genetic mutation. This would increase the digital world and biological one in which real mutations are present. A mutation factor could also possibly introduce new traits into the generations as they evolve. If this mutation factor was present then the generations would not be quite as dependent on the raw code that was produced in the parent generation.

Other possibilities for experiments would be to change what the warriors were evolving toward. In my experiments, I was evolving the warriors to destroy a certain other warrior. This strategy would not produce the best warriors however. If you put this warrior into a world with warriors other than the warriors that it was trained to kill and defend itself from then it would certainly have some trouble. To make warriors more versatile in the environments in which they can live would certainly make for an interesting experiment. The best way to make more versatile warriors is to not fight all the warriors against another warriors but only against others in their generation. This would produce a more powerful warriors. The only limitation on such a experiment would be that the original genetic code would be very important. It is surely possible to get hundreds of warriors that are "hiders" meaning that they are purely defensive warriors and never hunt other warriors or move around at all. This would result in a entire generation of warriors that just tie all the time because they don't move. I had this trouble with the experiment I was doing so this is not limited to this new experiment. It certainly makes for a boring generation of warriors.

Altering the level of what I am using as the "Genetic Code" could also change things. For my experiment I was evolving at the instruction level meaning that instructions or arguments are being targeted at directly. At a lower level, such as the bit level, I could evolve by flipping bits resulting in a lot of instructions that are not legal in Corewars. This would however be a closer representation to what might happen in nature. Since computers are all run by bits, why shouldn't programs evolve at that level too. This would cause lots of illegal instructions but do we not in nature have genetic diseases and death because of problems in genetic code. Why should digital organisms have the advantages of always having legal instructions.

This project has been an incredibly educational. My only regret is that I didn't have the time to do all of the variations on the above and start reading more scientific papers on Evolutionary computing in the beginning. The amount of information that I have been absorbing has snowballed into an incredible amount of information that I wish to include in this paper but would probably go off topic and be too much to read. I will just have to save it all for a later project.

VII. Bibliography:

Beasley, David and Heitkoetter, Joerg. "Hitch-Hikers guide to Evolutionary Computation.", 1993.

Brown, Titus. "Frequently Asked Questions for comp.ai.alife.", 1995.

Dewdney, A.K. "In the game called Corewar Hostile programs engage in the battle of bits." Scientific American. May, 1984.

Freeman, Miller. "Explorations in Artificial Life." AI Expert. pgs 4-8 Sept, 1995.

Perry, John. "Corewars Genetics: The evolutions of Predation."

Pratt, Vernon. Thinking Machines: The evolution of artificial intelligence. Oxford Press, 1987.

Unknown. "Artificial Intelligence." Encarta 95, 1995.

VIII. Acknowledgments:

Thanks to John Perry for introducing me to the subject and for giving me advice through Email.

The computer science community for making information so easily attainable through the Internet.