Competition: Programing waste eater Nanobots

Have a question or want to show off your project? Post it! No Registration Necessary.  Now with pictures!

Threaded View
http://www.symantec.com/specprog/university /

Ok, the robots are virtual, but the 10K prize is not. Unrust your assembler
skills.

Short deadline, so if you want to participate do it soon.

Cheers

Padu

PS: I have nothing to do with Symantec, other than I'm planning on
competing.



Re: Competition: Programing waste eater Nanobots
Padu wrote:
Quoted text here. Click to load it

Interesting contest, for those with good math and conceptual algorithm
skills.

Interesing concept for a competition by Symantec, as it mirrors the
functionality of a computer worm. The more we can understand the
algorithm behind an efficient virtual nano organism, the better we can
understand the algorithm behind an efficient net-based worm or virus.

-- Gordon

Re: Competition: Programing waste eater Nanobots
University students only.
Not open to residents of Quebec.

DAMMIT!


Padu wrote:
Quoted text here. Click to load it


Re: Competition: Programing waste eater Nanobots
"Don" wrote
Quoted text here. Click to load it


That's why I'm entering the competition. Since it's for university students
only and language is assembler (which will scary lots of nowadays students),
I think the number of participants will drop a lot.
Since it's no lottery, I don't know if it helps much (it only takes one
program better than yours), but it is a good incentive.

On another note, I wonder if it is possible to replicate this contest with
real robots (not nano), that would make a nice competition.

Cheers

Padu



Re: Competition: Programing waste eater Nanobots
I'm entering the contest too, and I'm curious to see how well I'm
doing... What's your avg on random number seeds 1 through 10?


Re: Competition: Programing waste eater Nanobots
Hey Steve

I'd like to hear what some of you out there tried. My first attempt
took about 3 minutes to write...~10 lines of code which just does a
random walk and desposits energy when it finds a collection station.
Completely unintelligent, but it surpasses the "sample" nanorg by a
factor of roughly 100, and it helped me ensure I understood some of the
basic commands.

I thought that was a good base to build off of, but I found as I
implemented obvious logic (such as "remember where collection stations
are and navigate to them when you're filled up on energy"), that the
score actually went down! This is due to what I see as a fatal flaw in
the simulation: traveling takes as much time as any other operation,
which means you can travel one square in the same amount of time you
can increment a register. Think about this, if you have coordinates for
two collection stations, by the time you calculate the cartesian
distance to each one and figure out which one is closer, you could
already be all the way across the board! So it really doesn't pay to be
smart, apparently.

Finally, last night, I started again from scratch and built a new
program from the ground up. After many hours of work (up until 6 am
today), I finally got all the logic implemented (although my
inter-organism communication wasn't where I wanted it to be), only to
find that it still doesn't surpass my first, three-minute attempt.

On seeds 1-10, I averaged 53.6m, max 93.6m, min 14.7m, std dev 20m. On
another random 10 seeds I averaged 48.8m.

My "smart" program, on the other hand, averaged 25.7m on 10 random
seeds.

Anyway, I'd like to compare notes/scores with others. What kind of
logic did you all implement? Here are a few of mine:

* Stack based navigation - All paths are stored as straight path
segments on a segment stack...Couldn't use the built-in stack because I
wanted to be able to make function calls in between path segment calls,
so I wrote a segment_push and segment_pop.
* Memorize collection stations - When you cross a CS, save its
coordinates. When you've accumulated more than a certain threshold of
energy (I picked 50k), then navigate to the CS by pushing the
appropriate path segments on to the path segments stack.
* Taste testing - since bad sludge can mutate your program, I wrote a
routine which cksums all 3600 words of memory, eats a piece, then takes
another checksum. There's a 32 word array where it stores sentinel
values indicating which types of food are safe to eat and which are
not.
* Edge-to-edge paths - in an effort to cover the board as efficiently
as possible, I made the default paths to criss cross the board from
left edge to right edge and vice-versa. This results in collecting food
much faster and more thoroughly than just randomly running around.
* Hungry behavior - when the nanorg is running low on energy (<10k), it
starts doing a random walk...this way pockets of the board where energy
density is high will get discovered by bots who've drifted away to
other parts of the board.
* Communication - this is not easy to do without interrupts...I
basically had two comm modules. For hostiles, my nanorgs just start
poking random memory values into random spots. For friendlies, the
nanorgs try to transfer the coordinates of a known CS.

Anyway, like I said above, all this logic was futile. It slows down the
robots and I was never able to come close to the efficiency that my
first, "dumb" nanorg had. I'd like to hear from anybody who had more
success. I didn't write any polymorphic code, which might be why I
struggled.

So how did you all fare/what strategies did you try?


Re: Competition: Programing waste eater Nanobots
Mark,
Thank you for sharing. I think it is very interesting to hear how other
people handled these situations. This program is grossly complex while
at the same time incredibly simple. The possibilities are endless. Let
me elaborate on my discoveries:

My initial design, like yours, walked, tested, ate, checked for
collections, checked energy levels, deposited if > certain amount. This
on its own does generally well but in short time, everything dies off.
There's a few things that make a significant difference in the lifetime
and outcome of your nano-organism:
1. Toxic Food (mutations)
2. Drones (mutations)
3. Energy depletion

Edit: A Summary of this lengthy detailed technical post can be found at
the bottom.

I saw mutations cause me the greatest problem throughout the lifetime
of my program. First some numbers: Testing against seeds 1-10, my best
result is 177.6 million on seed 10. My worst result is 44.8million on
seed 7. The average of 1-10 is 96million.

SCORES:
On 10 random seeds, my average is a bit higher. My best with 10 random
seeds is:
Your score: 660,218,493
Live organisms: 49, Live drones: 0, Final tick #: 1000000, Seed:
1141260297
and my worst of the 10 is:
Your score: 43,034,654
Live organisms: 9, Live drones: 0, Final tick #: 1000000, Seed:
1141260321

My best seed test ever on any seed was:
Your score: 949,076,249
Live organisms: 50, Live drones: 0, Final tick #: 1000000, Seed:
1141200156

I actually think the program I submitted as a final submission was
possibly worse then the one that actually obtained that above result.
Unfortunately that's the price of last-minute decisions.

Now, believe me when I say that results like this are incredibly
frustrating. I'll elaborate as to why these results differ so greatly
and some logic I implemented to achieve the top results and logic I
tried and discarded as useless.

First, you mentioned symantec made a mistake making movement and
register incrementing equal in value. I think a lot of this was done
for simplicities sake. My complaint was more that 1 million ticks is
not nearly enough time to display intelligent design. What is
intelligent in 10 million ticks may not get a great score under 1
million. So, many very excellent solutions have to be discarded in
order to simply earn enough quick points.

Let's go into detail:
The first impression of this project is that all robots are the same.
On the contrary, 50 duplicates of your code means you can have 50
unique robots. 'How!?' quite simply. You create a random generator
0-100 that if less than say, 10, jumps to one part of your code, if
greater, to another. You now can specify two completely different types
of robots and functionalities amongst them.

FUNCTIONALITY:
* Self-identification - All robots that are of the same type have
unique identifiers to distinguish themselves from robots of other types
and also and more importantly, from drones.
* Toxic waste detection. Storing toxic waste in a 32 word array, both
saving memory of safe and unsafe food. In regards to this, one thing to
consider is that if you are in a situation where there actually are 32
different types of food, 20% of those are toxic meaning ~6.4 foods will
mutate your program. That is a lot of chance of mutations which is the
VERY reason my results above differ so greatly. What I predict based on
my own analysis is that in the seed I did extremely well in the above
program, the types of food differed slightly whereas in the program
where I got 44million, my programs got terribly mutated.
* Collection point memory and pathfinding of collection points (I
discarded this technology near the last minute due to several reasons).
First, you have to constantly check your energy levels, compare them to
a certain fixed number and then decide if you want to go to a
collection point. That's not a big deal in itself, only slightly more
instructions then checking if you're on a collection point and then
checking if you should deposit based on that. However, its the
pathfinding of the collection itself that gets cumbersome.
1. If you start moving to a collection point, you have chances of
running into things (mostly other bots). You then need to take that
into account and restart your pathfinding for collection (a
possibility). This is involving quite a few jumps in the code and
happens often enough to be a serious problem. I do however think it has
a value if written well. So essentially every time you bump into
something, you recalculate the path.
2. On the plus side, you never have organisms running around with max
energy.
3. If something happens to be dead/immobile ONTOP of your collection
point, your organism will never get to its collection point and will
literally sit around doing nothing. You could program to then find
another collection point, but by this point, we're looking at quite a
few things to consider logically.

NAVIGATION: Control vs Chaos.
1. Randomized movements where they randomly recalc a direction and move
that direction every movement tend to not cover the board in full and
your organisms chances
of finding collection points are very narrow. They usually don't move
very far in a period of time although this type of movement is
excellent for getting organisms to bump into eachother frequently.
2. Sweeping the board. We know some popular sorting algorithms are
those like Quicksort using divide and conquer and also just whiping a
board one line at a time guarantees every line gets covered. This is a
nice idea in concept. If this type of implementation is done though, it
makes ABSOLUTELY necessary that your nano-organisms have collection
point pathfinding. Reason: If they dont have a collection point on
their "line" they are sweeping, they can never drop off energy.
However, those that do have a very short and easy path to get to their
collection point.
3. Bumping into stuff: If you have fixed movements that criss-cross in
any way, bumping into stuff is innevitable. This means recalculating
your movement because it might be a wall you bumped into or a drone.
This can be costly but it also gives you a chance to cover a lot of
areas.

DRONE ELIMINATION:
My robots start off as warrior bots. This has pros and cons. The cons
are to make them effective warriors, doing gathering logic (such as
figuring out if food is harmful, helpful, etc) can be time consuming
and make them innfective killers.

The pros are you can kill off drones. I effectively kill off all the
drones in the first 15-20000 ticks of any program I run. I think
figuring out how to do this took me a while and cost me some time in
implementing some other intelligent strategies. The way I do this is by
intelligently placing commands into the drones. They place jmp
instructions in locations 0,1,6,7. Since the jmp opcode happens to be 6
also, this creates an infinite loop in the drones and they eventually
fizzle out of energy and die. This also means the first part of my
program contains no actual intelligent logic. This is to prevent
possible re-writing of my own logic incase I mistakenly (even though I
do ID_checking) rewrite one of my own nano-orgs.

EVOLUTION/MORPHING:
I have a genetic algorithm that then evolves/morphs my bots into
gatherers.

By this time, drones are all over the place, just immobile, so sweeping
path by path becomes out of the question, I'd run into them everywhere.
Instead I move throughout the program randomly in a direction until a
hit something, then I alter my direction randomly. This affords lots of
collisions which means the directions get changed pretty quently,
however, edges of the board get swept more often then the middle (but
not by a terribly large margin).

Like I said, I discarded pathfinding of collection points. I'm not sure
if this was a great idea but it seemed to make things complicated for
the reasons I mentioned earlier (collisions, time to calculate
distances, odds of finding a collection point vs stumbling into one
randomly.

Evolution is an important aspect in this type of program. Evolving
based on criteria and morphing bots from one type to another in time of
need is useful and also pretty cool! The creative ways of doing this
are endless.

COMMUNICATION:
 I had a bot system that did this but it seemed to take a lot of time.
It seemed like a great solution for more than 1 million ticks, but slow
for 1million. Collection can let you do several things:
1. Help bots that are low on energy get recharged by other bots
2. Repair broken bots by letting repair-bots find them, repair their
instructions with good ones.
3. Share knowledge (bad food types, collection point locations, etc)

This is all done through pause/waite methods. Before every loop in a
program, check the "pause" memory location. If its flagged, you go into
a pause loop (which ends on a timer or by special command). Then the
two can communicate between eachother, exchanging information through
poke. You can also identify what type of bot it is and what it needs
using PEEK commands.

It sounds like Mark used the same concepts. Transfering known food
types is useful too. The problem I found is it takes a while to
communicate all of these types. Every time they stop, they'd need to
communicate 32 different types. One concept I had but never implemented
was to XOR multiple things together to reduce the number of transferred
commands. This however never got evolved into a working module.

 This all took a lot of time. In a 1million tick simulation, I couldn't
optimize this to be as useful as it was in 5million ticks. In a program
that ran over long periods of time. this is the perfect way to keep
your bots alive. You share information every time they run into
eachother and eventually and rather quickly, they know all the bad-food
types. Then they just eat until their hearts are content since they
know what is safe to eat.

EATING:
Eating causes mutations. LEARNING about bad food types by eating causes
mutations. I cannot stress this enough. There's also little way I could
figure out of telling where in the program these mutations occur unless
you had checksums all over the place. All of these checksums take
considerable amounts of time.

Some ideas: One thing you could do is have organisms who would
innevitably get mutated by eating bad-foods but took on the
responsibility of figuring out what was safe and unsafe. You could then
have other bots that collect this information from them and only eat
types they are told to be safe from this other bot-species. Using this
technique, only certain bots risk death while the other bots continue
to grow in knowledge about what is safe/unsafe from the "guinnea pig"
bots.

Another approach would be to have some bots dedicated to bot repair
while others just ate without care of mutations. If they got mutated,
fix them with the repair bots.

SUMMARY:
Every check takes time. Every comparison takes time. All of these
things are factors. Every communication between bots is a time that bot
could be moving around, learning, eating, collecting.

All of these factors made this a very challenging and imaginative
competition. I am certain many people stretched their minds to think of
ways of coping with various problems. I am also confident that some
implementations that do identical tasks can be optimized differently.

I liked how Mark used the stack based navigation. I'm wondering how you
deal with "obstacles".

Hopefully this post gives some insights into possibilities and an
alternative method.

Benjamin G.
University of Alaska Anchorage


Re: Competition: Programing waste eater Nanobots
I actually made a huge mistake in my program. I've taken the time to
rewrite certain checksum functions today and am pretty upset that I
didn't figure this out yesterday.
Here are sequential scores after fixing it (TOO LATE
UNFORTUNATELY!!!!):
Your score: 117,193,952
Live organisms: 18, Live drones: 0, Final tick #: 1000000, Seed:
1141269484
Your score: 196,066,951
Live organisms: 13, Live drones: 0, Final tick #: 1000000, Seed:
1141269489
Your score: 174,076,918
Live organisms: 22, Live drones: 0, Final tick #: 1000000, Seed:
1141269493
Your score: 221,478,558
Live organisms: 33, Live drones: 0, Final tick #: 1000000, Seed:
1141269498
Your score: 257,049,160
Live organisms: 25, Live drones: 0, Final tick #: 1000000, Seed:
1141269505
Your score: 136,108,329
Live organisms: 28, Live drones: 0, Final tick #: 1000000, Seed:
1141269510
Your score: 187,330,684
Live organisms: 11, Live drones: 0, Final tick #: 1000000, Seed:
1141269516
Your score: 201,499,127
Live organisms: 31, Live drones: 0, Final tick #: 1000000, Seed:
1141269520


Re: Competition: Programing waste eater Nanobots
After fixing yet another problem, i've taken my solution skyhigh. A day
late and 10,000 dollars short but it's been fun:
Your score: 573,082,755
Live organisms: 47, Live drones: 0, Final tick #: 1000000, Seed:
1141272524
Your score: 499,465,575
Live organisms: 44, Live drones: 1, Final tick #: 1000000, Seed:
1141272532
Your score: 544,252,912
Live organisms: 48, Live drones: 0, Final tick #: 1000000, Seed:
1141272595
Your score: 297,679,583
Live organisms: 31, Live drones: 0, Final tick #: 1000000, Seed:
1141272602
Your score: 798,031,186
Live organisms: 50, Live drones: 0, Final tick #: 1000000, Seed:
1141272608
Your score: 608,996,064
Live organisms: 49, Live drones: 0, Final tick #: 1000000, Seed:
1141272616
Your score: 321,857,000


Re: Competition: Programing waste eater Nanobots
Hi,

Very interesting, thank you! It's really too bad about your submission.
I think mine is more simplistic than yours - all the bots run the same
program, move around totally randomly and never "peek" at each other.

I simply have two copies of a loop that senses, eats if there is
unknown or non-poisonous food, determines if the food is poisonous,
releases down to 4500 energy if on a collection point and moves. It
continues in a straight line until it encounters an obstacle. When it
encounters an obstacle, it charges 200 in that direction and changes
its direction randomly. Surprisingly, even though this results in
charging the drones, I consistently found it earned more points then
peeking to make sure you only charge friends.

As I said, I have two copies of the loop, and the bots alternate
between the two copies every time they change direction. This lowers
the harm done by mutation. Interestingly, I found that having 2 copies
of the loop is better than having 1, but having more than 2 is
generally worse. The first copy of the loop is slightly different, in
that in addition to charging, it pokes a 0 into location 7 of the
obstacle. This proves to be highly effective, because my bots just have
some initialization code there that they never return to, and the
drones have a "call" instruction in location 6 that they apparently
loop back to frequently, so putting 0 into location 7 turns this into
an infinite loop and freezes them.

Instead of using memory locations to store the poisonous/non-poisonous
data for food, I used a register, that stores the "or" of 2^(foodtype
mod 16) for each food type that is poisonous (I mod the foodtype by 16,
which means if there are lots of food types the bot will be paranoid
and may not eat enough). It seemed like this often worked better than
using memory, presumably because there was no risk of corruption.

I also found that any attempt to move towards collection points, for
instance, did more harm than good. It's very difficult to have the bots
efficiently navigate, it seems, even though the scarcity of the
collection points make it seem like if someone could find an efficient
way to do this they would do very well. In general, I found simple
optimizations could make a big difference, with the number of times the
loops are called. For instance, checking for a collection point by
"release 1; jns loop" rather than a 3 instruction sense, cmp, je
actually increased my score a fair bit. Another surprisingly helpful
trick was padding the end of the code with hundreds of jmp
instructions, telling the bots to jump back to the main loops, in case
they bounced to weird portions of the code by mutation.

It looks like my results were more moderate than yours. My highs
weren't as high as yours, but my lows weren't as low.

On some of your seeds:
Note that, because I charge everybody, most of the drones stay "live,"
although in practice they are immobilized.

Your score: 833,655,602
Live organisms: 50, Live drones: 14, Final tick #: 1000000, Seed:
1141200156 (your high from above)

Your score: 513,503,203
Live organisms: 50, Live drones: 17, Final tick #: 1000000, Seed:
1141272595

Your score: 549,695,328
Live organisms: 49, Live drones: 17, Final tick #: 1000000, Seed:
1141272608

Your score: 540,391,768
Live organisms: 50, Live drones: 12, Final tick #: 1000000, Seed:
1141272616

Your score: 512,562,097
Live organisms: 50, Live drones: 15, Final tick #: 1000000, Seed:
1141272524

Steve


Re: Competition: Programing waste eater Nanobots
Great idea for your submission. As you can imagine, i'm bummed out but
that's just the tough break. I think your bot could do a lot better if
it implemented my drone killing algorithm and then evolved into your
bot following that. Your ability to keep your drones alive seems
extremely well done. The odds of drones mutating you in a severely
negative way aren't too bad either it seems. My submission definetely
won't be beating yours though :)


Re: Competition: Programing waste eater Nanobots
Here's some results of implementing your charging routine AND combining
it with bot identification.

Your score: 615,088,621
Live organisms: 39, Live drones: 1, Final tick #: 1000000, Seed:
1141322064
Your score: 501,657,293
Live organisms: 44, Live drones: 0, Final tick #: 1000000, Seed:
1141322072
Your score: 524,535,120
Live organisms: 41, Live drones: 0, Final tick #: 1000000, Seed:
1141322079
Your score: 582,612,492
Live organisms: 46, Live drones: 0, Final tick #: 1000000, Seed:
1141322086
Your score: 528,069,457
Live organisms: 42, Live drones: 0, Final tick #: 1000000, Seed:
1141322094
Your score: 378,086,185
Live organisms: 37, Live drones: 1, Final tick #: 1000000, Seed:
1141322101
Your score: 367,327,955
Live organisms: 35, Live drones: 0, Final tick #: 1000000, Seed:
1141322108
Your score: 414,220,991
Live organisms: 43, Live drones: 4, Final tick #: 1000000, Seed:
1141322115

Nothing great really.
Here are the results without doing an ID_CHECK before charging (way
better):
Your score: 540,184,654
Live organisms: 44, Live drones: 1, Final tick #: 1000000, Seed:
1141322273

Your score: 716,819,109
Live organisms: 50, Live drones: 1, Final tick #: 1000000, Seed:
1141322280

Your score: 630,731,876
Live organisms: 42, Live drones: 2, Final tick #: 1000000, Seed:
1141322288

Your score: 818,958,402
Live organisms: 50, Live drones: 1, Final tick #: 1000000, Seed:
1141322295

Your score: 508,047,870
Live organisms: 42, Live drones: 1, Final tick #: 1000000, Seed:
1141322302

Your score: 512,757,779
Live organisms: 45, Live drones: 1, Final tick #: 1000000, Seed:
1141322309

Your score: 534,307,765
Live organisms: 42, Live drones: 0, Final tick #: 1000000, Seed:
1141322317

Steve, i'm definetely impressed! Good luck with the competition, I
think you definetely sport a good chance of winning with submitted
numbers like those!


Re: Competition: Programing waste eater Nanobots
Oh... also padding the code with jmp instructions back to the
beginningis a brilliant idea :)
I padded my code with all the wrong things in that regards. Last minute
posting and over-tiredness :}

I tried padding my own though the results didn't improve dramatically.
Perhaps only because my code is 50 lines. :)


Re: Competition: Programing waste eater Nanobots
In regards to your use of 2^(foodtype)mod16 solution, while this does
reduce corruption, it does make your bot choose certain foods not to
eat that would actually be acceptable (reducing your overall score). I
believe if you were to instead use the last 32 words of memory, the
odds of you experiencing mutations that affected your checksum would be
extremely small. You would experience an incorrect checksum .008% of
the time, meaning that only 32/3600 random seeds executions would
result in a incorrect checksum. Considering the fact that the contest
does only 10 executions, the odds of you getting a faulty checksum on
just 1 of those 10 runs become 10*(32/3600) or 5%.

The tradeoff here is score vs guaranteeing less mutations (which could
make a big difference in a long-term scenario or if this was a
distributed application that was going to be run many thousands of
times accross different seeds for a long number of ticks.


Site Timeline