Eventual improvements to DNA language

[Numsgil]

This thread is primarily a place for me to record all my thoughts for DNA in one place.  But I'd like feedback as well, so instead of just writing it up on my computer, I'm positng it.  Most of this was in old posts, some from February, and it was fairly well recieved then, so I'm not too worried.  

I recommend printing this out and taking it with you to lunch.  It's quite long, even for one of my posts :P  Feel free to read and comment on one section at a time.

[span style=\'font-size:11pt;line-height:100%\']DNA STRUCTURE[/span]
This is the idea I have for expanding the language to make it easier for complex behaviors to be developed and hopefully evolved.

First off, the cond-start-stop structure is refined to a cond-stop-body-stop-else-stop structure.  For backwards compatibility, 'start' is interpreted as a stop-body command in one (won't be evolved by the DNA, and when it's read in by the parser it will place it at two commands, stop and body).

cond, else and body set a flag that determines how the following DNA is executed (this idea is from shvarz, though it was a while ago).  This is called the execution flag.  It'll be referenced quite a bit below, so be sure you understand what I mean by flag.

Now, here's the main commands:

1.  cond tells the DNA to evaluate and place conditions on the conditions stack, and accept logic commands.

2.  else and body tells the DNA to evaluate store, inc, and dec commands.

3.  stop command resets the current mode.

cond and body and else are all mutually exclusive.  You can't store commands and evaluate conditions in the same section of the DNA.  If there is a body command after a cond but before a stop, nothing happens.  The reverse is true.  (Or we could do it the other way.  A body command after a cond switches evaluation types and empties the conditions stack.  Either works, so long as it's consistant).

A stop statement is multipurpose.  If the execution flag is set to cond, then it will AND together all true/falses on the conditions stack.  If the result is true, it sets the condition flag to allow the next body command to be evaluated.  If the result is false, it sets the execution flag to allow the next else command to be evaluated.

If the execution flag is set to body when the stop command is called, store, inc, and dec are no longer allowed to operate.  In addition, the flag is cleared out, awaiting a new cond statement.

Likewise if the execution flag is set to else when the stop command is called, it's cleared out.

If a stop is called when there's nothing to stop, that is, the execution flag is still clear, nothing happens.

If a body or else is called when the execution flag is already set to body or else, nothing happens.

So here's what I'm thinking basically.  It's easier to explain via example.

Code: [Select]

cond
*.nrg 5000 >
stop

'some Junk DNA

body
50 .repro store
stop

'some more Junk DNA

else
-1 .shoot store
10 .up store
stop
end
[span style=\'font-size:11pt;line-height:100%\']Select / Cond[/span]
Similar to regular gene flow, but slightly modified.

Here's a sample segment of DNA

Code: [Select]

*.robage select
'(Note that there's no stop here!)
cond
0
start
5 .tie store
stop

cond
1 5
start
5 .deltie store
stop
stop 'this is the stop for the select
Okay, now that you've seen it, I'll show you how it's working.
Select sets the execution flag for conditions to operate slightly differently.  The conditions stack remains off.  However, any values put onto the regular stack inside the condition are evaluated against the variable selected for, in this case *.robage.  If any of the values are equal to the selected value, the gene is executed.

The second cond above works the same as

Code: [Select]

cond
*.robage 1 =
*.robage 5 = or
start
5 .deltie store
stop
That is, all the evaluations against the selected variable are ORed together.

[span style=\'font-size:11pt;line-height:100%\']Nested conditions (Noble genes)[/span]

These work exactly the same as the regular commands above, but the bodies themselves can't execute store, inc, or dec.

The commands are all the same as all the above, but capitalized.  They allow large sections of DNA to be turned on or off.

Basically:

Code: [Select]

COND
*.nrg 5000 <
STOP
BODY

gene1

gene2

gene3
STOP
ELSE
gene 4

gene 5

gene 6
STOP
if *.nrg is less than 5000, then genes 1,2,and 3 will have a chance to be evaluated.  Otherwise genes 4,5, and 6 will have a chance.  Gene1 still might not excute even if *.nrg is less than 5000 if its condition doesn't evaluate to true.

These uppercase controls I call 'Noble' genes.  The regular lower case genes are called 'Pleb' Genes.  I haven't worked out exactly how the execution flag will work with these noble genes.  Very likely they will have their own seperate execution flag.

The idea is to be able to group large amounts of DNA that are supposed to be run together simply and easily, as well as encouraging them to be near one another.

[span style=\'font-size:11pt;line-height:100%\']Sleep Command[/span]
This is basically a multithreading idea that would work well for DB to coordinate events between multiple cycles.

the syntax is:
number sleep

This will cause the current gene to 'sleep' for number cycles.  Once it awakens, it will continue the execution of the gene where it left off.

Something like this to remove a birth tie:

Code: [Select]

cond
*.robage 0 =
start
5 .tie store
1 sleep
5 .deltie store
stop
The gene will not be evaluated while it is sleeping.  That is, you cannot have more than one copy of the same gene executing at the same time.  This is the price you pay for sleeping: not executing again until you're all done.

For example, this will only allow you to reproduce every 50 cycles:

Code: [Select]

cond
start
50 .repro store
50 sleep
stop
The logistics can be accomplished by a command stack of genes and timers.  Shouldn't be too difficult.

[span style=\'font-size:11pt;line-height:100%\']Conclusion[/span]

These changes hopefully will encourage more complex DNA to develop from both writers and mutations.  Most bots today are still very, very simple.  Archeabacteria knock our socks off!  Alot of the above is based on programming languages and computer science theory, but that doesn't mean they can't be useful to organsims.

Since the stop command is used so heavily, it should have a disproportionate chance of developing.  Also, since the noble genes should control several smaller genes, noble commands should be less likely to develop.  I'll probably need to develop sliders for the different types, or have noble commands be a seperate type altogether.

[Endy]

I like the ideas about Noble genes, select, and sleep. Not so sure about all the stops... It's pretty late where I am, I'll try again in the morning to understand it all. :blink:

P.S.
Started porting the wiki over, also checking out wikipedia for ideas to use in ours.

Not that big of a post Nums, only took a few minutes to read. :)


Endy B)

[Numsgil]

Not that big of a post Nums, only took a few minutes to read. :)

Must have just seemed bigger in my head.  Feels good to put it all in one place.

[Greven]

Num this is some very nice ideas! This will certainly make the DNA language much more powerfull! And will make DB better in many ways.
The new 'stop' multi-function is much better.

I just have one worry (maybe more but this one is what first came to my mind):

What happens when the bot evolve a 'select'-command and there are no additional stop, to stop the 'select'? How will the program handle this?

Will it be possibly in this system to have something like this:

Code: [Select]

cond [REAL]
0 1 >
stop
[JUNK]
body
1 2 store
cond [JUNK]
stopwhat will this do?
Stop the junk cond or will it stop the real one? or will it not be possible to have this?
(I think it would be great to have this!)

[Numsgil]

I'm not sure Greven, I think we just have to pick a rule that we like.  I'm in favor of cond, body, etc. not being activated if the execution flag isn't set appropriately.  So the last stop would stop the body block since the cond wasn't activated.

That is, you have to finish you current block before you can start a new one.  This isn't as hard as it could be since stops are multifunctional.  A stop that used to stop a cond can just as easily be made to stop a body or a select.

If you get to the end of your DNA and some parts haven't been 'stop'ed, the program will just close them all anyway.  Easy enough.

I'd love to get Carlo's take on this.  Although I'm afraid I have a feeling what his feelings might be  :rolleyes:

[Greven]

Oh my god! I got stars alast!!!!!!!!  :D  :boing:  :boing:  :boing:  :boing:

But what Carlo is thinking is not important, if the community like it, implement it!
But still his opion is to be taken into account, but I think he would like it, it will make DB better in many ways!

[Carlo]

I'd love to get Carlo's take on this. Although I'm afraid I have a feeling what his feelings might be

I'd just like to know what is the rational for all this proposals. You say:

This is the idea I have for expanding the language to make it easier for complex behaviors to be developed and hopefully evolved.

and

These changes hopefully will encourage more complex DNA to develop from both writers and mutations. Most bots today are still very, very simple.

That's ok. But you should be more specific about which things exactly would be better, and why. For example: how each of these changes would positively affect mutations? And how programming? What would be possible that isn't possible now, from one point of view or the other? How should mutations handle these new flow control instructions? Etc.

[shvarz]

Hmm, I feel like the new syntax is actually going to be more restrictive than the current one.  All those rules....  I'd rather relax them.  Also, I don't like the idea of Noble genes.  I think I have a more elegant solution.

What I would change:
1.  "Stop" command should not be required for anything.  When the program meets "cond" and "body" and "else", it just assumes that there was a "stop" in front of it.

Code: [Select]

cond
blah
start
blah
cond
blah
else
blah
end
should work just fine.  "stop" may still appear, but it does not have to.  One possible use for stop would be to separate real DNA from junk.

2. Instead of Noble genes we can simply have nested conditions.  There is no need for additional syntax.  Conditions place their "execution flags" on somthing like a stack (but not really a stack) with earlier values acting as your Noble genes toward later values.  The syntax will be very simple:

Code: [Select]

cond
*.nrg 5000 >
cond
*.nrg 7000 <
body
blah
cond
*.nrg 9000 <
body
blah

body
stopThe last part there is to remove the original conditions flag from stack, so that it does not transfer to the next part of DNA code.

This way you can have multiply-nested conditions without any additional commands.  

3.  I don't like the select command, because the same can be accomplished using commands that exist already.  Keep it simple.

4. Sleep command - no opinion right now.

[Numsgil]

Hmm, I feel like the new syntax is actually going to be more restrictive than the current one.  All those rules....  I'd rather relax them.

The syntax is backward compatible, so I'm not sure what you mean by more restricitve.  At the very most it's as restrictive, unless I'm missing something.

1.  "Stop" command should not be required for anything.  When the program meets "cond" and "body" and "else", it just assumes that there was a "stop" in front of it.

Very possible.  The only problem of course is that we have no way of assigning Junk DNA to stretches of the genome (assuming that is a problem of course), which is what I would like to see happen.  In this method, the DNA will or more less be expressed 100% all the time.  But as I said before, all we have to do is think up a rule system we like and go with it.  I wouldn't be opposed to this idea at all.

2. Instead of Noble genes we can simply have nested conditions.

The only reason I didn't suggest nested conditions of indefinate depth was that it seemed too powerful to me, and caused problems with the syntax of the above stop commands.  Again, I'll go with popular opinion on this one.  Either one accomplishes the same objective.

Noble genes allow you to quickly and easily see which level a cond, start, etc, is on.  As well as clearly defining the roles each is to play, since Noble BODY commands can't perform any store operations.

Also, I see problems if you want to go up a level in the nested structure.  Like:

cond
blah
..cond
..blah..
back down to the original level

but then I guess we'd use the stop command?

3.  I don't like the select command, because the same can be accomplished using commands that exist already.  Keep it simple.

Select makes things easier only if you have long runs of genes all doing the same thing for slightly different values.  Such as a multibot assigning tasks for each cycle after it's born.  In such a case:

cond
*.robage 0 =
start

stop

cond
*.robage 1 =
start

stop

cond
*.robage 2 =
start

stop

cond
*.robage 3 =
start

stop

becomes:

*.robage select
cond
0
start

stop

cond
1
start

stop

cond
2
start

stop

cond
3
start

stop
stop
Which not only is slightly shorter, but decreases the chance of the genes drifting apart during mutations.  That is, all the genes are involved in the same logical operation, so they should probably be grouped in some way inside the genome.  If you or mutations change the condition from robage to something else, the effect can effect multiple genes at once, instead of having to go through each one one at a time.

Carlo:
All the ideas are borrowed straight from computer languages.  The advantage of select is the same advantage it has in all languages, it helps combine what otherwise would be long stretches of almost identical if statements.

The advantage of sleep is that it allows single genes to work over multiple cycles.  I don't know if you've tried coordinating actions that take more than one cycle, but it isn't that easy.  sleep definately makes it easier.

Noble genes allows the genome to be constructed as a large Finite State Machine, with much broader states than allowed currently.  So you can have 'hunt' mode, 'find a mate' mode, etc, and the appropriate genes are all turned on and off quickly and concisely.

If instead you added the state condition to all genes manually, the chances of these interrelated genes drifting apart through mutations becomes more probable.  That's fine for some sims, but others would like to see more specific changes to the details instead of the structure.

The changes in DNA structure allow Junk DNA to form, helps make the structure less rigid, allowing mutations to change order of genes, stop commands, etc. more easily.   A stop can be deleted, combining two genes into one, etc.

The sleep command is my favorite.  It's relatively simple, but solves alot of the problems of forming complex multibot structures.

[shvarz]

The syntax is backward compatible, so I'm not sure what you mean by more restricitve. At the very most it's as restrictive, unless I'm missing something.

Does not your syntax require "stop" after each "cond"?  That's an additional rule.  Not a big deal for designed bots, but may be an important factor for evolving bots.

The only problem of course is that we have no way of assigning Junk DNA to stretches of the genome

Yes, we do.  That's where "stop" command comes in.  It stops execution of any meaningful DNA; stuff after "stop" is not expressed untill the next "cond", "start" or "else" is encountered.

The only reason I didn't suggest nested conditions of indefinate depth was that it seemed too powerful to me

I don't think it is too powerful, but let's hear from other people.  Remember that for evolving bots having multiple nested "cond"s would be a liability, because it makes DNA very inflexible, essentially leading to dead-ends in evolution.

lso, I see problems if you want to go up a level in the nested structure. Like:
cond
blah
..cond
..blah..
back down to the original level

but then I guess we'd use the stop command?

I am not too good with programming, but I think I see what you mean.  I think I tried to solve the same problem by having "body stop" command.  In my idea any time "body" command is encountered, the value of an execution flag is removed from the "execution flag stack" and you move up the level of conditions.  Is that clear?  I think not, so here is an example:

Code: [Select]

cond
1 1 =
'execution stack reads "true"
cond
1 2 =
'execution stack reads "false, true"
cond
1 1 =
'execution stack reads "true, false, true"
body
'true is removed from the stack,
'body is not executed, because there is a "false" somewhere in the stack
'execution stack reads "false, true"
blah-blah
else
'false is removed from the stack
'else is executed, because false was just taken out and the higher level condition is true
'stack reads "true"
blah-blah
'here would be the end of the section of DNA to which the very first cond is applied
'but the execution stack still reads "true", so it has to be removed
body
'true is removed from stack, which is empty now
stop
I certainly hope this makes it clear...

Select makes things easier only if you have long runs of genes all doing the same thing for slightly different values.

I understand the purpose of select command, but still think it is a bad idea.  For programming language it makes sense, but as far as artificial life goes, it is counter-productive.  The whole thing about AL (as Carlo pointed out, and I agree) is to assemble complex structures from simple rules and elements (also, see my sig).  So, if something can be done using existing elements and rules, then I am strongly against introducing shortcuts just for the sake of easier programming.

[Numsgil]

Does not your syntax require "stop" after each "cond"?  That's an additional rule.  Not a big deal for designed bots, but may be an important factor for evolving bots.

Yes, but current syntax requires start after cond.  Remember I'm converting "start" statements into two: stop followed by body.

I am not too good with programming, but I think I see what you mean.  I think I tried to solve the same problem by having "body stop" command.  In my idea any time "body" command is encountered, the value of an execution flag is removed from the "execution flag stack" and you move up the level of conditions.  Is that clear?  I think not, so here is an example:

I'd have to work out all the cases to see how it'd work.  It seems a bit overly complicated (ironic, I know).  If nothing else it becomes difficult to keep it all straight.  And I can't imagine what you'd want to nest more than a level on.

I understand the purpose of select command, but still think it is a bad idea.  For programming language it makes sense, but as far as artificial life goes, it is counter-productive.

It's usefulness is such a special case I can't imagine it being unfair in some way.  But if that's how people feel, I'll wait to add it until I add an on/off switch for all the commands (so it can be off if you prefer).

Personally I feel if a shortcut is legitimate, that is, it's not a macro, but a different way of approaching a problem, it should be a valid addition.

[shvarz]

Yes, but current syntax requires start after cond. Remember I'm converting "start" statements into two: stop followed by body.

So, before there was one command required and now two - things got more difficult for evolution.  In my model still only one commands is required.

I'd have to work out all the cases to see how it'd work. It seems a bit overly complicated (ironic, I know).

Yeah, it is not perfect.  I hate the fact that "body" is required to go up the level of conditions.  Some kind of special command maybe?

And I can't imagine what you'd want to nest more than a level on.

Me neither, but it is a very open system and future-proof, that's why I like it.  Having just one level with a special command for it is more restrictive.  What if you decide to allow another level later?

What we need is system that is as simple as possible, but one that still allows (at least in theory) the bare minimum:

1. Conditions and executions can go in any order and not necessarily one after another.
2. Nested conditions should be possible.

[Numsgil]

Well, in other programming languages you have operators to end the current level and go up.

VB uses 'end X' whre X is whatever block you're ending.

C uses multipupose { and } operators to show when you're entering a new level.

We can use the VB model, but remove the X in end X (one command better than two) and have cond-stop, cond-cond-stop-stop cond-cond-stop-cond-stop-stop,etc.

We'd have to start writing bot code with tabs to keep it all straight, or it becomes a mess.

I'll spend some time thinking how best to implement it.


Back onto the cond-stop method, we'll need a way to end a condition if the above is to work.  A stop operator works well for this purpose.  Without the stop operators, scope becomes impossible to determine.

That is, without stop:

cond
'condition
body
'do stuff
stop

becomes identical to:
cond
'condition
..body inside condition
..do stuff
..stop

The only way to tell the difference between the two is wethere there's two stops or one at the end, and that makes the DNA language difficult to parse and execute.

[shvarz]

You know, I was thinking along the lines of keeping things simple and using stuff that is already available, and I think that even the nested conditions are not necessary.  The same effect can be achieved using existing DNA syntax.  It is a pain to program them, but it can be done, right?  

So, what if all the shortcuts, like nested conditions and your "select" commands are converted into the conventional DNA language when DNA is loaded into a sim?  I don't see why it can't be done.  It would be a pain to read the DNA back after it evolved, but some tools can be created for converting it back into compressed form.  What do you think?  This would keep both parties happy.

The only addition to current syntax we would need is to allow stopping of a condition using "stop" command, so that DNA can flow like this:

cond
blah
stop
junk DNA here
start
blah
stop

The stop command would not even be required.  As I said, when the program meets cond, start or else commands, it just assumes that there was a "stop" right before it.
There would be no condition stack, just an execution flag, as we discussed.  If two conditions go one after another, then the second condition simply over-writes the flag.

[Numsgil]

Here's why I wanted Noble genes:

Currently the bots are a collection of equally footed genes.  That is fine for simple organisms, where each gene represents an overall strategy, but makes more complex behavior models more difficult.

For instance, say you design a bot with 20 find food genes, 10 find a mate genes, and 3 nothing to do genes.  Now say you have a condition in each one *.mood X = to turn on which instruction set you follow.

In the current system, when you run an evo sim, there's nothing to keep those 20 find food genes connected to each other.  Over time one is bound to lose that *.mood X = condition.  That's fine if you don't care how the bot evolves, but if you're trying to watch it get more complex, you'll be disapointed.

One might argue that the bot will only lose these conditions if it's in its best interest.  However, this isn't how mutations work!  Mutations select against bad, instead of rewarding good.  Simple entropy will eventually move the genes from being so directly related to each other unless doing so makes it fundamentally less fit.  But there's no guarentee of that.

If they're related to each other through a noble gene, the chances that the genes will drift apart decreases.  They're much more likely to oevolve in context with each other.

If mutations are like small explosions, these new controls are like gun barrels.  If you can concentrate the explosions in one direction, you can produce more useful work.

Looked at another way, if there are N possible mutations, there will be P such mutations that wreck any complex, heirarchial behavior system.  If the hierarchy is enforced from within the DNA language, then P decreases without effecting N.

So the reason I want these controls is not just ease of programming.  I'm hoping mutations can be herded together to encourage genes to mutate not just against the fitness of the bot as a whole, but against how it works with other genes.

I'm not sure this will have the desired effects I'm after.  It's not a law I'm espousing here, but a theory.