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
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.
On 10 random seeds, my average is a bit higher. My best with 10 random
Your score: 660,218,493
Live organisms: 49, Live drones: 0, Final tick #: 1000000, Seed:
and my worst of the 10 is:
Your score: 43,034,654
Live organisms: 9, Live drones: 0, Final tick #: 1000000, Seed:
My best seed test ever on any seed was:
Your score: 949,076,249
Live organisms: 50, Live drones: 0, Final tick #: 1000000, Seed:
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.
* 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
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
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
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.
I have a genetic algorithm that then evolves/morphs my bots into
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
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
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 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"
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.
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
University of Alaska Anchorage