Steve Bailey : CORE WARS

Steve's Guide for Beginners Iss 1-9 (v4)

I am a beginner and I find all this Core Wars stuff VERY confusing, so I am writing this "guide" for my own use, to encourage CONSTRUCTIVE criticism and advice and as a possible aid to other beginners. Such a guide may already exist - in which case please point me at it. During these guides I will make statements that are incorrect in detail, but please don't correct them when the intent of the statement is for beginner simplicity. The bias is towards IBM PC compatibles. (I use a 486/66 running DOS 6 and Windows 3.1.) The line length is intentionally narrow to ease quoting. Introduction: Some people will have a vague recollection of the concept of Core Wars from the Scientific American article around 1984. Most people have never heard of it. What is Core Wars? It is a game for 2 players. The field/board is a simulated small computer. The player's "piece" is a program. The objective is to corrupt your opponent's program so that it executes an illegal instruction. The field of play (the computer) is known as MARS which stands for "Memory Array Redcode Simulator". One common simulator is pMARS (p for portable). The programs written are "Warriors" and have names. How to start? I started in Most of the r.g.c. posts are technical gobbledegook, ignore them. Find the FAQ or references to the archives: >From there load down .../documents/tutorial.1.Z, .../documents/tutorial.2.Z and .../systems/ (which is PC executables) (don't download the sources Create yourself a corewar directory (I'll refer to this as \COREWAR). Unpack the tutorials, merge them into one file (I called mine TUTORIAL.TXT) and put it in \COREWAR and read it. Unpack the zip file into \COREWAR then run your virus checker. (I renamed many files to ease my personal use - eg PMARS.DOC is now DOCN.TXT). (If you can't unpack .Z or .zip files, that is a separate matter beyond the scope of this guide.) >From DOS, change to \COREWAR, type DIR. You will see 3 *.EXEs and some *.REDs. Just to prove you've done it right, type PMARSV to get the usage prompt. Next choose two *.REDs (I'll pick two as examples here) and type: PMARSV RAVE.RED AEKA.RED Watch it compile and splash pretty patterns on the screen. You are up and running. Next issue will discuss what the patterns mean and what the *.REDs are. I made myself a one-line batch file PM.BAT to ease my DOS typing: PMARSV %3 %4 %5 %6 %7 %8 %9 %1.RED %2.RED Thus "PM RAVE AEKA" is the same as "PMARSV RAVE.RED AEKA.RED" Warriors: The *.RED files are warriors - that is simple programs. You need to study the tutorials and other documents on and at the archives to fully understand them. If you have no knowledge of programming and/or no knowledge of assembly languages then Core Wars may be too much for you. Meanwhile lets make a very simple warrior. Edit a text file BORING.RED to contain: ;redcode-94 ;name Boring ;author Your Name mov 0,1 end pMARS instructions are all 1 instruction per memory location, all locations are addressed with an offset relative to the current Location. So "MOV 0,1" copies the contents of location 0 (the current location, whose content is "MOV 0,1") to location 1 (the next location). It then executes the next location refering to that as location 0, thus the program rolls round pMARS's circular memory writing the next intruction to execute into the next location - all 'just in time'. Type PM BORING BORING Watch some compilation text appear then watch blue zeros (representing memory locations accessed by the zeroth warrior) and green ones (representing memory locations accessed by the 'first' warrior) scroll around the screen for several seconds. Wait for the "Press Any Key" prompt, then press a key. Observe the results at the end "0 0 1". What you have done is asked program (Warrior) BORING to fight warrior BORING. At the end of the fight, both were still alive, so the results were 0 wins, 0 losses, 1 tie (draw). Now make an absolutely useless warrior as file USELESS.RED: ;redcode-94 ;name Useless ;author Your Name start jmp start end This so-called warrior just jumps to itself, never attacks anything and shouldn't last long. Now type (the case of the -s option matters): PM USELESS USELESS -s 1000 and observe a blue 0 in the top left of the screen and a green 1 somewhere else in the top half of the screen. It will be the top half 'cos there are 1000 character positions in the top half of a 25 line 80 character display and the " -s 1000" makes the pMARS memory size 1000 locations. Patiently wait for the "Press Any Key" prompt. The result of that fight is obviously a tie. Now try PM USELESS BORING -s 1000 The Blue 0 in the top left shouldn't last long. The green 1s march all over the top of the screen. I believed this ought to be a convincing win for BORING. However it isn't - the results show a tie with both warriors surviving. The explanation is in issue 3. Sequencing: The programs are run "multi-tasked", swapping programs after each instruction. To "see" what is going on, lets "run" the two programs in a 10 location memory. I'll use "." for an empty location, "j" for one with USELESS's "JMP start" instruction and "m" for one with BORING's "MOV 0 1" instruction. The "j" is at location "0" and the "m" starts at, say, location 6. I'll capitalise the instruction being executed and start each line with "U" or "B" depending upon whose turn it is. (Data is shown before execution of the instruction.) U J.....m... B j.....M... U B j.....mM.. U J.....mmm. B j.....mmM. U J.....mmmm B j.....mmmM U M.....mmmm B Mm....mmmm U mM....mmmm B mMm...mmmm In other words, USELESS has started running BORING's code and is travelling around memory with the same Program Count as BORING (although it executes first.) This explains why USELESS doesn't die. ====== OK, lets copy BORING.RED to BORING2.RED and edit it to read: ;redcode-94 ;name Boring2 ;author Your Name mov 0,2 mov 0,2 end When we analyse this fight: U B j.....Mm.. U J.....mmm. B j.....mMm. U J.....mmmm B j.....mmMm U M.....mmmm B m.m...mmmM U mMm...mmmm B Mmmm..mmmm U mmMm..mmmm B mMmmm.mmmm we see the same phenomena - USELESS is executing BORING2's code. So when we run PM USELESS BORING2 -s 1000 we expect and get a tie. We can see the blue and green warriors, and it is obvious why there are lots of green 1s. It is also understandable why there is a single blue 0, but what about the "." characters? Display meaning: All characters are coloured to define which warrior did the action. Number (0 or 1) means that program executed the instruction in that location. Flashing number; as Number but illegal instruction so a warrior died. (Or at least part of a warrior.) "." Location was written to. Small "." Location was read from. "-" Location decremented as an address access. Note an 8000 memory corewar fight puts 4 locations per character position on the 2000 character PC screen and so the last access type to any of the four locations is what is displayed. Ok, so now we get "sophisticated" (refer to a dictionary - 'perverse') and do BORING3.RED which is a two instruction move pair, but the first instruction moves the second one and the second instruction moves the first one. This will have the effect of zapping the "JMP 0" instruction before the following instruction is in place. (Well that will be the case ~50% of the time.) ;redcode-94 ;name Boring3 ;author Your Name mov 1,3 ;Copy "MOV -1,1" mov -1,1 ;Copy "MOV 1,3" end I'll use "M" for the "MOV 1,3" and "N" for the "MOV -1,1" instruction and do it twice, once with BORING3 starting at locn 6 and at locn 7. I'll use "." and "e" for empty locations, the "e" being a significant empty cell. locn 6: U B j.....Mn.. U B j.....mN.n U J.....mnmn B j.....mnMn U Jn....mnmn B jn....mnmN U Mn....mnmn B Mn.n..mnmn U mN.n..mnmn B mNmn..mnmn Here USELESS safely runs BORING3's code. locn 7: U J......mne B j......Mne U N......mne B ne.....mNe U nE.....mnm and at this point USELESS crashes. Try running PM USELESS BORING3 -s 1000 several times and compare the results. Also try PM BORING3 USELESS -s 1000. Now all that stuff with "." and "j" and "mnMn" is all very well, but PMARSV includes a debugger to assist in this task. My aim here is to get to grips with some of the debug tools - I'm nowhere near ready to contemplate designing Warriors yet. So lets investigate CDB. Type: PM USELESS BORING3 -l 5 -s 20 -e -F 10 (lower case -l, -s and -e) (upper case -F) The "-l 5" limits each warriors source code length to 5 instructions. The "-s 20" specifies a memory size of 20 (which will easily fit on one screen). The "-e" enters the debugger. The "-F 10" Forces BORING3 to start at Adr 10. (Ignore the compilation stuff scrolling up the screen.) You get presented with the instruction about to execute, in this case a blue (USELESS's) "JMP 0". Type "HELP" with several returns to see built-in prompts. At a (cdb) prompt type "L0,$" to list all of memory from Address 0 to the last address (19). I see USELESS at adr 0 and BORING3 at adr 10..11. Adr 0 is blue, for USELESS's current instruction. Adr 10 is green for BORING3's current instruction (MOV 1,3). "s" (for step) executes Adr 0 and displays Adr 10. "s" executes Adr 10 and displays Adr 0 again. "l0,$" displays all memory again and I note that Adr 11 is now green, and that Adr 13 contains a copy of Adr 10. Do a dozen "s" commands (You don't have to type the s each time as ENTER repeats the last command.) Then l0,$ again, you can see how BORING3 has 'grown' (? probably the wrong term). Type "r" to see a summary of the registers. Note that we have done about 7 cycles (IE each warrior has had 7 instruction operations) with only 79993 left to go. 1 copy of USELESS exists and is about to run at Adr 0. 1 copy of BORING3 exists and is about to run at Adr 17. (The P-space stuff is definitely ignorable for the present!) Another eight "s" and we see USELESS executing BORING3's code. BORING3 seems to have disappeared as it has the same Program counter value as USELESS. Type "q" (quit). Now lets repeat all this with PM USELESS BORING3 -l 5 -s 20 -e -F 11 Do 13 "s" and then "l0,$". One "s" and "l0,$". Note that USELESS is about to execute MOV -1,1. One "s~l0,$" (A meld of two cdb instructions). USELESS's PC is at Adr 1 which has no content. Two "s". The second "s" ends the round with USELESS dead at Adr 1. ====== That's the basics of the debugger. It can also search, edit, jump etc etc. For any beginner reading these guides, note that they are basically a log of what I am doing to learn core wars. You too can do the same experiments, but you MUST ALSO read the other documentation (FAQ, Tutorial, Language specification etc). Assuming you have a decent SVGA screen, type (from DOS, NOT from a DOS box in windows) PM RAVE AEKA -v 525 What you will see is a box of 8000 cells containing red and green dots dancing at the top of the screen. This is a high res version of the text display we looked at earlier. The lower half of the screen is a debug window - press "d" to get the cdb prompt and you can type things like "l PC1,PC1+10" For details and other screen types read the PMARS documentation Appendix. ====== Now its time to start getting to grips with some basic Warriors. The tutorials and the newsgroup are full of self-referencing jargon. I suppose that that is in keeping with the programming style of Core War but it is very confusing. Dewdney seems to have a thing for fantasy creature warrior names - IMP, DWARF etc. Lets look at some. ====== IMP (adapted from the tutorial file): ;redcode-94 ;name Imp ;author A.K.Dewdney imp mov imp, imp+1 end This is none other than our friend BORING, written using address labels - The current instruction is at address 'imp'. When executed, copy the contents of address imp (at a displacement of 0 from the current instruction at address 0) to the location after imp. This is a very simple program and I don't see how it can kill anything. ====== DWARF (adapted from the faq file): ;redcode-94 ;name Dwarf ;author A.K.Dewdney bomb dat #0 dwarf add #4, bomb mov bomb, @bomb jmp dwarf end dwarf Now this has lots of new stuff. The "end dwarf" terminates the program source code and causes the instruction at adr 'dwarf' to be the first executed. The instuction at adr 'dwarf' adds the number 4 to the contents of the instruction at adr 'bomb'. Thus after execuction of the ADD, bomb will contain 'DAT #4' (and next time round the loop it will contain 'DAT #8' etc) (Note: All instructions have two operands "A" and "B" and that 'DAT x' is shorthand for 'DAT #0, x'. I think the default ADD operation is to add to the B operand of the desination location.) Then we step to 'MOV bomb, @bomb'. (Now here things get 'clever'. The assembler knows operand sizes and the like. I believe it to be possible to add instruction modifiers to alter default behaviour, but ...) This copies the entire instruction at location 'bomb' to the adr specified by the B operand of the instruction at adr 'bomb' WITH RESPECT TO the location it was accessed from (bomb). That is it copies "DAT #4" to adr 'bomb+4'. Why is this a bomb? Well it is illegal to execute the DAT (data) instruction. Copying it to somewhere where your opponent will run it will cause him to crash. Next we step onto 'JMP dwarf' which causes us to loop and do our ADD instruction again. ====== Dwarf comments: I assume that this is the archetypal bomber. The loop length is 3 instructions, the program length is 4 instructions. The bombs are placed every fourth location. This means that we could happily sit in our 4 locations throwing out bombs as long as the bombs miss our code and for "our" 1 bomb in 4 locations it is the DAT adr which is hit. This won't work if CORESIZE isn't a multiple of 4. Run the debugger to check what addresses get bombed and how DAT increments: PMARSV -l 5 -e -s 20 DWARF.RED (there is only one warrior, so we can't use the batch file!) (Use debug command meld: @s~l0,$ to step one instruction without displaying it and then to display all of memory.) Redo it with "-s 19" and kill yourself! Instruction set and Addressing modes: These are covered formally in the redcode 94 draft specification, (Is it still draft? Am I looking at the right file?) and informally in the tutorial. Most fights discussed in seem to use "Draft-94 extended" which is covered in REDCODE.REF . Points to note. All instructions have 2 operands, although sometimes only one is used. All numbers are positive integers in range 0..CORESIZE-1. The format is: Label Opcode AOperand, BOperand (An Opcode is a basic "opcode" with a "modifier".) (An operand is an address "mode" with a "number".) Opcodes are typical of traditional assemblers: MOV, ADD, SUB, MUL (need to check what happens with overflows and "negative" numbers), DIV produces the quotient (ditto), MOD produces the remainder (ditto). CMP (Skip if equal), SLT (Skip if less than). JMP, JMZ (Jump if zero), JMN (Jump if non zero). All jump to AOperand and test BOperand. DJN (Decrement BOperand and then if it is non-zero jump to AOperand), DAT is for storing data (possibly two numbers in the two operand files. EXECUTING A DAT crashes a process, thus killing part of a warrior. SPL splits the warrior, producing an extra process. It acts if a "photocopy" of the instruction is made with the original executing a NoOperation instruction "JMP 1" then the new process executes "JMP Source" Once you split your warrior into N processes, each process runs at 1/Nth of the usual speed. SEQ (CMP), SNE (Skip if not equal), NOP (JMP 1), LDP and STP are extensions. The mixture of modifiers for the opcode (.A, .B, .AB, .BA, .F, .X, .I) with modifiers for the Operands ( #, $, @, <, > and extensions *, {, } ) produce a complicated set of possible instructions. ====== Lets look at DWARF again. First what we (nearly) typed: bomb dat #12 ;was #0 dwarf add #4, bomb mov bomb, @bomb jmp dwarf Next the assembly listing. (Comments are not assembler output!): dat.f #0, #12 add.ab #4, $-1 ;really $CORESIZE-1 mov.i $-2, @-2 jmp.b $-2, $0 Which means: DAT The .f means both operands, a meaningless option for the DAT non-instruction. # means immediate data (IE the address is the address of this location). Note that the data is in the B operand. ADD .ab Take the A number from ( # ) current location and add it to the B number of ( $ -1 ) the previous location. Store result in B number of the previous location. $ means the address is the number in the instruction being executed. MOV .i The entire instuction, opcode and both operands. @ The address is the B number found in the location specified by this operand. JMP .b Doesn't make sense in this context, the destination address is in the A operand. ====== Lets try a set of instructions, before execution on the left, and after execution on the right, to demonstrate some of these points: st add.a #1, #10 #2, #10 add.ab #1, #10 #1, #11 #1, #10 #11, #10 add.b #1, #10 #1, #20 add.f #1, #10 #2, #20 add.x #1, #10 #11, #11 add.i #1, #10 #2, #20 add.a $a1, $a2 jmp $ab a1 dat #1, #10 #1, #10 a2 dat #4, #40 #5, #40 ab add.ab $ab1, $ab2 jmp $ba ab1 dat #1, #10 #1, #10 ab2 dat #4, #40 #4, #41 ba $ba1, $ba2 jmp $b ba1 dat #1, #10 #1, #10 ba2 dat #4, #40 #14, #40 b add.b $b1, $b2 jmp $f b1 dat #1, #10 #1, #10 b2 dat #4, #40 #4, #50 f add.f $f1, $f2 jmp $x f1 dat #1, #10 #1, #10 f2 dat #4, #40 #5, #50 x add.x $x1, $x2 jmp $i x1 dat #1, #10 #1, #10 x2 dat #4, #40 #14, #41 i add.i $i1, $i2 jmp $0 i1 dat #1, #10 #1, #10 i2 dat #4, #40 #5, #50 end st Lets look at ways of copying code around. Traditional assembler: Make a text file COPY.RED: ;redcode-94 ;name Copy ;author sgb ;Block copy code: traditional assy style OFFSET equ 20 ;Variables (data is arbitrary) src dat #1 dest dat #1 count dat #1 ;Initialise variables start mov.ab #last-src, src mov.ab #(lastQ.)-dest, dest mov.ab #last-src, count ;Do the copy loop mov.i