Competition: Programing waste eater Nanobots

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

University students only. Not open to residents of Quebec.

DAMMIT!

Padu wrote:

"Don" wrote

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

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?

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 (

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

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

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

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

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 :)

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!

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. :)

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.