OwenWiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== ArchEvo ======
// See ArchEvo in action on [[https://github.com/architectdrone/ArchEvoPangea|GitHub]] //

**ArchEvo** is an experiment on evolution of digital lifeforms. It is a simulation of a 2D world, where virtual machines must compete for energy and reproduce. The ArchEvo program has had two distinct versions, and parts of it have been written in C++, Java, React/Javascript, and Python.

===== Model =====

//See main article, [[projects:archevo:model | The ArchEvo Model]]//

Cells are virtual machines that have a program and eight registers. The program is translated by the [[ projects:archevo:ISA ]] into an action. Reproduction requires energy, and to get energy, cells must attack each other. New cells are spawned every iteration.

===== Evolvable ISA =====
//See main article, [[projects:archevo:ISA]]//

Cells require a special type of ISA known as an //evolvable// ISA. Real world ISAs tend to be brittle - that is, bitflips in a program lead to programs that behave much differently from the original. Evolvable ISAs, on the other hand, have the property that bitflips tend to not alter how the program functions.

To be evolvable, there are two important requirements. Firstly, the ISA must be faultless. That is, all possible instructions should be valid. Secondly, it should be structurally robust. Structural robustness mainly refers to jumps. In normal ISAs, jump instructions jump to certain labels, but that is hard to evolve. Some other nice features that we want are the ability to inspect other cells, and a limited number of bits per instruction.

[[ projects:archevo:ASIA ]] accomplishes these goals with some clever tricks.
  * [[isa#ghost_bits | Ghost Bits]]: Instructions that would cause a permissions fault are interpreted as different instructions that would not cause a permissions fault. This way, 3 bits of opcode maps to 16 possible instructions.
  * [[isa#template_jumps | Template Jumps]]: instead of jumping to labels, jump to groups of instructions. ((I actually borrowed this from TIERRA))
  * [[isa#IPLOC]]: The most significant bit of a certain register (known as the **I**nspection **P**ointer **LOC**ation, or IPLOC for short) represents an offset from the cell. A set of virtual registers represent the registers that are pointed at by IPLOC.

===== Implementations =====

ArchEvo has been implemented twice.

==== ArchEvo Classic ====

{{:projects:archevo:archevo_classic.png?200 |}} [[https://github.com/architectdrone/ArchEvo|ArchEvo Classic]] was the first implementation of ArchEvo. It was written in purely C++, and the graphical component was handled by [[ https://github.com/libtcod/libtcod | libtcod ]], a platform for creating roguelikes. It began development in the summer of 2020, as I had a lot of spare time between my graduation from KU and the beginning of my new job at Cerner. While the GUI is spartan, I think it is really cool if I do say so myself 8-)

This version demonstrated that my model, along with the ISA I had created (later known as [[ ASIA ]] ) were capable of demonstrating interesting evolutionary properties.

ArchEvo Classic suffered from a number of problems that crippled it's usage as an experimental tool. Firstly, it had poor separation of concerns, which meant that trying out new concepts like new ISAs would end up touching almost all of the parts of the code. Secondly, there were some logical problems. The Universe was rife with race conditions, including the fact that cells with a lower x and y had priority over other cells. Finally, the Universe's state was tied to the GUI, which led to some awkwardness.

Despite these flaws, ArchEvo Classic is one of the projects that I am most proud of. The entire project is almost 3,500 lines of code, making it the largest personal project I had undertaken at the time.

==== ArchEvo Pangea ====
{{:projects:archevo:archevo_pangea.png?200 |}} [[https://github.com/architectdrone/ArchEvoPangea|ArchEvo Pangea]] was the second implementation of ArchEvo, and the only version that is currently being developed. It was written as an attempt to address some of the problems with ArchEvo Classic. ArchEvo Pangea is actually three components: 
  * Backend simulation logic (java)
  * Webserver run the simulation and serve it's state (java/spring)
  * Website to display the state of the simulation (javascript/react)
Some diagnostic tools were also written in Python. 

The modular design of the simulation backend makes it much easier to test out new ideas than ArchEvo Classic. Additionally, the whole thing is unit tested, meaning that I know that the simulation works how I think it does.

GitHub reports that there are something like 8,000 lines of code in Pangea. It's hard to gauge how much of that is autogenerated, boilerplate, etc. Regardless, it is a very complex project.

===== Results =====
As this is an active project, the "results" of the experiment are still up in the air. However, I can report on whether or not my initial hypotheses were correct. The parameters of the initial experiment were:
  * ISA: [[ ASIA ]]
  * ReproductionHandler: [[ SetCost ]]
  * CombatHander: [[ CaptureTheFlagPercentage ]]
  * Iteration Execution Mode: Instruction By Instruction
My hypotheses were:
  * Replicators can emerge in the ArchEvo model.
  * Complex food webs will form (ie, species A is adapted to eat species B, etc)
  * Logical structures will emerge to prevent cannibalism. This aids in the propagation of genetic material.

The first hypothesis was confirmed. Within just 10,000 iterations, at least one species of replicators will generally emerge. 

The second hypothesis was disproven. In all of the iterations I have seen past about 10,000 iterations, one species gains hegemonic power. When positive mutations occur in this species, the mutation will quickly take over the gene pool.

The third hypothesis was also disproven. I think the reason that this is is due to the processing overhead of making decisions in ASIA. The cell must make an observation, compute a response, and then execute the response. This overhead makes the cell vulnerable to predators. However, some non-logical strategies for avoiding cannibalism were discovered. Mothers can move, reproduce, and attack in a certain pattern that ensures that many grandchildren are protected from it, assuming exactly shared genetic material.

===== Inspirations =====
This project has had many inspirations. In the spirit of evolution, I like to think of the traits from these projects as being a part of the genetic history for ArchEvo. :D
  * [[https://www.cc.gatech.edu/~turk/bio_sim/articles/tierra_thomas_ray.pdf | TIERRA]] was the first time someone tried something like this, as far as I know. Many of the concepts that are used in ArchEvo, such as template jumps and the overall concept of evolvable ISAs, were borrowed from this paper. Despite this, TIERRA is much different from ArchEvo. Whereas in ArchEvo reproduction is accomplished by meeting certain conditions and triggering the REPRODUCE action, in TIERRA, the cells must build the new cells up instruction by instruction. In fact, an organism is really only defined by it's instruction pointer.
  * [[https://github.com/adamierymenko/nanopond | Nanopond, by Adam Ierymenko ]] was probably the biggest inspiration for ArchEvo in terms of format and ideas. When I stumbled across videos of it due to the almighty YouTube algorithm, I knew that I wanted to create something like it. The [[ projects:archevo:CaptureTheFlag ]] system comes from this project. Rereading the source, I am now wondering if I could get better results using a brainfuck compiler. Hmmm... yet more genetic inheritance!
  * [[ https://www.youtube.com/watch?v=C9tWr1WUTuI | evolv.io, by CaryKH ]] was the "kick in the pants" that got me wanting to work on this project. The idea was so interesting, yet so (not offense to Cary) hobbled by its implementation that the evolution was difficult to observe.

===== More information =====
This article was meant to be succinct, so a lot of details were skipped over. Please take a look at these articles for more in-depth information.
  * [[ISA]]
    * [[ASIA]]
  * [[CombatHandler]]
    * [[CaptureTheFlag]]
    * [[CaptureTheFlagPercentage]]
  * [[ReproductionHandler]]
    * [[SetCost]]