Programming NANORGs in a Virtual World

Objective

In this project, you will design an assembly-language control program for the microprocessors of a colony of nano-organisms (NANORGs) in a virtual world.

Introduction

This Science Buddies project is adapted (with permission) from Symantec's 2006 University Programming Competition. It features a fun software engineering challenge: write an assembly language program to self-direct nano-robots to harvest energy in a virtual world.

Assembly language programming forces you to think at the level of the microprocessor. Your code works at the level of single words of memory, registers in the CPU, and fundamental processor instructions. Assembly language programming gives you insight into how computers actually work. This can help make you a better programmer in higher-level languages. This project requires previous experience in assembly language programming, or previous experience in higher-level programming languages (e.g., BASIC, C, C++) and a willingness to learn assembly language programming.

Your goal in this project is to program the NANORGs to extract energy from industrial sludge, found at random locations in the virtual world. The extracted energy must be delivered to special collection points, which the NANORGs must locate. Note that the NANORGs also require energy for their own operation.

Two additional problems complicate the task.

About one-fifth of the sludge is toxic to your NANORGs, and will cause random mutations of the processor code. The NANORGs can recognize the type of sludge before consuming it, but can only identify toxic types by experience.
The virtual world is also inhabited by a population of malicious drones, which use energy from the sludge, but never deliver it to collection points. These drones will reprogram your NANORGs to behave the same way if they get a chance! Your program will need to defend your NANORGs against these malicious attackers.

Here is the scenario in more detail.

Overview of the Project

The year is 2020 and all is not well. The world's accelerating consumption of oil during the 2000's and 2010's has largely depleted the world's reserves of oil, leading to mass shortages. Scientists and engineers all around the world are looking for environmentally safe and cheap alternatives to oil. The problem has become so large, and the opportunity so immense, that Symantec has decided to direct its Nano-technologies division to try to tackle the energy problem.

You have been hired by Symantec Nano-technologies Division to work on a new programmable nano-organism (NANORG) that is capable of converting industrial sludge into a renewable energy source. Symantec has already developed nano-organisms with the proper hardware to extract energy from the sludge, but needs you to write the control logic for the 16-bit NANORG CPU to make it as efficient as possible at harvesting energy. Of course, for your organism to function, it must use a portion of the energy it generates for its own operation, so it needs to balance its own energy needs with its goal of outputting as much energy as possible.

Once you have written the control program you can test how your NANORGs perform in a virtual world. In this simulation, fifty NANORG clones containing your logic will be dropped into a large tank of sludge and must consume the sludge and release energy into special collection points in the tank. Obviously, the NANORG that produces the most energy in the allotted time will be commercialized by Symantec, so it's your job in this project to produce the most efficient organism possible.

Unfortunately, in addition to converting sludge into electricity, your organism must also confront several other challenges. First, about 20% of the sludge is contaminated with radioactive chemicals; eating this sludge will cause your NANORG to undergo small mutations to its programming logic. Second, and more concerning, your organism must deal with an earlier generation of malicious NANORGs that are also present within the sludge tanks. These organisms, called "drones," were written by a spy to sabotage Symantec's Nano-technologies Division and are based on the same exact hardware and machine language instruction set as your NANORGs. However, their programming logic was intentionally designed to be harmful. While they also consume sludge, they produce no energy output. Moreover, if they come into direct contact with a foreign organism (such as yours), they may attempt to spread their logic by copying it into the adjacent organism (mutating your logic until you become one of them!). Your NANORG's logic must cope with both of these challenges.

The project includes a ZIP file for you to download, with all of the materials you will need for the project (see the Materials and Equipment section, below). The ZIP file includes a simple command-line program that you can run to measure the performance of your control program. It's the same program that was used for the contest, so you can compare your results to the contest winners. The ZIP file also contains a detailed instructions document (in PDF format, requires Adobe Acrobat). These instructions explain the assembly language commands that you can use to program your NANORGs. The instructions also explain the details of the virtual world which is simulated in the contest program. The Experimental Procedure section contains brief instructions on downloading the ZIP file and getting started.

Terms, Concepts and Questions to Start Background Research

To do this project, the following terms and concepts related to processors and programming should be familiar to you:

assembly language,
assembler,
machine code,
opcode,
operand,
register,
instruction pointer,
stack pointer.

Bibliography

For help learning assembly language, try one or more of the following references:
- Bartlett, J., 2004. Programming from the Ground Up. Downloadable from the "Files" section at: http://savannah.nongnu.org/projects/pgubook/,
  or you can order a print version online from Bartlett Publishing: http://www.cafepress.com/bartlettpublish.8640017,
- Carter, P., 2005. "PC Asssembly Language," DrPaulCarter.com [accessed July 10, 2006] http://www.drpaulcarter.com/pcasm/,
- Smit, F., 1996. "Assembly Tutorial," [accessed July 10, 2006] http://www.xs4all.nl/~smit/asm01001.htm.
If you get interested and start doing a lot of programming, you may want to try using a text editor that is a little more sophisticated than NOTEPAD. An editor designed for programming can help with formatting (with an auto-indenting feature), so that your code is more readable, yet still in plain text. This type of editor can also do "syntax highlighting" (e.g., automatic color-coding of .ASM or other programming language files) which can help you to find errors. Here is a free programmer's editor that you can try:
Kang, I., 2004. "Homepage of Crimson Editor," CrimsonEditor.com [accessed July 10, 2006] http://www.crimsoneditor.com/.
To see the original contest winners, and the seed values used for running the contest program, check out the following link:
Symantec, 2006. "Symantec's University Programming Competition," Symantec Corporation, 2006 [accessed July 10, 2006] http://www.symantec.com/specprog/university/.

Materials and Equipment

To do this experiment you will need the following materials and equipment:

computer with Internet access, a text editor, and an unzip program (e.g. InfoZip's free UnZip, available from http://www.info-zip.org/).
You will also need the CONTEST06 program and the documentation (SciBudProjectBioGenerator.pdf), which are both included in the following ZIP file. (The documentation is in pdf format, which requires Adobe Acrobat. You can download a free copy of Adobe Acrobat with this link http://www.adobe.com/products/acrobat/readstep2.html).
- To download the ZIP file, first create a folder on your computer for working with the program.
- Click on the link CompSci_p021_Files.zip and save the ZIP file to the folder you just created.
- Unzip the file CompSci_p021_Files.zip using your unzip program and extract the files. You're now ready to get started.
- The Experimental Procedure section has instructions to get you started.
- The ZIP file also contains the authoritative documentation file, SciBudProjectBioGenerator.pdf. This file includes information on debugging your program as well as a table of all NANORG processor assembly language instructions. We suggest printing this file for handy reference.

Experimental Procedure

This section provides more information about the "virtual world" that your NANORGs will have to navigate, as well as information about the details of running the CONTEST06 program. You can click on the links below to skip to the section of interest (the Back button on your browser will return you to this list):

Details of the NANORGs' "Virtual World"

You will write an assembly language program using Symantec's NANORG assembly language to control an individual NANORG. To write your program, you should use a standard text editor (e.g., Notepad). You can then use the accompanying CONTEST06 executable file to assemble and test your NANORG logic.

When you run CONTEST06, it will compile your NANORG source code into NANORG machine language and then create 50 NANORG clones, each with a copy of your logic. Each of these NANORGs functions as an individual entity, and each has its own copy of your program, its own memory, registers, etc. This colony of 50 NANORG clones, each running your program logic, will be placed in the virtual tank and must harvest energy.

Your colony of NANORGs will have a total of 1 million timer ticks to generate as much energy as possible from the sludge in their tank.

At the start of the program, your 50 clones will be randomly placed into a 70 wide by 40 high (i.e., two-dimensional) tank of sludge along with 20 clones of the malicious, previous generation of NANORG drones. Each NANORG (including drones) starts out with 10,000 units of energy. The tank's 70×40 locations are numbered from 0-69 and from 0-39, with the position 0,0 being in the north-west corner of the tank.

In a given tank, there will be hundreds of chunks of sludge. Every time a NANORG eats a chunk of sludge, it receives 2,000 units of energy. Each chunk of sludge is a member of a specific "sludge type" which is identified by a non-zero integer value (e.g. 5, or 17).

Your NANORGs can sense the type of each chunk before eating the chunk. Some types of sludge are entirely safe for a NANORG to eat and will simply provide it with energy, while other types of sludge are toxic (but still provide it with energy). For example, there might be 200 total chunks of sludge of 5 different types in the tank: 40 of type 1, 60 of type 2, 50 of type 3, 30 of type 4, and 20 of type 5. All 40 chunks of sludge type 1, 60 chunks of type 2, 50 chunks of type 3, and 30 chunks of type 4 might be safe to eat, while all 20 of type 5 might be toxic to your NANORG and cause mutations to its memory.

The number of different sludge types, and the quantity of each type of sludge, varies from tank to tank. In one tank there might be just 5 different types of sludge (with IDs 1-5), while in other tanks there may be up to 32 different types of sludge (with IDs 1-32). If there are N different types of sludge in a particular tank, then approximately 20% of the N different types of sludge will be toxic to your NANORGs. For example, if there are 10 different types of sludge (with IDs 1-10), then exactly 2 different types of sludge will be toxic (e.g. ID #7 and #9 will be toxic, while IDs 1-6, 8, and 10 are safe to eat). All food of a given type is guaranteed to either be toxic or safe to eat (it will never be the case that some food of type 5 is safe while other food of type 5 is toxic). Which specific types of sludge are toxic in a given tank is determined randomly and varies from tank to tank.

If your organism eats a chunk of sludge which is of the toxic type, it will cause one word (16 bits) of your organism's memory to mutate. Note that the malicious drones are completely immune to the mutagenic effects of the sludge and do not become mutated when eating toxic types of sludge.

You can determine the ID number of a given chunk by having your organism use the SENSE instruction while in the same square as a chunk of sludge. Your organism can learn which types of sludge are toxic and avoid them if you like.

Each time one of your NANORGs or one of the earlier, malicious generation of NANORGs eats a chunk of sludge, a new chunk of the same type of sludge (i.e., with the same type and therefore the same toxicity) will be dropped in a random location of the tank automatically, creating a perpetual source of energy. To gain points, each of your 50 NANORGs must eat sludge to gain energy and then release this energy at designated collection points using the RELEASE instruction. Your final score will be equal to the total of amount of energy released from the tank at the end of 1 million ticks. Each organism may not exceed 65535 energy units at a time, limiting how much each organism can eat before burning off the energy by executing instructions or using the RELEASE instruction to release energy or the CHARGE instruction to charge a neighboring NANORG.

To release energy and gain points, a NANORG must first travel to a collection point in the tank and then use the RELEASE instruction. 10 different collection points are randomly distributed within the tank. Your organism can sense when it is on top of a collection point by using the SENSE instruction, and these collection points are displayed on-screen with a "$" character. Be careful not to release too much energy at a time or your NANORG may run out of energy it needs to operate before it can find more food!

Each NANORG (including each drone) gets to execute a single machine language instruction per tick of the simulation. Each instruction consumes either 1 unit of energy (for computation) or 10 units of energy (to travel to an adjacent square in the tank).

Attempting to release energy when not on a collection point will drain your organism's energy without increasing your score, so be careful!

If a NANORG runs out of energy, it doesn't die but instead hibernates. An active NANORG can reawaken a hibernating NANORG by sharing energy with it using the CHARGE instruction.

You will be programming your NANORG using a simple assembly language, which will be compiled into NANORG machine language for execution (the drones were also written in this assembly language and use the same machine language as your NANORGS). The executable Symantec provided for the project has a simple assembler (as well as a disassembler) for this language. Your NANORG program can be up to 3600, 16-bit words long, and should never terminate; it should continuously hunt for food and produce energy until it is finally terminated at the end of the simulation.

In addition to traditional assembly language instructions, like MOV (to move data), and JMP (i.e., GOTO), the NANORG assembly language also includes other instructions to control the NANORG. Your organism can use the TRAVEL instruction to travel through the tank, the EAT instruction to eat sludge, the SENSE instruction to determine if your organism is standing on sludge or on top of a collection point (each type of sludge has a different ID number between 1 and 32, and collection points have an ID of 65535), and the RELEASE instruction to release energy into a collection point. Furthermore, organisms have special instructions to interact with adjacent organisms. The PEEK and POKE instructions can be used to read/write to/from the memory of an adjacent organism (including both your NANORGs and drones). The CHARGE instruction can be used by a NANORG to transfer a portion of its energy to an adjacent organism.

The NANORG virtual machine used by both your NANORGs and the drones has exactly 3600, 16-bit words of memory, numbered 0 through 3599. The NANORG assembly/machine language instructions are only capable of reading/writing a word at a time, and cannot read and write individual bytes. Attempts to access memory outside the 3600-word range will return a value of 0 but will not cause your NANORG program to terminate. Since your organism's data and logic are stored within the 3600 words of memory, your program may use self-modifying techniques (i.e., a NANORG can read/write/modify its own instructions). The CPU will happily execute data as if it were an instruction, so long as it is properly encoded. The NANORG machine only supports UNSIGNED arithmetic; the processor does not have any support for signed/negative numbers.

All instructions in the machine language are exactly 3 memory words long, and all instructions must be aligned on 3-word boundaries (i.e. the CPU will restrict the instruction pointer to multiples of 3). The first memory word of each instruction specifies the opcode and the addressing modes used for the operands. The second and third words specify the operands to the instruction. The designers of the NANORG hardware chose this encoding (as opposed to a variable-length instruction encoding) to reduce the impact of logic mutations. In order to simplify the process of writing self-modifying NANORGs, all jump and call instructions in NANORG programs that use immediate operands use relative-addressing for their target offset, enabling you to write relocatable code if desired (see Operand Details, bullet #5 in the SciBudProjectBioGenerator.pdf file).

The NANORG CPU has 14 registers, numbered R0–R13 that can be used in all instructions. All registers can be used interchangeably. Each NANORG also has a flags register (which can be referred to as FLAGS) and the instruction pointer (i.e., program counter)). Unlike typical processors, arithmetic instructions DO NOT set the CPU flags! See the SciBudProjectBioGenerator.pdf file for information on which instructions set flags.

The CPU has a stack pointer called SP whose value starts at 3600 at the start of execution. When pushing values onto the stack, the stack pointer is pre-decremented and then the value is stored at the specified location in the NANORG memory. When popping values off the stack, the top value on the stack is fetched first and then the stack pointer is post-incremented. If the stack pointer is invalid (i.e. too large) during a PUSH, POP, CALL, or RET instruction, it will reset to 3600 before the instruction runs. You can directly refer to the stack pointer in all instructions, by using SP instead of normal registers like R0 or R09.

If at any point a NANORG CPU encounters an invalid instruction, it will attempt to interpret and run the instruction if at all possible. Here are the possible cases:

An instruction with an invalid opcode will be skipped.
An instruction with an invalid operand will have the value of that operand treated as if it were 0. For example, "mov R5, [9999]" attempts to access slot # 9999 of memory, which does not exist, so R5 will be set to 0 instead. On the other hand, "mov R999, 52" will be treated as a NOP, since there is no such register.
The CPU will only execute instructions on 3-word boundaries since all instructions are 3 words long. If the instruction pointer is set to a non-multiple of 3, it will be reset to the nearest higher multiple of 3 before executing the next instruction.

Organism Source File Layout

An organism source file has two required components:

The first line of your organism source file must have an information line that is used to identify your organism and yourself. It's form is:
info: robotname, your full name
For example:
info: SampleBot, John Doe
Your organism source file must have one or more assembly language instructions on the lines following your information line. You can have standard instructions, like these:
mov r0, r5 // r0 = r5 // can be used for comments
add r0, 17 ; r0 = r0 + 17 ; semicolons comment too

You can have labels which specify locations in your program, like these:
startProgram: // a label call timeToEatFood // call to a label jmp startProgram // jump to a label timeToEatFood: // a label mov r0, 17 eat ret

You can define data regions anywhere in your program, like this:
topOfProgram: mov r0, 0x01 mov r1, [myData+r0] // r1 = memory[myData+r0] mov [myData], 5 // memory[myData] = 5 jmp overHere myData: data { 1 2 3 4 } // defines 4 words of data equal to {1,2,3,4} data { 0xdead } // defines 1 word of data equal to {0xdead} overHere: sub r0, 1 jmp topOfProgram otherData: data { 99 127 127 55 myData 42 42 42 overHere }
There is a sample source file from Symantec (samplebot.asm) included in the ZIP file. You can use this file as a starting point if you wish. It is also useful for testing the operation of the CONTEST06 program.

Assembling and Testing Your NANORGs

To assemble and run your organism source file and see how it works, use this command line (or its equivalent for Linux or OSX as detailed in the section below, Running the Contest Program on Apple or Linux Computers):

C:\CONTEST06> CONTEST06.EXE –p:yourPlayerFile.asm

Where yourPlayerFile.asm is whatever you name your NANORG's assembly file. This will assemble your source file and report any syntax errors it finds.

If your source is error-free, then the program will bring up a simple ASCII-based user interface where you can watch your organism run in simulation. You can hit ctrl-c at any time to terminate the simulation. Note the line at the bottom of the screen:

Score: 24800, Ticks: 1100 of 1000000 (Seed=11275142)

This indicates that your current score is 24,800 (that's how much energy all of the NANORGs have generated so far), and that 1,100 of 1 million ticks have elapsed. The seed number specifies the random number seed used to run this simulation. If you run the contest program with the same seed value S and the same NANORG assembly file, it will have the same result every time (simplifying the debugging process).

There are two different types of organisms shown on the screen: your NANORGs and the malicious drone NANORGs. Your organisms are represented by upper and lower-case letters. The drones are represented using @ signs. Food is represented by an asterisk (*). Collection points are represented by a dollar sign ($). The entrant's hibernating NANORGs (those with 0 energy) are represented as a period (.), and hibernating drone NANORGs are represented by a comma (,).

When the simulation completes all 1 million time-ticks (or all organisms, including drones, perish), then a summary of the simulation is printed out:

Entrant: SAMPLEBOT, JOHN DOE
Your score: 1352226
Live organisms: 35, Live drones: 0, Final tick #: 1000000, Seed: 2

If you want to compare your scores to the best and brightest in the U.S., the top three scores for the university-level contest entrants were (Symantec, 2006):

Matthew Menke, MIT, average score: 3.08 × 10⁹,
Bryant Brownell, Oregon State University, average score: 1.76 × 10⁹,
Louis Kruger, University of Wisconsin, Madison, average score: 1.72 × 10⁹.

Using the Contest Program

The contest program (provided for Windows, Red Hat Linux, and Apple OS X) can be used to test and debug your NANORG program. Here's how to get started:

Unzip all of the files into a new directory (i.e., folder) on your hard drive.
Open a command shell (e.g., CMD.EXE under Windows) and make sure that the command shell window is at least 80 columns wide by 50 rows high. (If you do not do this, the CONTEST06 program output will be difficult to understand.)
You can start by editing the sample NANORG that Symantec provided:
samplebot.asm
Using your favorite source editor, e.g. NOTEPAD or a programming editor (e.g., Crimson Editor, Kang, 2004). You can modify the programming logic of our sample NANORG to improve it. Alternatively, you can create your own NANORG from scratch.
Once you have updated/created your NANORG source file, you can test it by following the instructions below. If your NANORG programming logic contains any syntax errors or other errors that prevent it from compiling, the contest program will inform you of these errors, and you can fix them.
You can iteratively update your NANORG's programming logic and re-test it until you are happy with it.

Running the Contest Program on Apple or Linux Computers

The CompSci_p021_Files.zip file (downloadable from the Materials and Equipment section, above) contains Windows, Linux and Apple versions of the contest program. The contest program file for Red Hat Linux is called contest06-linux. The contest program file for Apple OSX is called contest06-apple. First, you should extract all of the files into a directory of your choice on your Apple or Linux computer. Next, open a command shell (e.g. csh) and switch to the directory that holds the contest files.

In order to run the contest executable on Linux and/or Apple OS X, you will need to change the permissions of the program file first. After extracting all of the files from the official contest .ZIP file into a directory on your hard drive, run the chmod command as shown below from within your command shell, in the same directory as the contest files:

For Apple, type the following on the command line:
chmod +rwx contest06-apple
and then hit enter.

For Linux, type the following on the command line:
chmod +rwx contest06-linux
and then hit enter.

You will now have a runnable executable file for either Apple OS X or Red Hat Linux. To run the executable in the Apple OS X command shell, switch to the directory where you unzipped the contest files and type:
./contest06-apple
and then hit enter.

To run the executable in the Linux command shell, switch to the directory where you unzipped the contest files and type:
./contest06-linux
and then hit enter.

The remaining sections below describe how to use the Windows version of the contest program, contest06.exe. If you are running the contest program on a Linux machine, then simply substitute "./contest06-linux" for the "contest06.exe" in the documentation below. If you are running the contest program on an Apple machine, then simply substitute "./contest06-apple" for the "contest06.exe" in the documentation below. (Note the dot followed by a slash, preceding the filename.)

Using the Seed Command

Occasionally when debugging, you will notice one of your NANORGs behaving erratically. You may wish to run the simulation again in single-step debugging mode and determine what went wrong. To do so, you'll want to run the simulation again using the same seed as was used during the last run; this ensures that the exact same set of circumstances will be reproduced. To do so, write down the seed value during your first run. During the second run, you can then invoke the contest program as follows:
C:\CONTEST06> CONTEST06.EXE –p:myorg.asm –g:C –s:####
Where you specify the letter of the misbehaving clone that you wish to debug after "–g:" and you specify the proper seed value after "–s", for example: "-s:112314895".

This will ensure that (assuming you make no changes to your organism's source code in between debugging sessions) that you will exactly recreate the previous simulation, only in debug mode.

If you want to compare the results of your NANORG program to those of the contest winners, you can use the seed command to set the actual seed values used in the contest (see Symantec, 2006).

Running the Contest Program in Quiet Mode

To speed things up drastically (after all, our UI is quite slow), you may wish to run simulation in quiet mode. This will ensure that the simulation runs without any output; the result of the simulation will simply be displayed on-screen upon completion. Note: you cannot use the single-step debugger (option –g) while the game is in quiet mode:
C:\CONTEST06> CONTEST06.EXE –p:myorg.asm –q

Variations

Scientists and engineers often make progress by building on the results of their predecessors. Study the programs written by the contest winners (Symantec, 2006). What can you learn from them to improve your own program? There are many approaches you could try.
- One approach would be to write your own assembly language code to include a desired feature from one of the winning programs (be sure to give credit for the idea with a citation).
- Another (more difficult) approach would be to use one of the winning programs as a starting point, and try to find one or more ways to make a significant improvement. You'll need a thorough understanding of how the program works in order to do this, and there is no guarantee of success. You will also need to be scrupulous about citing the source for your starting point, and clearly explaining the improvement(s) that you originated. Can you increase the average score by 10%, 20% or more? Remember that it is completely unethical to copy someone else's work and call it your own.
Here are a couple of advanced strategies that you might try when writing your program:
- Can you improve your score by increasing the amount of cooperation between your NANORGs?
- Can you improve your score by writing your program so that sub-groups of your NANORGs are specialists for certain tasks? For example, how about a group that specializes in shuttling energy to the collection points? Or a few defense specialists to neutralize (or recruit) the malicious drones?