Creating a “world” for evolution of programs

Question

I am trying to create a "world" where "copies of programs" are allowed to evolve, proliferate and fight for resources. Organisms copy information with errors and memorize the results. It seems like one can create a "world" with resources, place various copies of a program and let them fight for resources, grow and evolve.

What would it be for Java programs. World has cells each producing certain amount of letters per tic. An organism is a String of text that extends Life, compiles correctly, has methods eat, move and breed. Every tic move, eat, breed are executed. On move organism can decide to move to nearby cell. On eat it can move all free letters from cell to it's body (store those behind /* here */ to make sure program compiles). During breed stage it it can build it's own copy using letters from the commented area of the program body. Copying is error prone. If the resulting copy compiles it joins the race for resources.

Here are the problems I am having: A single character change in a program tends to cause compile time error. How to increase survival chances of an offspring with a point mutation? IRL organisms eat each other. How to model predator attacking prey? Some simple injectPoison(prey); that injects */ between 50th and 51st characters in the body of prey string would kill pretty much any program. Something like "to fight: run Robocode - winner gets all loser's letters" would turn the world into a Robocode engine competition. IRL organisms do exchange information. One can allow programs to exchange their methods, but then it is very tempting for a program to just inject a suicide method and eat the body of dead partner.

My questions are: Is there any research on building such world? What is the best way to model resources? What limits the extent of evolution in such models.

Answer 1

As mentioned in the comments, for most practical purposes, you need to select a level of granularity / abstraction that can be easily modified without invalidating the code. When I studied artificial life in graduate school, the option were to either:

• directly use a language that was well suited to symbolic programming (we used LISP at the time)
  • this is less work up front since you're not building your own custom language, although this is not true if you have to learn a new language that's signifgantly different from what you're used to using
  • gives more flexibility since technically anything that could be coded could be generated by the simulation
  • often takes longer to converge on a solution since there are typically way more wrong / inapplicable programs than correct / relevant ones
• create your own op codes & and interpreter for them in what ever language you want (I used C++ to reimplement the Santa Fe Trail Problem)
  • this is more work up front since you have to build at least some of your language before you can start evolving/ simulating stuff
  • gives less flexibility since you're opcodes are typically tailored to a specific problem
  • often takes less to converge on a solution since you typically have fewer opcodes than a general purpose programming language & they're typically all relevant to your problem of interest

Having tried both, I favor the roll your own approach, but both have there place. From a game dev perspective, it's probably better to roll your own since you can constrain things for safety - not cool if you allow the user to evolve a program that nukes their hard drive.

Answer 2

Speculative question indeed, and thus a bit unwelcome here, but a favourite topic of mine. A-life is a fascinating field, as is Evolutionary Computing and related / sub-fields like Genetic Programming.

A single character change in a program tends to cause compile time error.

Then don't model the program code in that way. Rather ensure that any given string (perhaps within some enforced set of parameters such as a max length, or only unique characters in the string) can always be interpreted as a compilable program. For example A might denote a certain ability/functionality on its own. This has been done I believe, though I forget the name(s) of the language(s) in question.

It could even be as simple as that every character in the ASCII range has some fixed meaning within the context of your "organism", e.g. Z means it is motile. That's a very simplistic scheme, though.

RL organisms eat each other. How to model predator attacking prey?

Perhaps you have some standard approach, like in Chess where moving onto the enemy's cell is in itself an attack. This obviously implies that organisms are "territorial".

Is there any research on building such world?

You're certainly not the first to foray into this area, though not sure anyone has written a game that has executed these ideas really well (as in hit title). Also, see the aforementioned fields for much more.

What is the best way to model resources?

That's a very open-ended question. I would say the choice is initially between abstractly and spatially. Spatially probably makes for a more visually engaging gameplay experience. Set it up on a grid. Let them fight for resources and find their tactics through spatial engagement... as e.g. cells in tissue.

What limits the extent of evolution in such models.

Combinatorial complexity. Just how many permutations does your code support, and just how many are you planning to test, and just how many thousands of CPU hours will that take? The simpler you keep it, the more testable it is. Then again, games like Go show that even an incredibly simple ruleset can lead to extremely deep gameplay.

A word of advice. There really are a million directions in which you could take this. Anything heavily procedural and close to pure logic / mathematics is prone to quickly getting bogged down in exceeding complexity, when looked at from a creative standpoint. In a way, you're playing with the fundamentals of existence, so try to limit your depth in terms of design, at every step. Fast prototyping / iteration and rapid elimination of potential design paths will be your best friends in this endeavour.

Answer 3

There is quite a lot of research in that area. But usually the agents are not controlled by programs written in programming languages humans would code in. A popular choice to control evolving AI agents are neural networks. They are rarely completely crippled by small mutations but can still form surprisingly complex behaviors.

A project very similar to what you seem to want to do based on neural networks is Critterding.

If you want to create something similar with a real-world human programming language like Java, you might not want to work on the level of single characters, because these are practically guaranteed to break the program. Rather go up a step in abstraction and deal with permutations on basis of the syntax tree. That way you will have a much easier time creating permutations which might actually be valid programs.