Author Topic: Codules  (Read 15047 times)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Codules
« on: March 24, 2006, 04:48:16 AM »
I've been working on this and I think it solves alot of problems.  Really one of my better ideas.

Each Bot will have various "Codules" which are short code snipets (or long code snipets, length is irrelevant) that are all assigned to certain numbers.

A basic bot might have 1000 codule "slots" in a codule array.  Custom bots could increase or decrease that number.

During DNA execution, say you have something like:

50 goto

Codule 50 will be executed.

Here are the basic featues/points:
  • Empty codules will have (some random slot in the codule array) goto.  So if a bot mutates a goto statement and there's only one codule, the bot will execute that lone codule.  I imagine the best way to do this is to "shuffle" the codules.  That is, say you have an array of 5 codule slots.  The slots would call each other creating a circuit.  Like this:

    1->5->3->4->2->1

    This ensures that given a goto command that doesn't actually point to an existing codule:

    1.  Something happens, and so the mutation isn't quite so hit-or-miss.
    2.  Points to the same codule every cycle until a new codule is added or the codule it points to is deleted.  For instance, if the DNA calls codule 1 and 2 is the only codule with code in it, 1 will goto 2.

    Now suppose the bot mutates and acquires a codule at 3.  1 now points at 3.
    3.  The chances of where a random codule points is more or less evenly divided among the existing codules.
  • Codules that are called have their index placed on a "calling stack".
  • When a codule is called, a check is made to see if that codule's index is already on the calling stack.  If it is, the codule doesn't execute.  Or we could have it execute so long as there's less than a fixed number in the stack.  The idea is to prevent infinite loops.  Any finite upper limit will stop infinite loops, so the number can be anything.

    I'm thinking having an upper limit of 100 instances of a Codule on the calling stack is a good value.  That allows some fairly complex recursive functions that can't hang the system.
  • When a codule finishes executing, it pops the calling stack (removes its instance from the stack) and returns to where the goto that called it ends.
  • Once a goto is encountered, flow moves to the codule pointed to by the top of the regular integer stack.  This means you can construct goto's that call different functions based on the value of a single sysvar.
  • Values can be passed to and from codules through the stack since the goto statement basically just moves where the program is executing and doesn't change any scope or anything like that.  You could therefore sort of code your own custom math operators and things like that.
  • Codules can be passed between bots as viruses (either in shot or tie form).  An incoming codule replaces whatever codule was in that slot previously.  In fact, this is what I'm thinking should replace the present virus system.  The effect would be that viruses would be far more intimately connected with their host, and trans-species transmission wouldn't be a real problem to worry about (infected bots would just accumulate the new codule as "junk".  It would only execute the codule if the codule happened to replace an active codule slot, or the bot mutated to active the codule).
  • Codules are immune to flow controls from the gene that called it, and the gene that called it is immune to flow controls from inside the codule.  Say the DNA looked like this:

    start
    1 goto
    1 .up store
    stop

    Codule 1:
    stop

    Calling codule 1 won't prevent the 1 .up store from executing.

    This helps encapsulate possible mutations.  Mutations can't cause direct changes in program flow for any DNA that calls them.
There are two things I'm uncertain about:

1.  Should bots' regular DNA be represented as a Codule, perhaps with a "root" index of 0 or something like that.  If so, all bots' DNA would be highly susceptible to viruses since the "root" DNA is responsible for everything that defines a bot.  On the other hand, a bot would be able to call it's root program setting up some recursive possibilities.  Maybe root DNA can be accessed from inside the bot but can't be replaced by a virus.

2.  Should bots be allowed to actively modify its codules?  This goes into self-modifying DNA code, which is a whole other can of worms really.  A bot that could write it's own DNA on the fly could be quite adaptable and powerful.

The basic effects that it simulates:
1.  The Swtich-Case statement in other languages.  You just would set up something like:

cond
*.robage 5 <
start
*.robage goto
stop

to set up a multibot.  You'd just put codules in the first 5 slots that correspond to the first 5 steps of your multibot.

2.  Program Hierarchy - It simulates the effect plus some of the "Noble Genes" I talked about last summer.  Also, this allows for a more structured approach to building Multibots, since you can create a run a kind of state tree that is reflected in the coding architecture.

That is, mutations are more likely to respect the basic structure of your DNA, and so are more likely to stay in line with your original DNA's purpose (I imagine).

3.  It encorporates a new virus system that addresses many (if not all) the issues shvarz pointed out with biological equivelances.

I'm sorry if any of the above is a little too comuter-ese, I'm writing this write before I go to bed and I'm always a little less comprehensible when my brain shuts down ;)

Offline Elite

  • Bot Overlord
  • ****
  • Posts: 532
    • View Profile
Codules
« Reply #1 on: March 24, 2006, 11:38:26 AM »
Wow, great idea.

Self-modifying DNA - why not? That would make for some super-cool bots. Lots of new oppertunities

Mmm ... new virus system ...

 :drool:

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #2 on: March 24, 2006, 01:25:19 PM »
Very nice.  Some quick feedback:

I'm all for enhancing the regulatory and structural elements of the DB DNA language.  Codules would be hunks of semi-atomic structural information whose expression could now be more richly controlled.  I think the term "Transcription Factor" is the biological equivalent.  They become a unit of mutation, sequence exchange and expression.  Genes are the expression triggers.  Love it.

This question of what language mechanisms to use is a hot area of research in the ALife community.  If I understand it correctly, the propsoal is not unlike elements of the transsys language which is a "formal language for modelling regulatory network systems conssisting of transcription factors and genes encoding them." See: transsys overview

From what I have read, it seems that much of the evolution of complex organisms is about selection for regulatory elements, not just structural elements.  That is, it's not just about evolving better genes that do better things, is about evolving better logic about which and when what genes are expressed I.e. evolving a regulatory system which expresses the right genes at the right times in the right way.  Evolving better transcriptions on your own takes time.  It's faster for selection to operate on the regulatory system governing the expression of already evolved DNA sequences (whcih you may have stolen from different species).

Did you know the length of the genomes of different biological organisms are not necessarily corrolated with pheneotype complexity?  I didn't.  Some "simple" species like some newts for example have genomes a lot longer than humans.  Most of the "code" never gets expressed in a given species yet it is preserved accross generations in case futue selection pressure selects the regulatory system to express it, in effect, selecting for expression of dormant codules.   Lots of genes (or is the right term 'transcription factors'?) are very old, having changed little over time.  They evolved long ago in common ancestors of today's different species.  They are just not necessarily expressed or expressed in the same way in different species.  So, I'm all for adding a richer mechanism which allows for selection to operate more richly on the regulatory system.

That said, I have to noddle on the implementation specifics.   Some quick thoughts:

I like the linked list of current codules and that gotos are indexes into that list.

I like that newly aquired codules get inserted at end of the list.  You don't want the aquisition of a new codule to necessarily screw up the expression logic for current codules.  Aquiring a new codule (though mutation, gene exchange, sex, virus, etc) should be a separate thing from a mutation which starts expressing that codule.

I think you want codules to be able to be expressed multiple times per cycle.  I don't understand the infinite loop risk.  I assume codules cannot invoke genes and that there are no looping primities in the DNA language.  Thus there must be one goto for each codule expression, right?.  Where do you get loops?

I assume use of codules would not be mandated.  Current bots which emodied all their DNA in genes would continue to work.  Thus, the tradoffs about whether an organism puts their DNA in codules or genes and the resulting advatnages and disadvantages of each strategy such as susceptability to things like viruses can be left up to the bots and their authors.  I.e. I feel no need to create special cases such as "root" codules that are immune to viruses.
 
Isn't self-modification of DNA is a separate issue from the codule issue, the pros and cons of which can be disucssed as a separate topic?

-E
Many beers....

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Codules
« Reply #3 on: March 24, 2006, 01:49:16 PM »
Quote
I think you want codules to be able to be expressed multiple times per cycle.  I don't understand the infinite loop risk.  I assume codules cannot invoke genes and that there are no looping primities in the DNA language.  Thus there must be one goto for each codule expression, right?.  Where do you get loops?
It's not that codules can't be expressed multiple times per cycle.  It's that codules can't (or should be able to only a limited number of times) call themselves or another codule that calls themselves.

For instance, say Codule 2 calls codule 5.  Now Codule 5 calls codule 2.  This creates a potentially infinite recursive loop that the program would have a hard time detecting.  By limiting the number of instances that a codule can have on the calling stack, after a certain point the above goto calls would fizzle and not do anything, at which point the codule would pop from the stack and return control to the previous codule, which would pop, etc.

You have to be really careful about infinite loops in a project like Darwinbots.  Other ALife sims that use organism code generally have robots (or whatever) all executing their DNA one command at a time every cycle.  Bots with infinite loops are permissable and even encouraged as they only effect themselves.

Quote
Isn't self-modification of DNA is a separate issue from the codule issue, the pros and cons of which can be disucssed as a separate topic?
Yes, but it seemed to come to mind as I was playing with this idea.  If you'd like to talk about it too, we can start another topic.

-E

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #4 on: March 24, 2006, 02:05:32 PM »
Okay.  Codules calling codules.  Got it.

We need a natural backpressure mechanism on loops.  What if we thought of infinite loops (and other ineffecient DNA execution aberations) as a form of cancer?  Assume a goto costs something.  If the engine calculated energy usage periodically during the genome execution, say at every goto, there would be tremendous selection pressure against infinite loops and other gross regulatroy ineffeciences.  As long as the stack was large enough, a bot which mutated an infinite loop would die that cycle without any artificial limits on codule executions per cycle.  That said, a sufficiently high limit as a simulator safeguard - one that no organism without cancer would ever hit - would certainly be advisable.
Many beers....

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Codules
« Reply #5 on: March 24, 2006, 02:23:17 PM »
There are really two issues here.

1.  How hard is it to create an infinite loop.

2.  The consequences if you do.

Originally a while back I considered charging for the gotos like you suggest.  In which case, infinite loops cause instantaneous death, which has issues IMO.  Generally speaking, I try not to penalize bots for evolving stupid things, but reward them for evolving smart things.  There are a few safeguards in place to generally prevent bots from screwing themselves over too bad.

The limits on up and dn etc. for instance.  They can be fairly high, the point is that it should be really hard for a bot to kill itself without trying.

So in this case, I think an upper limit is preferable, since bots are still allowed to survive and live if one little part of its DNA happens to create an infinite loop.  Theoretically this limit can be anything, since any number is going to be less than infinite.  Realistically when you get above maybe 1 000 000 you probably are stretching it.  100, 1000, or 10000 would be my preferable choice.  DNA execution isn't really the bottleneck for the program at the moment, so I don't think we have to worry too much about program slowdown.

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #6 on: March 24, 2006, 03:03:30 PM »
We have slightly different philosphies I think.  Mine is likely the result of inexperience w.r.t. the "real world" of what actually works in DB to make it fun/forgiving/probable to evolve something interesting.  So, I must defer to expereince and I'm fine with the approach and with having an upper limit.

That said, my philosphy is that I think it should be easy for bots to develop fatal DNA artifacts such as infinite loops, but the consequences of this (imposed by the associated costs inherent in the environment) should be severe and that this provides the selection pressure feedback such that bots won't evolve in that direction.  For example, if mutating an infinite loop is immediatly fatal, the number of individuals that will ever get impacted from this will be a vanishingly small percent of the population since no organism with such a mutation will ever procreate.  The diversity of the population upon which selection oeprates will contain no idividuals inclined to infinite loops.

INHO, it should be easy for bots to evovle DNA that results in quick death and favor those who do not.  Evolution isn't just survival of the fittest, its non-survival of the unfit, which has the effect of shifting the entire bell curve of individuals in a species towards fitness instead of just broadening it.  This isn't so critical I think when there is only asexual reproduction as the average fitness of other individuals within a species has little effect on the fitness of the fitter indivuals.  But the average fitness of the population becomes critical to the fitness of the most fit individuals in a population when we have sexual reproduction.  Sexual reproduction emphasizes evolution of species not just individuals.  Not punishing stupid mutations will drag down the fitter individuals in a species until we create rich mechanisms for sexual selection I.e. for fitter bots to recognize and refuse to breed with less fit bots.

-E  

"There are a lot more ways of being dead than of being alive" - Richard Dawkins.
« Last Edit: March 24, 2006, 03:05:07 PM by EricL »
Many beers....

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Codules
« Reply #7 on: March 24, 2006, 03:15:53 PM »
Can't say I understand it completely, so some questions to clarify:

1. Are we placing all of DNA into codules?  Can DNA exist outside of a codule?
2. If DNA in a codule has a goto command the flow of that DNA is stopped and the called codule is executed first, once it's done it comes back to the original DNA and continues right after the goto command.  Is that right?
3. I'm not sure how you are preventing infinite loops.  Let's say codule 1 has the following code:

cond
start
1 goto
stop

I don't see how it can get resolved.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Codules
« Reply #8 on: March 24, 2006, 03:20:38 PM »
Eric:  Look at the existing DNA structure - it is designed to be forgiving.  We could make it so that any letter in DNA can be mutated, so that .refeye could mutate into .sefeye or .tefeye with fatal consecuences.  But it would not work for DB, because it would take a freakishly long time to mutate .refeye into .up.  Reality is good, but it's not fun :)  We just assume that all these mutations happen, but die out immediately, so there is no need to spend cycles on creating dead bots.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #9 on: March 24, 2006, 03:24:49 PM »
I'm not suggesting we allow the evolution of syntaticly incorrect organisms.  I agree we can just assume all those guys die fast.  I'm saying semantic ineffeciency should be more severely punished than it is today.
Many beers....

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Codules
« Reply #10 on: March 24, 2006, 03:48:33 PM »
I think what you are actually proposing would achieve exactly reverse - it will soften the rules.  The way I see it (although I may be mistaken) your proposals differ as follows:

Nums - we don't allow any infinite loops (assume bots with infinite loops immediatey die)
You - we allow bots with infinite loops to be born, but make it so that they die of energy loss

The end result seems to be the same: no bots with infinite loops, but in your proposal we also waste some processor cycles along the way.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #11 on: March 24, 2006, 04:06:10 PM »
My understanding of the positions:

Me - allow bots with infinitie loops or other semantic inefficienies to be born, but they tend to die out fast and not reproduce because everything costs something.

Nums - allow bots with infinitie loops or other semantic inefficienies to be born, persist and even reproduce by mitigating the effects of their stupidity by putting limits on things in the name of providing a forgiving environment.  Execute infinite loops only so many times, truncate the maximum values they can store in .up and .dn, etc.

My way is a lot more effecient from a cycle perspective - ineffecient bots die and tend not to reproduce instead of potentially being allowed to survice despite their ineffeciences - but I don't think that is really the main issue which is about keeping the bar to creating/breeding something that successfully lives to reproduce sufficiently low that it stays fun.
Many beers....

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Codules
« Reply #12 on: March 24, 2006, 04:20:17 PM »
Oh, I think I see.  But "infinite loop" is not a semantic inefficiency, it is a dead bot by definition because it can never complete execution of its DNA.  "Infinite loop" is (let me borrow you term) syntaticly incorrect.

Why not combine your two approaches?  Don't allow infinite loops AND charge a little bit for having a loop.  That's pretty much how current system works, it charges bots based on the length of their DNA.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline EricL

  • Administrator
  • Bot God
  • *****
  • Posts: 2266
    • View Profile
Codules
« Reply #13 on: March 24, 2006, 04:29:07 PM »
It's essentially impossible for the engine to apriori figure out if there is an infinite loop in a bot's DNA.  A bot with a infinite loop IS actually a syntatically correct program I.e there is nothing syntatcially incorrect about the code.  An infinite loop is a semantic error and it's generally computationaly prohibitive to try to figure out if a loop is infinite or not without actually executing the DNA.  You can imagine very convoluted loops

1->3->44->23->6->39->7->8->1

or cases where a loop is only infinite under certian environmental conditions, or certain cases when the recursion doesn't terminate, etc.  These are all run-time things, things you can't determine apriori.  You have to run the bot and even then it may only happen once in a blue moon.

So, there really is no such thing as 'not allowing' infinite loops.  If the language syntax allows for the expression of the right constructs - for recursion, gotos, whiles or other expressions of conditional loops or jumps, infinite loops will be possible.  The only debate is what to do about it when a bot exectes such a loop.
« Last Edit: March 24, 2006, 05:29:25 PM by EricL »
Many beers....

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Codules
« Reply #14 on: March 24, 2006, 05:25:36 PM »
Look at it from a fitness landscape position.  Mutations that cause immediate deaths are like singularities.  Bots that venture there are immediatly killed, and hence can't continue moving around the fitness landscape.  The more singularities the more unlikely a population of bots is going to make the trek from lows to highs (or highs to lows depending on how you view the fitness landscape).

I'm not against letting the bots do stupid things.  For instance, bots that forget how to feed are going to die.  This is fact, and the simulation isn't going to rescue them.  But that death is going to take a while.

Another way to look at it is in terms of mutation neighborhoods.  Let's say you have a strand of DNA.  A neighborhood is any DNA strand you can get to with a single mutation.  Most are going to be neutral or mildly deleterious.  A few are going to be quite lethal and some are going to be quite good.  Lethal mutations will never produce offspring worth the simulation's time or resources, so we simply don't let the bots mutate them.  It doesn't really change the fitness landscape except to maybe to allow more experimentation.

Bots shouldn't be able to kill themselves with terrible ease.  If this were a bowling game, it's like playing with bumpers in the gutter.  Gutter balls are simply not fun, so you can use bumpers to steer the ball towards some pins.

These goto commands would really be a new category of DNA, so there's no problem adding another costs field for them.  But like the rest of DNA codes I think the cost should be kept quite light.

Quote
1. Are we placing all of DNA into codules? Can DNA exist outside of a codule?

All DNA is either in a codule or a root DNA.  (The present DNA system is like the root DNA.)

Quote
2. If DNA in a codule has a goto command the flow of that DNA is stopped and the called codule is executed first, once it's done it comes back to the original DNA and continues right after the goto command. Is that right?

That's right.

Quote
3. I'm not sure how you are preventing infinite loops. Let's say codule 1 has the following code:

cond
start
1 goto
stop

I don't see how it can get resolved.

Let's say that there can only be 5 instances of any codule on the calling stack at once.  After 4 calls it starts on the 5th.  1 goto checks to see the number of instances of the codule on the stack, and finds that there is already 5.  The goto does nothing (other than removing 1 from the stack of course), and the codule finishes executing.  Then so does the codule that called it, etc.  Each instance pops from the stack.  After each pop another instance of codule 1 is allowed to execute.  The 5 instance limit is like limiting the depth of the calling tree.