Author Topic: Non-Determinstic Bot DNA flow  (Read 27486 times)

Offline Carlo

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Non-Determinstic Bot DNA flow
« on: May 29, 2005, 06:45:10 AM »
Quote
First of all, I want to comment on Carlo's notion that we already have junk DNA.  This is not exactly true, becasue true junk DNA is not expressed at all, while any "junk code" that evolved bots acquire actually does affect bot's behaviour - at the very least it places some numbers on the stack, which may affect real genes later on.  So, when I am talking about junk DNA, I mean DNA that is not processed by program at all.
I really can't understand your point. Junk dna is present in DB in form of copies of genes which have been inactivated by mutations in the cond section. So it is really dna which is not processed at all. Take a look at some of an evolved dna files (for example FilansEvolved, though I don't know if it is in the standard distribution). It is full of genes which are never activated.


Quote
duplicate gene >> turn one copy off >> mutate for a while>> turn it back on>> got a new protein.

But then I thought about it some more... In DBs we are forced to use relatively high mutation rates, becasue we don't have time to wait for millions of generations for something good to appear and our population size is several hunderds at most. At these mutation rates, any inactive gene will go into complete mess very quickly and is unlikely to become anything even remotely useful for a bot.

And this is true. This is why, for example, there was (is?) a cap at three conditions per gene in the mutation routines (that is, no mutation can insert new conditions in a gene which already has three conds). The less the conditions, the more probable a gene is executed; and when a gene is executed, selection works on it again, so that it stops accumulating junk. The idea was of making possible and fast this cycle:

working gene -> gene duplication -> gene inactivation -> mutation -> gene activation -> working gene

The less the time between gene inactivation and gene activation, the more probable to select interesting features.

I'd like to propose again the non deterministic execution of genes. This means that only one gene should be executed per cycle. The gene to execute would be chosen randomly among the active genes, those which have true conds for that cycle.
Why:

1) there would be no more the mixture of sequential and non sequential execution of genes. Position in dna would count no more.

2) no more the problem of genes writing values in output location, taking effect only in the next cycle. For example, now if you have a gene which passes information through a tie and at the same time writes a flag in a memory location to tell another gene that it has done its job, you have the problem that the flag is immediately readable by the other gene, but the information won't actually pass through the tie until the next cycle. The other gene is activated by the flag if it comes after in the dna; it will be activated only in the next cyle if it comes before in the dna (I hope you understand what I'm saying, today my english is a real shit :))

3) Number of genes would count. As only one gene is executed randomly at each cycle, if the frequent execution of a gene is really important then for a bot is convenient to have multiple working copies of that gene. It's like evolving reaction times: more prompt reaction to events means more copies of a gene.

4) multiple working copies of a gene means also multiple slightly different copies of that gene working. Now, if you have two working copies, slightly different, of the same gene, the one which comes last in the dna "wins"; with non-determinism, you'd have mixes of the different effects.

5) multiple working copies of genes means faster evolution: changing a working gene can result in a new behaviour without destroying the original behaviour (still produced by the copy).

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #1 on: May 29, 2005, 08:33:16 AM »
1.  We have more than one definition of Junk DNA going around.  Here's the list
  • DNA that doesn't execute
  • DNA that doesn't exist inside a gene
  • DNA that codes for non existant commands
So shvarz is mainly talking about the second one in this case, while Carlo is talking about the first one.

2.  The only problem with one gene/cycle is bots like The One.  It's only a single gene long, and it manages to absolutely pulverize everything else.  Yikes.

And also it would decrease the period of time 1 cycle represents.  The simulation already runs slowly compared to other ALife sims.

I had an idea for synchornous DNA execution a while back.  Here's the post.

Basically there are two camps.

1.  Each chromosome acts as DNA does now.  That is, the genes in the same chromosome execute as if they were in the current system.  Then, the effects of the chromosomes are applied at the end of DNA execution.  (In case of conflict, we'd have to devise some system.  Perhaps randomly pick an action, or something along those lines).

We can create a seperate memory array for each chromosome to allow communication between genes in the same chromosome via memory just like what can happen now.  Or not.

2.  Each gene acts as an independant unit, and can't use the stack to pass values to other genes.  All memory events are applied after DNA execution.

I'm in favor of #1, because it allows current bots to still work.  I'd probably eliminate the stack's ability to carry over to further cycles, as well as prevent changes to memory from occuring until after DNA execution is over.

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #2 on: May 29, 2005, 01:47:31 PM »
Regarding Carlo's proposal.  We don't have to go as far as executing a single gene per cycle.  Executing half of all genes would do the trick almost as well.  And then of course the problem is that this may lead to consolidating functions into long complicated genes, that is to completely different outcome than proposed by Carlo.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline PurpleYouko

  • Bot God
  • *****
  • Posts: 2556
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #3 on: May 31, 2005, 08:16:25 PM »
IMO if we were to change the way that the DNA operates such that all of the genes that read TRUE are not always activated then it will completely and utterly screw up any form of bot programming.
All my carefully constructed MBs would be utterly useless as would all functions relying on activation at a precise age. And there are a lot of these.

For me this would make DB a complete waste of time as I am only in it from the genetic engineering side of things. I want my robots to be utterly predictable. I actively use the fact that an internal memory value flag can be used later in the same cycle. Most of my robots wouldn't be able to operate without this.
IMO it is one of the things that makes DB as good as it is.

I like it the way it is now

Comunications could be improved and very likely will be but please not at the expense of programming predictability or else we might just as well have a bunch of randomly moving circles on the screen.
There are 10 kinds of people in the world
Those who understand binary.
and those who don't

:D PY :D

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #4 on: May 31, 2005, 08:26:27 PM »
When I get around to programming chromosomes, this is what I'd like to do:

PY, tell me if this is a huge pain.

Within each chromosome, genes can communicate using the stack within the same cycle, just like now.  Each chromosome has its own stack, and each stack is reset every cycle.

Changes to memory locations are saved in a command stack until after all DNA is executed, so all the chromosomes appear to execute at the same time.  (THat is, store, inc, and dec don't affect what appears to be in that memory cell, but the effects are still carried out at the end of the cycle).

So same cycle communication has to use the stack, multicycle communication has to use the memory.  Right now both can do either, which seems kind of pointless to me.  By specializing each, we can encourage different uses of each.

That's what I'd like to have happen.  It would mess up a few bots (mostly yours I bet), but it would allow me to create a diploid DNA system for sexual reproduction, which would be a huge step forward for the evolutionary aspect of the program.

We could have a sexual reproduction system that's more than just shuffling every other gene.
« Last Edit: May 31, 2005, 08:28:59 PM by Numsgil »

Offline PurpleYouko

  • Bot God
  • *****
  • Posts: 2556
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #5 on: May 31, 2005, 08:55:03 PM »
What you are suggesting makes a lot of sense Num.

I don't actually care if it stuffs up a bunch of my older bots provided that the structure of the DNA is 100% predictable for writing new ones.

If I program a bot to carry out specific instructions in a specific order then that is the order I want it done in. No random gaps where a bot just spontaineously decides that it doesn't want to carry out a critical step in the program and just skips it.

If I want to send a particular message down tie number 615 on the cycle when the robot is aged exactly 23 then I want it to do precisely that, every time

Only carrying out one gene per cycle and skipping the others? Bad bad bad bad idea
Same for only performing the action from about half of them.

If a condition is met then the gene must always be carried out or else the robots lose all predictablity and become random blobs of crap rather than useful artificial life forms.

I would much rather go back to watching a bowl full of Sea Monkeys than play with such a system
There are 10 kinds of people in the world
Those who understand binary.
and those who don't

:D PY :D

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #6 on: May 31, 2005, 09:17:57 PM »
Quote
I would much rather go back to watching a bowl full of Sea Monkeys than play with such a system
And we learn what PY did before he found Darwinbots.

Offline Endy

  • Bot Overlord
  • ****
  • Posts: 852
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #7 on: May 31, 2005, 10:27:47 PM »
Sea Monkies :boing: ...That explains alot :)  :lol:  :D

On a more serious note that sounds like the best suggestion, Nums. I honestly didn't know what to think about only executing a single or even half of the genes per cycle, the memory requirements would be unreal :blink: Poor computer is already hurting when running alot of bots.

Would something like:

Chromo1
DNA
Chromo2
DNA
Chromo3
etc.

Be possible for the chromosomes? I don't think anyone would like having to deal with seperate txt files for them.

Endy B)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #8 on: May 31, 2005, 10:39:58 PM »
Definately keeping all the chromosomes in the same file.  I can see some problems arising though, as the current max DNA length is 32000.  That's huge by today's standards, but chromosomes have a way of duplicating whole long stretches of DNA.  I may have to raise the limit to a long, which is something like 2 billion.  That would be intense.  Can you imagine a bot with 2 billion DNA units?  That would be like several gigabytes of DNA code.

More likely DNA of lengths around 50 000.

Offline Carlo

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #9 on: June 01, 2005, 09:01:47 AM »
Quote
IMO if we were to change the way that the DNA operates such that all of the genes that read TRUE are not always activated then it will completely and utterly screw up any form of bot programming.

Your opinion is totally wrong. You're old enough to know well that every deterministic program can be transformed into a perfectly equivalent nondeterministic program. So the new type of execution would not screw up anything, it would just provide MORE possibilities and would be MUCH MORE elegant.

Quote
All my carefully constructed MBs would be utterly useless as would all functions relying on activation at a precise age. And there are a lot of these.

Again, totally false. Only one of the genes whose condition evaluates to true will be executed in a cycle; but you can always set conditions so that ONLY THAT particular gene's condition could be true at the right time, to be sure it is executed. The main difference is that you don't have to bother anymore about which gene comes first, which last, genes that take effect only after the complete cycle, genes that have immediate effect. More, EVERY gene which becomes active has an effect: that is, effect are not hidden by subsequent genes. If you have two genes:

cond
...
start
-1 .shoot store
stop

cond
...same cond as above
start
2 .shoot store
5 .shootval store
stop

BOTH will have effect, 50% the first gene and 50% the second gene. The interleaving between the two genes (1 cycle on average) is small enough to give the impression they are executed at the same time. This makes possible subtle tweaking and mixing of different reactions to events, which now are much more difficult to achieve. Would be great not only from the point of view of evolution, but also from the point of view of programming. Remember that if you want to obtain strictly sequential operations, you can do it in a straighforward manner, just by setting the appropriate activation conditions to genes.

Quote
I actively use the fact that an internal memory value flag can be used later in the same cycle. Most of my robots wouldn't be able to operate without this.

Are you sure you can't obtain similar, if not exactly the same effect, by breaking operations in different cycles, or grouping them in the same gene? Tell me why you use the "same-cycle" flags.

Quote
If a condition is met then the gene must always be carried out or else the robots lose all predictablity and become random blobs of crap rather than useful artificial life forms.

Again, totally false. And by the way, "artificial life" is not about programming combat bots. There's CRobots for that. So "useful alife forms" don't means "F1 bots that act exactly as I programmed them to".

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #10 on: June 01, 2005, 09:06:52 AM »
Quote
Your opinion is totally wrong.
Now children, do I have to seperate you two :P

Offline Carlo

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #11 on: June 01, 2005, 11:49:33 AM »
This is for Shvarz.
Shvarz, you've become an expert of evo sims, and probably you're the most expert in this kind of simulations. So, I was thinking of this experiment: would you try to run an evo sim on a version of the last DB modified to be nondeterministic? I think you're the most fit to run the experiment, since you have the best experience in tweaking evolution parameters and analyzing the results. It would be the best way to decide for a type or another of dna improvement (we could try the same also with other proposals).
As for the nondeterministic version, I have the routines ready, and I'm very curious about the result.
So? What do you think about that?

Offline shvarz

  • Bot God
  • *****
  • Posts: 1341
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #12 on: June 01, 2005, 11:57:33 AM »
Sure, post a version at the FTP or e-mail it to me, whatever works for you.  Would old bots work in this program?  If not, then you'll have to give me some kind of working bot to start with, I suck at programming.
"Never underestimate the power of stupid things in big numbers" - Serious Sam

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #13 on: June 01, 2005, 12:08:02 PM »
Carlo, if you'd like the darwinbots FTP username and password to upload, send me a PM.

Offline Carlo

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Non-Determinstic Bot DNA flow
« Reply #14 on: June 01, 2005, 06:13:12 PM »
Ok, I've uploaded the experimental nondeterministic version. It's on the DarwinBots FTP, in the misc section, just at the bottom.
I've tried a bit myself with a few bots (I flamma, preservans, fish school, and a tie feeder). Robots really seem to act less efficiently and in a less predictable way; but this may just depend on the fact their reaction times are longer, since only a gene per cycle is executed. The tie feeder didn't worked at all, probably relying on the execution of two genes in the same cycle. The fish school seemed to work pretty well.
Anyway, it needs to be tested by someone who knows better the actual program and the actual bots than I do. I even wasn't able to run a decent simulation: for some reason, veggie number (on the bottom bar) was always stuck to 101, except it sometimes suddenly started to grow. Maybe it has something to do with the old settings files in my DB folder or it is a bug of 2.36.

Ok. Shvarz, if you want to run some evo sim and tell us you impressions...