Author Topic: Bots with Arrays  (Read 5418 times)

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Bots with Arrays
« on: May 12, 2009, 10:05:34 AM »
I had a great idea this morning:

What if a bot used a chunk of memory and treated it like an array?

For the most part, I know it can work, but there is one problem; it wouldn't be able to use the whole array in one cycle.

I can't think of a single-cycle solution.  Of course, if you define the upper and lower bounds of the array (which, coincidentally, allow it to be added to and expanded simply by incrementing the upper bound and storing the new data to the new upper bound) you can go through one or two values in the array each cycle, but without the ability to use a loop I don't think you can be certain you will look at the whole array every cycle.

I want to find a way around that problem, but I don't know what to do.  Of course, if you could increase the number of genes in a bot every time the array size increased, then you could simply add a gene for each value in the array, but I don't think that is possible.

If there was a structure like the Codule that could be called by other genes, that would also work, but alas, that is a thing only found in DB3, which still is not up and running (But is still getting there).

Any ideas?  If not, then this is one of DB2's bottle-necks, and would drastically hinder evolution in the program.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Bots with Arrays
« Reply #1 on: May 12, 2009, 09:12:13 PM »
Look into SG techniques.  Depending on what you want to do with the data, you can just do 1000 iterations and use no-op techniques if the array is out of bounds.

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Bots with Arrays
« Reply #2 on: May 13, 2009, 07:53:46 AM »
Ehm... in a sence all the DB2 bot data is an array from 0 to 1000...
And evolution has no REAL botlenecks, and the things that slow down evolution are rarely the things we've noticed.
Evolution doesn't care about arrays, the sequence of it, or if it got the entire content of the array.
In fact nature couldn't care less, and the less precise the input is the more likely things are to work.

Even bugs in DB2 aren't a real problem for evolution, they may aswell be an advantage for all we know.
But for developping hand authored bots things are ofcourse different.
I haven't found any need for an array myself, but I think part of the reason is that all the memmory could be concieved as one big array.
For a hand authored bot I think going through a large array of data each cycle would slow down the sim speed for no good reason, and itterating through it for each cycles would take too long (Would probably require a rather large multicellular organism in a large sim in order for that to work)

But I think what I'm trying to get at is that DB has no loops ad probably shouldn't have them or it would allow programmers to create insanely slow bots.
And an array is realy no different from random data in memmory locations... Spinner uses an "array" of 5 different tie attack types and chooses one randomly from the array when attacking. (Just by chooseing a random offset to the first position of the "array")

So I guess what I'm saying is that arrays are already there in a way, it's the ability to itterate though the array that you're missing, and you can't make it since it would allow loops.
So if you have a lot of data you want to process every cycle, you'll have to manage without loops (Copy paste).
For readability I would personaly increment an offset in order to be able to use more or less the same line for each "itteration", so your code looks more like a loop wich has been unfolded.

But as mentioned, I realy don't think evolution cares, I'm pretty sure it'll access the data it needs directly, and if it needs all data every cycles it'll just access all data every cycle.

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Bots with Arrays
« Reply #3 on: May 26, 2009, 04:50:38 AM »
I was just sitting around thinking about the way dna works and how genes are defined with the whole cond, start, stop structure...
Was looking at zero bots and was noticing how an entire gene rarely had a condition, usualy the same things could be accomplished with inline conditions which seemed a lot easier for evolution to stumble uppon (Since it doesn't require a strict structure.)

Anyway got the idea that a gene wouldn't nessesarily have to be defined by such a structure, so here's my proposal for DB3 dna :
And bear with me, cause a lot of people may get stomach cramps and litle hairs raising on their neck when I say this but.... GOTO's !
And before you get into the whole loop's in dna area, I would sugest a limited use ofcourse.
I was thinking you should only be able to jump to positions that you have flagged in the code (This would make it easier for people to read the code)
And each flag should only be usable once per cycle... I'm not sure how noraml dna works, maybe it would be closer to reality if you could only jump forward.
Anyway, I know goto's are evil and all, but for dna I think it could actualy be usefull.

For viruses you could just use the flag to show which gene to charge as a virus (The gene being all code from the chosen flag untill the next flag), although I think it would be realy cool if viruses where buildt one bp at the time, so you would insert a new piece of the puzle for each cycle.
I know I heard someone mention self modifying code for DB3 which I think is an awesome idea, and I think this could actualy juice it up even more
I imaged it would work by having a new pointer type, which instead of pointing at a memmory location points at a position in the dna.
This would be usefull both for the self modifying code part (Especialy when us humans need to use it) and also for channeling viruses.
You could easily increment a pointer each cycle and add a piece of code, you can skip pieces and mix it up any way you like this way.

And viruses would be far more potent this way, a small piece of code can rearange your dna (Ofcourse you can always add a defence for this.)
Also this way a virus infection wouldn't change the amount of genes unless it contains a flag. I don't know if viruses IRL are actualy inserted as a gene or into a gene, if it has to be a gene the virus could just get a random flag.
Anyway the self modifying code part is also bound to make viruses and viral defences more interesting (Especialy if you have a pointer type for looking at specific bp)


Also if you want to go all out on jumps, you could just have a cap on how many bp can be rerun via a loop. A simple version of this could just be to add up the amount of bp jumped backwards (Jumping forward should be free I think), and if the jump you're trying to execute makes your total backwards line jumps in this cycle exceed the cap then you wouldn't be able to jump.
Personaly I prefer this idea actualy, now that I think about it... you could still allow the use of flags, but the point would be to make movement in the code more free and allow some loops with limited use per cycle. I think this would make the dna more powerfull, but I don't know if it's realistic to have loops in dna... would be very usefull though.
« Last Edit: May 26, 2009, 04:56:14 AM by Moonfisher »

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Bots with Arrays
« Reply #4 on: May 26, 2009, 08:18:12 AM »
Codules will basically facilitate this.  They can be called from within other codules, so they can be called recursively to simulate a loop, or can be used like a goto.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Bots with Arrays
« Reply #5 on: May 26, 2009, 10:12:40 AM »
There should still be a limit though... at the very least to avoid endless loops.
Not sure exactly how codules work... is it just the ability to use functions ?

I can think of 4 descent ways to limit it... either put a cap on how many times you can call a codule per cycle, put a cap on how many times the same codule can be called in the same cycle, put a cap on how many codule bp can be executed per cycle.... OR let a cycle execute only a fixed amount of bp, so if your code is 1000 bp and each cycle processes 100 bp it'll take you 10 cycles to run through your code, you would still execute actions every cycle, but only the ones you've executed from your code in that cycle. If your code is 50 bp it would be able to run through it twice in a cycle, but you'd still only be able to execute actions once per cycle. The lower the amount of bp executed in a cycle, the more interesting I think it would be... if you only ran 1-10 bp per cycle then the dna length would get far more important. You could always make up for it by adding cooldown to certain actions like shooting and such. (And only zeroing out key mem locations if the action was executed)

Personaly I think the last option is the best one, it would also set a more constant time for code execution, so you don't end up with huge slow bots like Guardian...
And it would work well with functions, since you'll want to keep a tight main loop and only call the functions you realy need, so you can think fast in battle.
It's probably also more work getting it done, since you need to balance how many cycles different actions take with how many bp are executed per cycle, but I think it would be worth it  

Also I still think the bp pointer type and charging virus code manualy would be usefull and help make things interesting. I think self modifying code is one of the things that's realy going to make things more ineteresting in DB3 and it would be nice to have tools to take advantage of it. I definately think self modifying code would be a lot easier to controll with a pointer for it, currently we only have values and pointers to memmory locations. With a pointer I could choose to overwrite the code in one location with code from a different location just by iterating through it for each cycle changing one bp at a time.

So those would be my revised sugestions :
- 1 bp executed per cycle, with different cooldown on different actions.
- pointer type for locations in the code
- and tailored viruses charged one bp at the time

The worst issue I can see for the 1bp per cycle thing is the movement and physics and eyesight and all the other stuff slowing things down. Best easy answer I can think off is to only update movement, physics and all that every X cycles (Something that fits well with the cooldown on all the actions).

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Bots with Arrays
« Reply #6 on: May 26, 2009, 10:30:18 AM »
It will probably limit by putting a maximum size on a call stack.

When you call more than your share of codules, they just stop listening to the calls.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Ta-183

  • Bot Destroyer
  • ***
  • Posts: 105
    • View Profile
Bots with Arrays
« Reply #7 on: May 26, 2009, 06:51:34 PM »
This would all be a crapload easier if we had an IDE. Anyone want to chance building one?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Bots with Arrays
« Reply #8 on: May 27, 2009, 08:56:18 AM »
Quote from: Moonfisher
There should still be a limit though... at the very least to avoid endless loops.

Basically you can't call a codule that is already on the call stack (the call just fizzles).  The only downside to this method is that you can't call the same codule recursively.  The other methods you listed work too, but IMO they're less elegant.

Quote
Not sure exactly how codules work... is it just the ability to use functions ?

More like sub routines, but yeah, basically.  There's a "root" codule, which is basically what the DNA is now.  You can then call other codules, creating a call stack which remembers where in the previous codule you were, on and on down into your code.  If you call a non existent codule, it tries to find the next "closest" codule to call instead, so it should play nice with evolution.

Quote
Personaly I think the last option is the best one, it would also set a more constant time for code execution, so you don't end up with huge slow bots like Guardian...
And it would work well with functions, since you'll want to keep a tight main loop and only call the functions you realy need, so you can think fast in battle.
It's probably also more work getting it done, since you need to balance how many cycles different actions take with how many bp are executed per cycle, but I think it would be worth it  

This is how most other ALife sims work.  But from what I've read, this actually favors "gray goo" bots over complex behavior.  Evolve 4.0 had more successful sims when "free instructions" were increased.  This is actually one of the things about Darwinbots which I think makes it work so well.

And if you think in terms of real life, DNA is a massively parallel computer.  The longer the DNA gets, the more processing power it has, not less.

Quote
Also I still think the bp pointer type and charging virus code manualy would be usefull and help make things interesting. I think self modifying code is one of the things that's realy going to make things more ineteresting in DB3 and it would be nice to have tools to take advantage of it. I definately think self modifying code would be a lot easier to controll with a pointer for it, currently we only have values and pointers to memmory locations. With a pointer I could choose to overwrite the code in one location with code from a different location just by iterating through it for each cycle changing one bp at a time.

I've been hesitant to go down that way, for various reasons.  Mostly because it's a super weapon, which means the code has to have special exceptions everywhere to make sure it's not abused.  There are probably clever ways around those problems, but I don't want to add it just for the sake of adding it either.  The main use I can think of would involve viruses, and for DB3 I'm specifically working to remove the need or ability to self police your genome (stronger defenses against virus infection, and inability to self modify your genome at all.  Viruses would work less like retro viruses (injecting into your genome) and more like normal RNA viruses (another genome in your bot vying for control)).

But if you (or anyone) can think of specific use cases I can probably design around them.

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Bots with Arrays
« Reply #9 on: May 27, 2009, 11:47:13 AM »
Quote from: Numsgil
Basically you can't call a codule that is already on the call stack
But what if I have 3 codules A, B and C, and A calls B, B calls C and C calls A ? (The classic downfall of some Garbage collectors)

Quote from: Numsgil
This is how most other ALife sims work.  But from what I've read, this actually favors "gray goo" bots over complex behavior.  Evolve 4.0 had more successful sims when "free instructions" were increased.  This is actually one of the things about Darwinbots which I think makes it work so well.

And if you think in terms of real life, DNA is a massively parallel computer.  The longer the DNA gets, the more processing power it has, not less.
I agree that IRL longer dna should mean more processing power, but I was mostly refering to the simulation speed. (Also a bot with more dna wouldn't have less processing power, just the same as shorter dna (Making it slower).)

But I think the issue is just how often you choose to update the world. For example if you only updated every 32000 cycles, even the longes possible bots would be able to comlete their code.
But the advantage would be that self modifying code in a small bot can accomplish a lot internaly during that time, and multibots can comunicate and stuff like that. (Since actions that don't affect the physical worls would be able to have a lower cooldown period.)
The issue I was most worried about would be the dna being out of sync with the update of the physical world, but I don't think it should be an issue as long as sysvars only get errased once they've been used.
If you updated every 10K cycles I think most bots wouldn't even notice.
For some handauthored bots it would probably help to have a flag being set every time the physical world has been updated (Although there should be plenty of other ways to tell).
But after thinking about it I think viruses would probably be the main issue, it would be a lot harder to create viral defences. You wouldn't just be able to block negative effects in the last gene, you would have to check for infections every time the physical world is updated.
So I know it makes things complicated, but I don't think evolution would suffer, and it would make some aspects far more interesting.

Quote from: Numsgil
I've been hesitant to go down that way, for various reasons.  Mostly because it's a super weapon, which means the code has to have special exceptions everywhere to make sure it's not abused.  There are probably clever ways around those problems, but I don't want to add it just for the sake of adding it either.  The main use I can think of would involve viruses, and for DB3 I'm specifically working to remove the need or ability to self police your genome (stronger defenses against virus infection, and inability to self modify your genome at all.  Viruses would work less like retro viruses (injecting into your genome) and more like normal RNA viruses (another genome in your bot vying for control)).

But if you (or anyone) can think of specific use cases I can probably design around them.

Well I don't know what you have planned in that area, and it's hard for me to speculate till I've had a look at how the dna will work in DB3.
I imagined the pointer would be usefull for removing infections and for manualy charging virus code. Figured it might make evo sims more interesting.
But it sounds like you may be rethinking the self modifying code idea, and generaly the way viruses work. So it's hard to say anything realy.

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Bots with Arrays
« Reply #10 on: May 27, 2009, 12:53:48 PM »
When he says that a codule can only appear on the stack once, he means that if the stack looks like: A,B,C : and you add A to the top, you end up with: A,B,C : because the second A is ignored.

Since a codule calling on another codule remains on the stack until all of the codules IT calls AND itself have completed executing, there should be no way to get stuck in an infinite loop.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Bots with Arrays
« Reply #11 on: May 27, 2009, 02:42:10 PM »
Quote from: Moonfisher
Quote from: Numsgil
Basically you can't call a codule that is already on the call stack
But what if I have 3 codules A, B and C, and A calls B, B calls C and C calls A ? (The classic downfall of some Garbage collectors)

As Prsn says, it's ignored.  The term I use for this is "fizzle", which is borrowed from the Magic the Gathering card game I played in my youth.  Other commands can fizzle, too.  10 mult, for instance, will leave 10 on the stack (mult fizzles).  false 10 20 store will take 10 and 20 from the stack, but no store action occurs.  (This is in DB3 DNA).

Quote
Well I don't know what you have planned in that area, and it's hard for me to speculate till I've had a look at how the dna will work in DB3.
I imagined the pointer would be usefull for removing infections and for manualy charging virus code. Figured it might make evo sims more interesting.
But it sounds like you may be rethinking the self modifying code idea, and generaly the way viruses work. So it's hard to say anything realy.

You can play with basic DB3 DNA using the command line interpreter.  It doesn't have codules or any of the other macro features, though.

Viruses wouldn't get inserted into the DNA.  Instead they'd form a new chromosome, which is essentially another DNA strand which runs in parallel (no interaction is possible between chromosomes except through the bot's memory, and then only during the next cycle).  It would be treated similarly to diploid bots.  I haven't totally decided how conflicting commands from different chromosomes might be resolved.  The idea is that each chromosome is like a separate program.  They have their own protected memory space, but they share the same hardware.  And their protected memory space gets resynced every cycle.

Not sure if I explained any of that well   The two primary purposes for self modifying code I can think of would be either viruses (offense and defense), or aggressive point mutations of a certain "magic number".  I'm specifically trying to prevent the need or ability in regards to viruses, since it tends to promote obtuse code which is robust to viral infections.  My goal is for it to be safe to write simple, straightforward code (there's sort of a maximum behavioral complexity you can write a bot for before the code gets too complicated to deal with).

The point mutations of "magic numbers" is a reasonable use case, but it wouldn't work very well if you had to rely on pointers, since the pointers themselves would drift after insertion/deletion mutations.  One idea might be that bots can specifically "hyper mutate" individual codules.  The codules provide a "handle" to an arbitrary grouping of DNA bps, so a codule might have just a single number in it and the bot can mutate it.  But there are some niceties as far as tracking heritage when DNA is static except for mutations.
« Last Edit: May 27, 2009, 02:45:30 PM by Numsgil »

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Bots with Arrays
« Reply #12 on: May 27, 2009, 04:01:47 PM »
So... there would be no loops at all...
Only advantage then would be that you can structure your code a litle easyer... I guess it could help evo sims though.
Sounds cool that other commands can fizzle by accident though, will probably make evo bots more interesting and it'll challenge bot coders to create safer code.

And the virus idea sounds good. One idea for determining conflicting actions could be to base it on the strength of the virus shot and the virus defences. So you can be badly hit and the virus has an 80% chance of "winning" an action, or you can suffer a weak hit and it'll only win 10% of the time. So the strength of a virus shot would be worth more than extra lifetime.

And the pointer wouldn't slide too much if locations where relative to the position in the code (Wrapping when exceeding the code length).
Then it would only slide when new code is inserted between the pointer code and the code it's pointing at. And as far as evolution is concerned it may be an advantage at times when a useless pointer suddenly points at something usefull. But mostly I'm thinking of a line like this :
110 inc
100 rnd &110 store

OR

100 rnd & 300 rnd & store

By having commands that execute things from random locations in the code the chances of finding something usefull are higher.
Half the evo bots I've seen use shifting operators to get more random results, and have complex lines that manage to end up with just the right odds to accomplish what needs to be done.
This is the effective code for the zbot I've been running lately. It's been compressed from over 100 bp to 26 (And I cut away the last bits of useless code)

 .tie dec
 .shoot dec
 59 << *.robage 192 ceil >> rnd << << ++ store

I tryed messing with everything on that line, and it's untouchable, I can't even change what seems to be constant values, like 59 <<, I suspect it's because it can be either 118 or 119.
Any changes to it will make it weaker, all the giberish has a clear purpose.
So it seems that evolution actualy prefers confusing and random code, probably because specialists tend to die in the long run.


As for self modifying code I was thinking there are some plusses where evolution is concerned, since a bot can go through a lifespan changing it's dna as it gets older. I would probably sugest seperating the inherited genome from the executed genome and have seperate commands for changing them. Theres a difference between wanting to create different offspring and the evolution of your own genome as you grow "old".
But I can definately also see all the issues of tracking different kinds of changes to the genome and understanding how an evo bot works by having to track it's internal changes. Viruses would be less of an issue if they work the way you described above though.
So I realize it's harder to observe whats realy going on in the code, but I often find *.robage involved in the actions taken by zero bots, so it seems like age is often a factor, and changing behavior can be realy usefull in evolution.
Also being able to change offspring dna could be usefull for adapting offspring to the current environment.

At the very least if self modifying code is off the table then I would sugest changing the way RNA works and allowing you to apply an "offset" to a specific bp in the genome for an offspring to turn it into a different action or value. The offspring can then change or shed the offset in it's code when it produces offspring of it's own. (Again this would work by changing the genome that will be inherited by offspring, except you would apply the change as an offset, so the offspring has the ability to revert back to normal for future offspring.)


Anyway I'll go play with that interpreter...