NANORG

[yijunhu1998]

I've been working on the NANORG project, and my main program has reached a score of almost 900,000,000, but the winning programs got scores of over 3,000,000,000, and a search over the internet shows that most people who posted their scores got higher than mine. Could someone give me some tips on how I could improve my program? It basically splits into two parts, one that reprograms enemy drones, and one that eats and releases. The first transitions to the second after a while, and only the second will protect itself from toxic food. Is there a way to improve on that? Please help!

[hhemken]

yijunhu1998,

There's more than one way to skin a cat, and figuring out how to create high-scoring NANORGS can be a sophisticated undertaking, depending on how far you want to carry it.

I would suggest you look into some kind of evolutionary strategy. Figure out a way to write a separate program in some normal scripting language like python, perl, ruby, PHP, Java, etc. that writes your NANORGS' code. Design the basic NANORGS to have several (or even many) distinct parts that get called in the course of their behavior, or add numeric parameters that regulate different aspects of their behavior. Those parameters should give them a high degree of tunability, i.e., it should be possible to generate thousands and thousands of slightly different NANORGS by varying the numbers in their code.

Your program would be designed to generate those thousands of variants and test them. You would keep track of the good ones and use them as a basis to tweak them and generate a new generation for testing. The best ones from that generation become the basis for the next one, and so on like that. The trick would be designing highly tunable NANORGS to begin with. The more they lend themselves to generating very large numbers of NANORGS with slightly different or even significantly different behavior, the more likely you will be able to find outliers with very high scores.

Play around with the idea and let us know how it goes.


Good luck!

Heinz

[yijunhu1998]

Well, I tried part of that, since it was very complicated, and I'm not a good programmer, but after a while, I found that this idea is very good in theory, but the contest06.exe takes care of this-- if I change the sum, or even one command, the two programs are uncomparable-- any given NANORG will not run the same way. For example, I tested this by making a simple program that, in the middle, changes r0 to a random number between 0 and 99, and then I created a variant of that which had a different command on line 12, (release 5000 instead of release 4992) and the number r0 was changed to was different, even though I tested them on the same seed. Unfortunately, I'd have to test the programs on 10 seeds each, and I cannot really do that too well... Is there another way to change the NANORG's for the better?

[hhemken]

yijunhu1998,

Let me have a closer look. I'll get back to you in a couple of days.

[hhemken]

yijunhu1998,

I think I can now recommend a strategy. Forget what I said earlier. Here is a (pretty lame) nanorg I managed to cobble up:

Code: Select all

info: hhbot-01, Heinz Hemken
 
main:
    // select a random direction and distance to move
        rand    [dir], 4

//------------------------------------------------------------------------------
// main loop
loop:
        // check if I�m top of food and eat if so
        sense   r2
        cmp     r2, 32
        jg      noFood
        eat

noFood:

        // see if we're over a collection point and
        // release some energy
        energy  r0
        call    bigRelease
        call    medRelease
        call    smallRelease
       
        // move me
        call    newDir
        travel  [dir]

        jmp     loop
//------------------------------------------------------------------------------
// subroutine-like code

newDir:
        rand    [dir], 4
        ret
       
hugeRelease:
        cmp     r0, 30000
        sense   r5
        cmp     r5, 0xFFFF      // are we on a collection point?
        jne     hugeReleaseDone
        release 28000
        ret
hugeReleaseDone:
        ret
       
bigRelease:
        cmp     r0, 10000
        sense   r5
        cmp     r5, 0xFFFF      // are we on a collection point?
        jne     bigReleaseDone
        release 8000
        ret
bigReleaseDone:
        ret
       
medRelease:
        cmp     r0, 5000
        sense   r5
        cmp     r5, 0xFFFF      // are we on a collection point?
        jne     medReleaseDone
        release 4000
        ret
medReleaseDone:
        ret
       
smallRelease:
        cmp     r0, 2500
        sense   r5
        cmp     r5, 0xFFFF      // are we on a collection point?
        jne     smallReleaseDone
        release 500
        ret
smallReleaseDone:
        ret
       
dir:               
        data { 0 }       // our initial direction


Note that I have a relatively tight main loop, and below that some subroutine-like sections of code that get called from the main loop. I do this so that 1) the main loop is easy to read and understand, and 2) I can compartmentalized the code into discrete chunks of activity, each relatively independent of the other.

I also found a few discussions:

Code: Select all

http://www.sciencebuddies.org/science-fair-projects/phpBB3/viewtopic.php?f=30&t=3736
http://www.dynamicdrive.com/forums/showthread.php?t=57963
http://hardforum.com/archive/index.php/t-1023254.html

What I would recommend id to devise a variety of subroutines that each perform a clever sub-strategy, such as "go in a straight line for a while", "check if this sludge is bad or not", "remember whether this sludge is bad or not", "go in a circle looking for food for a while", and things like that. Write them in such a way that you can just call them from the main loop, comment them out or uncomment them, and easily try different combinations of the sub-strategies while still having a tight main loop that is easy to read and understand. I think this is the way to figure out what specific behaviors will make you get higher scores. Also, once you have a bunch of such subroutines, you can write a lot of different nanorgs with different combinations of subroutines in different order and maybe even with different parameters. This might help shed more light on what makes a nanorg truly good.

Please let me know if this makes sense.

Heinz

[yijunhu1998]

Oh. I'm sorry! I accidentally put 9 million! I meant [almost] 900 million. I tried your program, and although the score's pretty low, I still don't understand the coding, unfortunately... Could you explain how you used RET and CALL? My programs are OK, but I have no idea what some of the commands mean, like XOR, RET, SHL, SHR, TEST, AND, OR, RET, CALL, MOD, PUSH, POP, etc. I tried to make a program with these that should have worked, theoretically, but didn't, so could you explain these? Also, here's a copy of my program:

Code: Select all

info: PWNAGE, Joshua Hu

jmp Start

simple_drone_loop:
travel r4
jns simple_drone_switch
sense r1
cmp r1, 0
je simple_drone_loop
cmp r1, 0xFFFF
je simple_drone_drop
eat
jmp simple_drone_loop
simple_drone_drop:
energy r3
sub r3, 5000
release r3
jmp simple_drone_loop
simple_drone_switch:
charge r4, 1000
rand r4, 4
jmp simple_drone_loop

pokedefense:
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }

Start:
rand r4, 4
rand r1, 2
cmp r1, 0
je attacker_loop

drone_loop:
travel r4
jns drone_switch
sense r1
cmp r1, 0
je drone_loop
cmp r1, 0xFFFF
jl drone_test
drone_drop:
energy r3
sub r3, 5000
release r3
jmp drone_loop
drone_test:
cmp [badfood+r1], 0xFFFE
jg drone_eat
je drone_loop
mov r13, 0
cksum r13, 3599
eat
jns drone_loop
mov r12, 0
cksum r12, 3599
cmp r12, r13
jne drone_mark
mov [badfood+r1], 0xFFFF
jmp drone_loop
drone_eat:
eat
jmp drone_loop
drone_mark:
mov [badfood+r1], 0xFFFE
jmp drone_loop
drone_switch:
charge r4, 1000
rand r4, 4
jmp drone_loop

badfood:
data { 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }

attacker_loop:
travel r4
jns attacker_command
eat
travel r4
jns attacker_command
eat
travel r4
jns attacker_command
eat
travel r4
jns attacker_command
eat
travel r4
jns attacker_command
eat
jmp attacker_switch
attacker_command:
mov r2, r4
mov r0, 0
poke r2, 84
peek r2, 87
cmp r2, 32782
jne attacker_switch
attacker_attack:
mov r9,   simple_drone_loop
mov r0,   [simple_drone_loop]
attacker_attack_loop:
poke r2, r9
jns attacker_switch
add r9,   1
mov r0,   [r9]
cmp r9,   pokedefense
jne attacker_attack_loop
attacker_end:
jmp drone_loop
attacker_switch:
charge r4, 1000
rand r4, 4
jmp attacker_loop

count:
data { 0 }

myID:
data { 500 }



[hhemken]

yijunhu1998,

I ran your program and it is vastly better than my own humble attempt. Have a look at any tutorial on intel x86 assembly language for more info on the commands (although there will be differences). I'm not sure you need more than what you are already doing. The CALL keyword is like a jump to a labeled location, and RET makes the program flow return to the point right after the CALL. It is like calling a function or subroutine in another programming language and then returning to the point right after the call. It makes it easy to create function calls that you can move around, omit, duplicate, etc. inside your program. They may or may not be of use to you, but they would help compartmentalize specific behaviours that you could then mix and match for experimentation.

I think you know much more about NANORGS than I do, so I don't know how much help I can really provide. It's a good idea for you to revive the "Comparing Virtual Nanobot Tactics" thread. That way you'll get feedback from people who have skills and interest in NANORGS. That sort of forum tends to be the best way to get high quality info. Also, if you post your scripts and ideas you'll help others and induce people to post their own code, thus helping everyone.

Good luck, and keep us posted.