| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| projects:archevo:archevo [2021/04/19 17:27] – Simplify model section Owen Mellema | projects:archevo:archevo [2021/04/25 18:15] (current) – Owen Mellema |
|---|
| ====== 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. |
| |
| //See main article, [[projects:archevo:model]]// | ===== 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. | 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 ===== | ===== Implementations ===== |
| ==== 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. |
| * 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: |
| |
| 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]] |
| | |
| | |
