Non-Determinstic Bot DNA flow

[Carlo]

Every one of these genes has to be 100% able to operate on every cycle or the robot does absolutely nothing.
Never mind slow reflexes. It just doesn't react to anything... EVER. it just sits there and does absolutely nothing.

PY, that's what happens when you use undocumented and deprecated techniques like using the stack to make genes communicate. There's nothing your combat bot can do that a nd bot can't - maybe just a bit slower. But it needs a different kind of programming. You shouldn't be so afraid of changes.

By the definition of the non-deterministic system, only one of these genes can activate in any given cycle, therefore it can never turn at all under any circumstances.

By the definition of a non deterministic system, you can't leave values in the stack for other genes, because it is erased at each cycle!

Simple little things like Diplomaticus Diplo may still work reasonably well but that is because they are incredibly simplistic to start with.

They are perfect for DB. DarwinBots, as the name suggests, is about evolution, not super perfect combat bots. You can use it as a programming game as much as you want, but you can't modify it to be a better programming game or favour combat to evolution. DB is _artificial life_ and that means that every other use you make of it other than evolving robots, is you personal misuse.

[Carlo]

Before it saved 15 in .up on every cycle and now only every 3rd/4th cycle, so of course its speed was lower.  I also had to adjust the energy flow, because Alga were now spending 3-4 times less energy/cycle than before.

Ok, that's normal. Obviously you have to tweak sim parameters to match the changed conditions.

The more active genes bot has, the slower is the time flow.  This is a problem in itself, as you are driving evolution to either reduce the number of potentially active genes or to make each gene more complex.  A duplicated copy of a gene is a huge liability, because without contributing much it slows down bot's reaction time.  It should not be this way.

I don't think so. Say that a robot has three different active genes in a certain condition. Each of the three active genes has 1/3 chances of being executed. Now, if one of the three genes gets duplicated, the active genes become four, each with 1/4 chances of being executed; but, since the two copies of the duplicated gene are identical, now that gene has 1/2 chance of being executed, while the other two have 1/4 chances. So, a gene, duplicating, increases its expression in the phenotype, decreasing that of the other genes. So that an equilibrium will be found between the importance of the various reaction to events. Correctly balanced mixes of different reactions should be easily selected with this system.

Every one of the duplicated genes still contributes to the overall behaviour, because they are under selective pressure. They don't become junk immediately as it is now usual. And a gene that remains functional, is also a gene which has more chances to mutate in an effective way. And mutations contribute to the behaviour. Etc.

In addition, it is impractical from our point of view, because the speed of simulations is essentially slowed down by a factor equal to the average number of active genes.

This is true. However, I'd prefer a more elegant and more effective system working slower than a high speed system which is cludgy and works bad. The problem here is simple to solve: I'd slow down physics. Robots really move too fast in standard conditions for ND execution. I'm running a high friction sim right now, with robot moving MUCH slower... and it's interesting, robots after only 240K cycles adapted perfectly to the new environment, put against the original ones they completely wiped them out.
I've set high values for genes duplication and deletion (1 in 200 for duplication, 1 in 200 for deletion, E_Diplo had 10 genes at start); now the genes are 16,  this means that an increase in genes number is positively selected, as I said before.

As I said, in theory the non-deterministic processes should be moved further down into the guts of simulation, so that the execution of different genes appears to be parallel and happening at the same time.

I surely agree. We could, for example, make genes execute each time in a different order. This would _discourage_ relying on the execution of a certain gene before in the same cycle; but on the other hand the execution would actually happen, sometimes. So, what happens if a gene sends a message through a tie, and signals to another gene that the tie now can be destroyed? Sometimes the other gene will read that signal _after_ the message has passed through the tie, but other times they will read it _before_, and destroy the tie before the message passes through it.

[Numsgil]

IF you really want ND to work right, the problem is thus:

1.  All commands are executed at the end of every cycle.  So complex commands cannot use more than one gene to work properly.

If commands are instead executed every n cycles, where n is roughly the number of genes the bot has, the genes can work together without necessarily communicating.  Just an idea.

Obviously another problem is the nature of DNA execution, which leaves modern bots in the grind, so to speak, but that's inherant in the system.
We're reaching a stalemate position, so we should probably just vote and decide if this is the direction we want DB to move in.

I vote nay, for the simple reason that a chromosomal system such as I outlined solves all the same problems with non of the problems (I'm not even sure it has problems.)

[Carlo]

1.  All commands are executed at the end of every cycle.  So complex commands cannot use more than one gene to work properly.

If commands are instead executed every n cycles, where n is roughly the number of genes the bot has, the genes can work together without necessarily communicating.  Just an idea

No-o. If commands are executed every n-th cycle, things become exactly as they are now. One of the main reasons to move to ND execution, is that this way commands are executed right after the gene execution stopped: this means that the other genes are sure that the operations have been performed and that a physical effect has been produced. DNA now is only partially working like that: if you have two genes, the first is correctly aware of operations made by the second with up to date physics, but the second is not. When I programmed vermis_patavinus, which has a complex structure, I had to program its embryonic development backwards (with genes activating first placed in the last positions of the dna), to be sure that their activation sequence was coherent with the changes in the outside world.

By the way, can you make an example of a complex command that needs more than one gene to work _properly_?

I vote nay, for the simple reason that a chromosomal system such as I outlined solves all the same problems with non of the problems (I'm not even sure it has problems.)

Your chromosome idea moves nondeterminism from the level of the gene to the level of groups of genes. Instead of having one of the active genes executed, you have one of the cromosomes (in fact each a dna on its own) randomly picked and executed. But if an executed gene in my system is, at least, an active gene, why should be a chromosome preferred to another one? Chromosomes aren't active or inactive. You may have two chromosomes, one with just one gene always active (or even without any active genes!) and one  plenty of genes. And you'd have each chromosome (and therefore, each gene) executed on average 1/2 of the times. You won't be sure of the execution of a gene, nor of the fact that an executed gene has produced any physical effect. So it seems to me that your system manages in combining together the worst defects of both systems, deterministic and nondeterministic.

[Numsgil]

By the way, can you make an example of a complex command that needs more than one gene to work _properly_?

Well, since The One is a single gene and does just fine, no, I can't.

But there are processes that are made easier by different genes.  Forming a multibot being a good example.

Your chromosome idea moves nondeterminism from the level of the gene to the level of groups of genes. Instead of having one of the active genes executed, you have one of the cromosomes (in fact each a dna on its own) randomly picked and executed.

...

So it seems to me that your system manages in combining together the worst defects of both systems, deterministic and nondeterministic.

No, you misunderstand.  ALL the chromosomes are executed at the same time.  They just can't affect the cell until ALL other genes have executed.  So, as far as they're concerned, they're all happening at the same time, which was your original goal, right?  The only linearity at all is inside the chromosomes, where the stack allows values to be passed from gene to gene within the cycle.

At first I saw this as a liability.  Real chromosomes aren't executed linearly, I thought.  Since the proteins they inscribe are floating around in the cell, all can work at the same time, with one not operating before another.  But later I learned, researching mutations and crossing-over, that expression of a gene, that is, it's transcription into a protein in the first place, can be changed if it moves location in the chromosome.

This implies that the transcription of genes is at least partly controlled by the genes around it.  Probably transcription inhibitors at least partly work for genes around their primary target, or work for large locations of on the chromosome, or something along that line.

So while one gene passing stack values to another isn't 100% realistic, neither is it all that unrealistic, and bots aren't necessarily real creatueres anyway.

Where conflict arises in my system, perhaps two store commands to .up, we have to define a system for which command to follow.  Randomly picking one could work, and follows alot of the consequences for ND DNA, but there are other possibilites too.  We could give preference to one value over another.  We could select the most numerous command every time.  We could pick the command closest to zero, or furthest from zero.  We could pick the command with a value closest to the bot's nrg levels.  We could pick 101 over all other numbers because we like the way it looks.  Each has different implications to DNA evolution and bot execution, so we'll have to pick a method carefully.

[Carlo]

Well, since The One is a single gene and does just fine, no, I can't.

Perfect.

But there are processes that are made easier by different genes.  Forming a multibot being a good example.

And this is the worst example you can take. Because multibots are particularly negatively affected by the current system, since they have to strictly coordinate actions which happen both inside and outside the robot, that is, in other robots. How can they manage to do that, if a gene don't know whether something really happened yet or not? As I told you, I had to write the dna of v_patavinus backwards to make it work properly. This wouldn't happen with the new system.

ALL the chromosomes are executed at the same time.  They just can't affect the cell until ALL other genes have executed. 

Ah. I thought for a long time about a system like that (no need for chromosomes, though, it can perfectly apply to genes only). The problem is that each gene should read values from a memory array and write back to a different memory array. And at the end of each cycle, you'd have to copy all the write memory into the read memory. Horribly time consuming. You may design an appropriate structure to hold the (location, value) couples written by a dna, and then just rewrite them on the true memory array at the end of the execution. Would be fine, but anyway won't solve the other problem, as you point out: that is, in case of conflicts you'd have to choose which value to store in the final memory, and this would be nearly impossible. Which compromise to take between -1 and -2 in the .shoot location? Or between two different tie addresses when using ties? And, finally, PY would cry, anyway.

[Numsgil]

And this is the worst example you can take. Because multibots are particularly negatively affected by the current system, since they have to strictly coordinate actions which happen both inside and outside the robot, that is, in other robots. How can they manage to do that, if a gene don't know whether something really happened yet or not? As I told you, I had to write the dna of v_patavinus backwards to make it work properly. This wouldn't happen with the new system.

Structured multibots would seem to me to be harder to create in a ND universe.  Unless you have a drastically different design paradigm.  In my experience, multibots work by:

cycle 0: do something
cycle 1: do something
cycle2: do something

all very structured and quite precise, especially for larger multibots.

Ah. I thought for a long time about a system like that (no need for chromosomes, though, it can perfectly apply to genes only).

Yes, you don't have to use chromosomes.  But doing so allows both for backward compatibility with PYs stack intensive genes and for more involved reproduction procedures in the DNA, such as realistic meiotic reproduction and crossing over.  It's really just a step in a process moving towards a more complete sexual reproduction model, which has always been a hurdle for DB.

You may design an appropriate structure to hold the (location, value) couples written by a dna, and then just rewrite them on the true memory array at the end of the execution. Would be fine, but anyway won't solve the other problem, as you point out: that is, in case of conflicts you'd have to choose which value to store in the final memory, and this would be nearly impossible.

But this problem is well known and understood.  Specifically in multithreading theory.  Note how our problem and the problems of singlethreading OSs are similar.  Makes sense that a similar solution should be considered.

Actual programs with threads competing for resources have different strategies for which to give preference to.  Some favor processor intensive threads, some the opposite.  Semaphores can be used to regulate shared data, etc.

We don't have to actually create semaphores (although we could.  That's a possible solution I haven't really explored), but we can model the end statistical effects on which commands are executed.  And, worst comes to worst, and we don't have any good idea, just picking a random instruction is just about as good as ND DNA as far as removing the linearity between gene execution.

And, finally, PY would cry, anyway.

PY's already acquiesced for a chromosomal sytem, so we don't have to worry there.   :P

[shvarz]

since the two copies of the duplicated gene are identical, now that gene has 1/2 chance of being executed, while the other two have 1/4 chances

Damn, I should have thought of this myself! :)

Well, these are very good points and interesting discussion from everyone.  One thing is still not clear for me (because I don't program bots): It seems like the major advantage of ND system would be an appearance of several processes happening at the same time in parallel.  Why would we want this?  And why is current system so bad?  I would like to see some kind of simple example of the power of the new system as compared to the old.

[PurpleYouko]

And why is current system so bad? I would like to see some kind of simple example of the power of the new system as compared to the old.

I second this completely.

And another thing. Since when is the real universe non-deterministic?

OK so at the quantum level it may be for for all intents and purposes, everything above that is totally deterministic anyway.

Even with that, the argument of whether the universe and everything in it, is 100% deterministic or not, is still raging in the highest echelons of physics research.
Even proponents of non-determinism wouldn't go so far as to suggest that macro-molecules like DNA don't act as if the universe is totally deterministic.

You have to go way below that to find any sign of non-determinism.

If you want realism then I would say that you need determinism along with parallel processing with the end result being the average of all the separate chains of determinism.

Num's proposed system seems to satisfy this pretty well.
I just don't see any realism whatsoever in just arbitrarily picking one or even a few genes to allow to activate on any given cycle. In reality there is nothing truly random about VB. We have been over this before on another thread. By setting the seed number you can exactly reproduce any sim you like. That won't change in the least if you randomly drop perfectly good genes for absolutely no good reason.

I just see absolutely no point in it.

[Sprotiel]

OK so at the quantum level it may be for for all intents and purposes, everything above that is totally deterministic anyway.

It's the other way round !! Quantum mechanics is totally deterministic. At higher levels, thermodynamics comes into play and it gets random.

[Numsgil]

No, Quantum Mechanics suffers from a great deal of true uncertainty.  It is probably the only science that relies so heavily on probability functions instead of deterministic functions.

From wikipedia for quantum mechanics:

Generally, quantum mechanics does not assign definite values to observables. Instead, it makes predictions about probability distributions; that is, the probability of obtaining each of the possible outcomes from measuring an observable.

It is only on the quantum level that unpredictability, and thus by definition non-determinstic phenomenae, are observable.  Wether or not they are really non-deterministic, as PY points out, is still debatable.  They could be following laws we don't understand.  But at the moment probability functions works well.

The ND nature of electrons can be seen in how some can escape from a black hole through Quantum Tunnelling.  It's because the electron is not in a deterministic state that it can do this.  It's because defining the electrons kinetic energy and position exactly simoltaneously is impossible (or maybe this is a consequence of the former.  I'm not sure).

[Sprotiel]

No, Quantum Mechanics suffers from a great deal of true uncertainty.  It is probably the only science that relies so heavily on probability functions instead of deterministic functions.

No, the quantum evolution of particles is totally deterministic and predictible. It's only when you interface quantum mechanics with classical physics that probabilities intervene. Probability distributions are much more important in statistical physics, for instance.

The ND nature of electrons can be seen in how some can escape from a black hole through Quantum Tunnelling. It's because the electron is not in a deterministic state that it can do this. It's because defining the electrons kinetic energy and position exactly simoltaneously is impossible (or maybe this is a consequence of the former. I'm not sure).

Hmm... I won't discuss electrons tunneling out of a black hole since this requires a quantum theory of gravitation, which doesn't exist, but quantum tunneling in general isn't really related to non-locality (I assume that's what you mean with "non-determinism"). Besides, quantum tunneling is treated perfectly deterministically. The fact that the electron either crosses the barrier or not is a consequence of its subsequent interaction with matter.

[Numsgil]

Determinism isn't the atomicity of a state, it's the determinability of a state.  Hence the name.

If I show you an electron, and say 'here's how fast it is, with X certainty, where is it?' you can only give me Y certainty that it's at a location.

That is, Determinism is unerring predictability.  And that's something particles don't have on a subatomic level.  You can be reasonably certain that a large number of electrons will follow a certain pattern, but the lower your sample size, the less certain you can be on how it's going to behave.  (Which reminds me of the Foundation series and psychohistory).

My point with quantum tunneling is any single given electron has a small probability to be in a completely different location, not based on it's Newtonian possibility of getting there.  You can't predict if electron Z is going to do it, but you can figure out the end net effects of massive amounts of electrons from a probability function.

Note that quantum tunneling is quite real and is the basis of tunneling electron microscopes, so it's not some crazy theory, but has physical evidence to back it up.

[shvarz]

Well, let's leave the determinism versus non-determinism aside, it is not really important for our purposes.

To PY:  The idea is not to create non-deterministic universe, but to allow parallel processes to occur.  What the proposed system wants to accomplish (I guess) is that each cycle is broken down into several mini-cycles.  During these minicycles different genes can influence the behaviour of the bot simultaneously.  One gene says: let's go forward 10 steps, another gene says: no, let's go backward 3 steps.  Both are working during mini-cycles, but when you look at the final result of the cycle, you see that bot moved 7 steps ahead.  This is a simple example and can be accomplished in ways that are easier than the one proposed by Carlo.  But I assume that there are things that can only be accomplished using Carlo's system and that's why I asked for an example of such a thing.  Maybe firing several different shots at the same time (but this too can be accomplished in an easier way).

P.S: The whole thing will remain completely deterministic, that was just a poor choice of words by Carlo.  The interaction between different genes will go to hell as a side effect of the new system and I personally would sorely miss that, because it is such a powerful system  and nothing of equivalnce is proposed for the new system.  :(

[Carlo]

The whole thing will remain completely deterministic, that was just a poor choice of words by Carlo.

Let's start from here. I noticed some confusion deriving from the use of the term "nondeterminism". Confusion is due to the fact that unfortunately -and strangely enough- there are at least two different uses of the concept of nondeterminacy in computer science. Nondeterministic finite automata and ND Turing machines are models in which the computation follows different branches at the same time. Every time a branch point is encountered, the machine "forks" in two different and parallel computations. This model of computation is sometimes called "angelic nondeterminacy", and clearly it's what you were thinking of (also because it's by far the most known).
A different use of "nondeterministic" have been introduced by Dijkstra in 1975. Dijkstra's nondeterminacy is based on guarded commands, that is, blocks of code activated by a condition. If more than one condition is met, only one of the blocks is randomly chosen and executed. This is called "demonic nondeterminacy". And this is the kind of nondeterminacy I am talking about.

There's a little explanation of how guarded commands work here:
http://en.wikipedia.org/wiki/Guarded_commands

The interaction between different genes will go to hell as a side effect of the new system and I personally would sorely miss that, because it is such a powerful system and nothing of equivalnce is proposed for the new system.

This is completely false. Interaction between genes would be perfectly possible, using memory locations.

For example, reproduce and shoot one info particle to the son:

Code: [Select]

cond
   *.nrg 6000 >
start
   50 .repro store
   1 100 store
stop

cond
  *100 1 =
start
  0 100 store
  familyloc .shoot store
  myfamily .shootval store
stop
This shows also the elegance of this system. If you want to do the same thing with the current system, you face a few problems. First of all, you have to know that gene 2 is executed right after gene 1, before any  external action. Then, you may ask yourself, well, but is the shot  created _before_ the son is deployed, or is it created _after_? In the first case, maybe the shot won't hit the son. If you want to be sure of the correct order of the actions, you have to put gene 2 before gene 1 in the dna. This makes you sure that the requested actions are performed in the correct order.

Both are working during mini-cycles, but when you look at the final result of the cycle, you see that bot moved 7 steps ahead. This is a simple example and can be accomplished in ways that are easier than the one proposed by Carlo. But I assume that there are things that can only be accomplished using Carlo's system and that's why I asked for an example of such a thing.

I think there isn't a single example like that you're asking for. You can always find a new way to mix up the results of different genes; you can make a mean or a sum or a complete overwrite of the different values falling in a same memory location, depending on the location; you can make possible to shoot two, three, or one hundred shots within a single cycle; deciding that if the shot is -2 or -1, then shootval is calculated as a mean, if it is  >0 then there's an overwrite, and so on. You'd then have the problem of deciding how many shots you can shoot in a single cycle, because shooting 100 shots against the enemy in a single cycle wouldn't be fair. Etc. Then you'd have to do the same thing for every other sysvar or memory location. These solutions are possible, but cludgy, inelegant. When I designed the dna model, I made a mistake. I wanted a daemon system, like that described by Dijkstra, but I made it internally sequential. I thought it was right to have multiple genes activating at the same time. It's not. It's even worse because all the physical actions are taken after a complete cycle has been executed, so that some genes are aware of them (those which come before of the genes producing physical effects, because they will be executed again only in the next cycle) and some not (the genes coming after).

So, the advantages of the nondeterministic system are

1) It's elegant, coherent. Makes understanding DarwinBots much, much simpler. It's a known model.

2) Genes have immediate physical effect. Their order is not important anymore. If a gene which takes at the same time physical and non-physical actions has been executed, you are sure that both actions have been performed.

3) Genes don't cover reciprocally their actions. Each active gene has effect. From the point of view of evolution this is very important, because genes duplications will bring to existence new working genes, not just dead copies, ready to be turned in junk dna.

4) Behaviours will mix. A gene for shooting attack particles can duplicate and mutate in a gene for sending disturb values to the victim. Both will have effect, and effects will mix. The correct balance between the two actions can be reached duplicating further one of the two genes.

5) Time becomes an important factor. A gene duplication changes the power balance of genes inside the genome. Duplicating a gene means giving it more execution time, subtracting it from that of the other genes; more active genes allow more complex or balanced reactions, but at the expense of reaction times.

6) May introduce the new choice between fast'n'simple and complex'n'slow robots. Also specialization may become more probable, because specializing would mean becoming faster. For example (maybe an idea for the future) the sequence of actions needed to perform photosynthesis may slow down a predator too much to let it follow a prey, so that it has to choose between the two ways of feeding.