OwenWiki

User Tools

Site Tools

Trace:
projects:archevo:archevo

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
projects:archevo:archevo [2021/04/19 16:32] – Add information about cannibalism Owen Mellemaprojects:archevo:archevo [2021/04/25 18:15] (current) – Owen Mellema
Line 1: Line 1:
 ====== ArchEvo ====== ====== ArchEvo ======
-{{:projects:archevo:archevo_classic.png?200 |}} **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.+// See ArchEvo in action on [[https://github.com/architectdrone/ArchEvoPangea|GitHub]] //
  
-===== The Model =====+**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.
  
-==== Cells ====+===== Model =====
  
-A cell is a virtual machine that exists in the Universe.+//See main article, [[projects:archevo:model | The ArchEvo Model]]//
  
-=== Registers ===+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.
  
-A cell has eight registers, each of which are eight bits wide. The first cell represent the amount of energy the cell has (( Since the registers are only 8 bits wide, that means that the maximum amount of energy a cell can have is limited to 256, as it cannot overflow )). When a new cell is created, all of the registers are set to 0, except for the energy register.+===== Evolvable ISA ===== 
 +//See main article, [[projects:archevo:ISA]]//
  
-Technically, the rest of the cells have no intrinsic meaning separate from the context in which they are run (including ISA, combat handler, reproduction handler, etc) , but generally the cells are given these names: +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.
-  * 0: Energy +
-  * 1: Logo +
-  * 2: Guess +
-  * 3: Register A +
-  * 4: Register B +
-  * 5: Register C +
-  * 6: Register D +
-  * 7: IPLOC+
  
-The names of regs 1 and 2 come from the [[ projects:archevo:CaptureTheFlag ]] combat handler, and reg 7 is IPLOC in [[ projects:archevo:ASIA ]].+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.
  
-== Death == +[[ 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. 
-When energy is 0 (it can't underflow), the cell is dead, and will be garbage collected in the next iteration. +  * [[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.
-=== Program ===  +
- +
-A cell has a set of instructions that is called a Program. Each individual instruction is simply a set of bits. The instructions may be of an arbitrary length depending on the ISA. [[ projects:archevo:ASIA ]]'s instructions are eleven bits long. +
- +
-When a new cell is introduced randomly into the Universe, all of the bits of the program will be randomized. However, when a cell is created as a child of another cell, the new cell inherits the parent's program, with some mutated bits. +
- +
-A cell also has an Instruction Pointer (IP) . This is a number that is between 0 and the length of the program. When a cell is created this is initialized to 0. +
- +
-=== Actions === +
- +
-Each iteration, the instruction that is pointed at by the IP is translated into an action. The possible actions are:  +
-  * RegisterUpdate <register> <value>: Changes the value of a register. +
-  * Attack <x_off> <y_off>: Attacks the cell at the given offset. +
-  * DoNothing ((DoNothing has a counterpart ExternalDoNothing that exists for technical reasons)) +
-  * Move <x_off> <y_off>: Moves the cell to the offset. +
-  * MoveInstructionPointer <new_instruction_pointer>: Moves the Instruction Pointer (Jumps) to a new location in the program +
-  * Reproduce <x_off> <y_off>: Creates a new cell at the offset. +
- +
-This action is then executed. +
- +
-== Reproduction == +
-{{ :projects:archevo:executereproduction.png?100|}}When the reproduce action is triggered, a new baby cell may be created. However, first the [[ projects:archevo:ReproductionHandler]] is. The ReproductionHandler decides three things: +
-  * Can the parent reproduce? +
-  * What energy cost will the parent need to pay to reproduce? +
-  * What will the baby cell's initial energy be? +
-If the parent cannot reproduce, no change will occur. If the parent can reproduce, then the energy cost is deducted from the parent, and a new cell is created with the proper amount of initial energy. (Click the flowchart on the right to enlarge it) +
- +
-== Attacking == +
-{{:projects:archevo:combatflowchart.png?100 |}}Attacking other cells is the only way for a cell to gain more energy. The change in energy for both attacker and (if there is one ((Cells can also attack thin air, although this generally results in a penalty.))) defender are determined by the [[ projects:archevo:CombatHandler ]]. +
- +
-==== Universe ==== +
- +
-The Universe is a grid that contains Cells. Although it is a finite grid, the edges wrap around to the opposite side, meaning that Cells can travel in one direction infinitely.  +
- +
-Each iteration, some new cells are spawned with randomized programs.+
  
 ===== Implementations ===== ===== Implementations =====
Line 70: Line 28:
 ==== ArchEvo Classic ==== ==== 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.+{{: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 [[ projects:archoevo:ASIA ]] ) were capable of demonstrating interesting evolutionary properties.+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. 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.
Line 93: Line 51:
   * ISA: [[ ASIA ]]   * ISA: [[ ASIA ]]
   * ReproductionHandler: [[ SetCost ]]   * ReproductionHandler: [[ SetCost ]]
-  * CombatHander: [[ CaptureTheFlag ]]+  * CombatHander: [[ CaptureTheFlagPercentage ]]
   * Iteration Execution Mode: Instruction By Instruction   * Iteration Execution Mode: Instruction By Instruction
 My hypotheses were: My hypotheses were:
Line 105: Line 63:
  
 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. 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]]
 +
 +
projects/archevo/archevo.1618849926.txt.gz · Last modified: 2021/04/19 16:32 by Owen Mellema