Subject: Re: Looking for MARS for the C-64 From: benh@eecs.umich.edu (Benjamin Harrison) Date: Sun, 1 Dec 1991 03:09:57 GMT Message-ID: This may be obvious, but the strategies one would use in a core of size 8000 or so is so completely different than the strategy one could use in a core of size 8000000 or so as to be extremely important. I mean, if you want to write any kind of intelligence into your program, it is important that your program be much smaller than the total core size. If your program is, say, half the core size, not only will most assemblers refuse to let it play, but it will be unable to reference itself, and will probably die immediately. But an intelligent program of say, size 1000, could very easily survive against almost anything in a core of size 1000000, where it occupies only 1/1000 of the core, but can do a lot of high level processing. If nothing else, I would recommend allowing some form of access to the 'coresize/2' constant. Perhaps in data statements, with 'MEMSIZE' as a predefined constant. But with such miniscule core sizes, I think intelligence will lose out to tiny persistance in the long run. Any thoughts on this? --------------- Ben/Bosk ---------------- Subject: Memory bombing (long) From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: Mon, 2 Dec 1991 16:47:45 GMT Message-ID: <1991Dec2.164745.12728@descartes.waterloo.edu> Several things I want to bring up. First. About the pre-decrement indirect instruction. What was the argument for introducing this mode? As far as I can tell, it was a way of letting the programmer do things like copy and bomb much faster than with the DJN, SUB, or original DJZ. I find that it just doesn't fit in with the regular CW instruction set. Just call me over-critical. And further, where is the pre-increment indirect? ----------------- The following ideas may have appeared somewhere in TCWN or some CW correspondence about the world. I've never seen anything one it though (maybe 'cause I haven't followed CW other than Scientific American and recently this group.) However, I'm sure there are others whoi haven't seen anything like it, so this is for them... Oh, yes, I'd like to mention that these ideas may not be viable for a good competition warrior. I couldn't care less. I just like to program for the sake of programming, and competition is quite secondary to inventing neat new concepts. However, if someone puts any of these ideas together into a good battle program, I'd like to hear about it. And maybe you could put a line into the source giving me credit... ----------------- This weekend, I was sort of bored and looking for something to do (actually, trying to avoid studying for finals...) so I started paging through a pile of CW stuff I've compiled over the years. At some point, an idea hit me. I hit back, and a major tussle stated. It won, and I was forced to boot up the handiest implementation of CW and actually test the idea. A little prelim stuff... Howitzer Fangs I suppose many are familiar with the good old fashioned vampiric fang. The one that looks like JMP @1 DAT wherever_you_want_them At some point, I came up with a variation, which I call the Howitzer fang (after a program named Howitzer) The basic fang looks like MOV 1,@1 DAT Some_address As Howitzer was written, it would bomb the world with these fangs, and if one was hit, the program hitting it would send it's relative location back to a Howitzer and die. Howitzer would then bomb the area hit, really heavily. You might be saying "So it bombs the place. It's already dead. Why bother?" Good point. This was written with the purpose of killing programs with good regeneration capabilities, like the Five Musketeers, or a few of my own. It's a pretty specific purpose program... A later incarnation of Howitzer simply replaced the fang. As I was using R.Martin's Mac implementation, I also used the PCT instruction to defend the cell. If a program regenerated onto the spot without bombing the place, it would likely hit the fang again. Very deadly against regenerators, and it would also handle imps and stuff. A later program I designed was a slave driver called Whip. It would launch fangs which looked like MOV 2,@2 JMP 0 DAT whatever I never got around to implementing Whip, but the theory was pretty complex. When an enemy hit the fang, it would signal Whip and sit on the JMP 0 until Whip picked it up. Whip would copy a simple slave program, the n send code to make the captured program jump to that slave. The slave program was loaded with the location it was captured at, and it was dedicated to bombing the point it was captured over and over and over again, until Whip finally killed it. Or was it suppoed to replace the fangs? Whatever, one or the other, it was still pretty complex. The whole Howitzer/Whip arguement is leading up to the biggy. The thing about Whip is that it would create as many new slave programs as captured prorgams were brought in. No real limit to things. (Some people are probably nodding and saying "uh huh" in an abstract tone of though) Memory Bombing So what hit me this weekend is the ultimate way to burn the hell out of programs that like to regenerate on the same location. Memory bombing. Essentially, the program launches Howitzer fangs. When a program returns an address, it will put the address at the end of a list, and every once in a while, it will go through the list and bombs every locations (and area around) Really simple, and surprisingly easy to implement. Took me about two hours to write, debug, and test. I wrote a simple program called Memory 1.0 to demonstrate the concept. Unfortunately, I don't have a ICWS '88 implementation handy (well, I have one, but my IBM is in Toronto) or I would have wrote it up in that. I couldn't even upload the code of the one I wrote, or I would have tried that too. Such is life. Here goes with a rough approximation of what it looks like, with an attempt to modify it to ICWS '88 standards. I'll try to find time and disk space for the x11 CW, and then I can do a good write-up and test. Sorry about the org-expressions. A hold over from the original. ; Memory 1.0 rough-idea-code Chris Beauregard Dec 1,1991 @-3 target dat 0 ; target for dumping fangs fang mov 1,@1 ; basic Howitzer fang bite dat 0 ; bite, each fang should point to gotone ; when placed @0 mainloop jmn addone,gotone ; this is the start of the program, and ; the main loop. Note that bite and target ; should have value loaded when the program ; starts up. depends on how you write it ; though. ; Oh, yeah, what are we doing. If gotone is ; not a zero value, go to addone, because it ; means a program has returned its location. [ insert vampiric fang placement routine here. Just make sure that the bite value placed always points to gotone, or you could have some serious problems. ] djn mainloop,count ; when count hits zero, bomb the target ; addresses known. I use count at 100, but ; whatever pleases you... bomb mov #100,count ; reset count jmz mainloop,numgot ; trying the bomb without targets would be ; useless and probably fatal. ; setting up for each bomb run. setup mov numgot,curgot ; move the value containing the number of ; known targets to curgot, so we can change ; it while bombing. add #1,curgot ; and add one. Check how numgot/curgot are ; set up, adn you'll set why. mov #5,target2 ; set up for bombing first target location. sub @curgot,target2 ; Since the value returned is relative to ; Memory, and negative, we have to change ; it so we're pointing the right way (shitty ; explanation, I know... ; The #5 is an offset, so we start bombing ; about 5 cells before the location the ; fang returned. mov #10, attacks ; we bomb each target for 10 cells. You ; can change to suit. bombloop mov #0,@target2 ;a basic bomb loop. ICWS '88 code would ; likely speed it up. add #1,target2 ; increment target djn bombloop,attacks ; loop back, until 10 cells bombed. sub #1,curgot ; decrement curgot, so it points to another ; target cmp curgot,#1 ; if 1, back to mainloop. jmp mainloop jmp setup ; else setup for next run. ; adding a target location. simple process. Simply add one to numgot, ; which points to the last target address stored, move the address in ; gotone to the new location, and reset gotone to zero. ; Oh, and 'addone' might not work as a label. I spent a while looking ; for this bug before I realized the assembler probablt though it was ; opcode. addone add #1,numgot ; increment numgot. mov gotone,@numgot ; move target to last location. mov #0,gotone ; reset gotone jmp mainloop+1 ; jump back to loop, one past where we ; were called from. '+1' not necessary, but ; I try to keep way from redundant code... ; now the data structures. count dat 100 attacks dat 10 target2 dat 0 ; for max efficiency and not having to do ; a lot of arithmetic, I keep target close to ; gotone. You can have it anywhere by just ; changing the mov #5,target2 to whatever ; gives the appropriate offset. gotone dat 0 ; bites point HERE! curgot dat 0 numgot dat 0 ; target locations are added here. numgot points to the last in the series ; which is why we add one when curgot is setup. curgot has to point to ; the last in the series while we're working. A little messy, but with all the comments, probably useable. As you can imagine, unless you really optimize the code, especially the fang placement code (at least what I wrote!) it's a bit slow. As well, it has nothing for imps, worms, what-have-you. It's also immobile, but that's not a big problem. The biggest problem is that as more targets are found, the time it takes to bomb them all goes up bigtime. And it's only really effective against programs that like to regenerate into the same location. The ones I've written with good regen capabilities are all mobile, and especially avoid areas they know have been bad for them in the past. I guess a lot of this is implementation. Who knows, someone might be able to scrap together a powerful system from this... Enjoy... -------------------------------------------+--------------------------------- Chris Beauregard | If all the world's a stage, what cpbeaure@descartes.waterloo.edu | do we do when the audience starts "If you can't beat 'em, take 'em with ya!" | throwing stuff? Subject: Memory Bomb - implementation From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: 3 Dec 91 17:08:03 GMT Message-ID: <1991Dec3.170803.6133@descartes.waterloo.edu> Okay, I managed to at least get the code for Memory 1.0, as written in R.Martin implementation, onto my unix account. Here it is... ------------------------------ * Memory 1.0 Chris Beauregard Dec 1,1991 * INTRODUCTION * This is an implementation of a concept called "memory * bombing." A program will, somehow, find the location of * a program, and "remember" its location. The program then * has the locations available for later use, be it bombing, * vampire fangs, or anything else... * METHOD * Sends out Howitzer fangs, and as data comes in, puts the * locations at the end of the program. Every once in a while * it bombs the area. * Howitzer fangs, btw, are derived from a program I wrote * called Howitzer. Instead of having the target jump * to where we are, it just returns its address relative to * us back to a certain location, and we do something with it. * Howtizer would bomb the area and then replace the fang. * Combined with the PCT command on the fangs, this could * kill just about anything... * SPECIFICS * The main loop does a typical vampiric fang placement, the * fangs being modified so that instead of the program jumping * back, it returns its location to gotone and dies. * If the main program finds something in gotone, it adds it * onto the end of a series of target locations, and increments * the number of known targets. * After every 100 fangs placed, the main program goes and * bombs all target addresses known. This value could be * changed depending on preferences. * COMMENTS * Very deadly to regenerating programs. At least the ones * that regenerate in the same location (i.e. Five Musketeers) * As the number of target locations increases, the length of * the bomb time increases. This could be a problem. * No protection from imp based programs, and non-mobile. It's * just a test program though. * The fang placement is way too slow. Using ICWS standard * opcode would change that. * Does not use ICWS standard. Uses original A.K. Dewdney, * with 1985 SPL opcode added. For R.Martin Mac version of * Core Wars, 1985 @-3 target dat 63 * target for fang drops fang mov bite,@bite * basic fang code bite dat -34 * return value for fang * points to gotone @0 start mov #63,target * set fang pointers mov #-34,bite mainlup jmg got,gotone * if we have a return, process add #9,target * place fangs jmz start,target * uses standard vampiric mov bite,@target * fang placement sub #1,target mov fang,@target sub #8,bite djz memory,count * countdown for memory bomb jmp mainlup * loop back memory mov #100,count * memory bomb. reset counter jmz mainlup,numgot * if nothing, return mov numgot,curgot * set for attack loop add #1,curgot loop mov #-5,target2 * setup for bomb. sub @curgot,target2 mov #10,attacks * we bombs 10 cells at target * area. loop2 mov #0,@target2 * main bomb loop add #1,target2 sub #1,attacks jmg loop2,attacks sub #1,curgot cmp curgot,#1 jmp mainlup jmp loop got add #1,numgot * add a target point mov gotone,@numgot mov #0,gotone * reset gotone jmp mainlup+1 count dat 100 @34 target2 gotone dat 0 * where fangs return values attacks dat 0 curgot dat 0 numgot dat 0 * number of known targets * points to last in series * target data starts here, as it's added. *CB ----------------------- If you're not familiar with this form of code, and you want to convert it to ICWS '88, look into the orginal two A.K.Dewdney Core War columns from SA, or The Armchair Universe...SA May '84 and March '85, I believe... This is pretty much the same as the code from my original post, but you might want to inspect this for actual implementation details. Now, we need some major improvements. Mobile code, including copying and updating the target points (and making sure none of them were pointing to where we have just moved). Imp protection. Adding a simple imp killer will probably save us from a lot of that stuff. It will slow down bombing. Faster fang placement. This is really important. The program is useless if it can't hit before getting hit. Faster bombing. This shouldn't be hard. I think I used the DJN opcode in my original posting to cut it to three lines... ------- I'm afraid a lot of the techniques might be a little inefficient compared to some of the stuff developed by the ICWS community in the past years. This happens when you haven't followed changes in the game. I'd especially like to see a better fang, and fang placement. I've seen the improved vampired JMP fang ( the jmp @0,something) that you get from being able to play with the B operand. I think I've figured out a way of doing this, by using the fang as mov 0,whatever Where whatever points to gotone. The whole instruction gets moved, and you have to B operand to play with. I guess you have to move and entire dat 0,0 instruction to reset gotone though. I'm not sure qbout this, though, I'm not all that familiar with the ICWS '88 structure. If someone would comment on this method... I notice that ICWS standards could probably do a lot for this program. If I have some spare time during exams, and my IBM back, I'll rewrite this with a pile of major fixes, and repost the whole discussion... -------------------------------------------+--------------------------------- Chris Beauregard | If all the world's a stage, what cpbeaure@descartes.waterloo.edu | do we do when the audience starts "If you can't beat 'em, take 'em with ya!" | throwing stuff? Subject: King of the Hill From: wms@iwarp.intel.com (William Shubert) Date: 4 Dec 91 06:02:32 GMT Message-ID: <1991Dec4.060232.7106@iWarp.intel.com> OK, folks, I spoke of it earlier and now it's ready. An implementation of King of the Hill corewar - a cumulative tournament. Justin seems to have finished up his also, but hey, enter both! How to enter? Simple! Format your corewar program as follows: ;redcode ;Name ;Author And mail it off to: wms@iwarp.intel.com The ";redcode" line is very important; without it my demon will think that it's mail for me and not enter it in the tournament. After receiving your mail, the demon should within a few minutes try to assemble it and reply to you with a message either telling you that all is well or that your program couldn't compile. If something goes wrong it will try to tell you what. The assembler is fully ICWS '88 compatible WITH the following exceptions: A comma is required between two operands. The EQU pserdo-op does a parenthesized text insertion instead of straight text insertion. The core size is 8000 instructions. In addition to the normal +, -, *, and / operators parenthesis can be used in an argument. I do not think that this is in ICWS '88. Notice that it implements every goofy restriction in the standards; for example, DAT instructions can only support immediate or pre-decrement argument(s). So hurry up! Send any program you have, no matter what it may be like, and when I get enough together I'll run the tournament. It is round-robin with every program playing every other 10 times (5 going first, 5 going second). 3 points for a win, 1 for a tie, 0 for a loss. SAMPLE PROGRAM: ;redcode ;name Dwarf ;author A. K. Dewdney bomblen: equ progend - bomb bomb: dat #0 start: add #bomblen,bomb mov bomb,@bomb jmp start progend: end start PS - DON'T include a line like ";address this problem" in your code; this will be interpreted as your return address for a mailer. PPS - I may not have sufficiently tested this program. It may crash, in which case all later programs sent in will not get replies. If this happens, please bear with me. Also, if you get a "weird" error message tell me about it. -Bill (wms@iwarp.intel.com) Subject: Re: Version 3.01 of CoreWar Pro (PC) available From: hallyb@globbo.enet.dec.com (John Hallyburton) Date: 5 Dec 91 14:40:28 GMT Message-ID: <31186@nntpd.lkg.dec.com> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >P.S.: Coming soon to soda: 2DCORE V1.0, a two-dimensional Core War system for >PC-compatibles I'm taking MAD's advice and waiting to see if the itty-bitties can be beaten before declaring support for 2-D CW. BUT in the interests of not getting shut out, I hope 2DCORE implements a "PC increment vector" rather than, say, just a "right turn" instruction. Thus, "PCI #1 #2" increments the "X PC" by 1 and the "Y PC" by 2. Of course, a matching "Assemble/Load this program 1-by-2" pseudo-op would be needed as well. Who knows, maybe we'll find out a "New York taxicab" program is the KOTH. -- "The Smart Money was on Goliath" John Hallyburton 43 55'N 71 45'W Subject: King of the Hill From: wms@iwarp.intel.com (William Shubert) Date: 5 Dec 91 16:18:44 GMT Message-ID: <1991Dec5.161844.22993@iWarp.intel.com> OK, King of the Hill seems to be going well; I've gotten a bunch of programs, maybe there'll be a tournament tomorrow. Before I decide I've got to make sure that they are all "real" programs and not a bunch of Imps people sent in to test the system (I know that a few people have done this, and I don't mind. I realize that people want to make sure that this works before they go through the effort of submitting a real entry.) I have gotten a request for more information about the program, so here are more stats: Game length - 80,000 cycles per player. I figured 10 laps around the core for an Imp is enough time to win. Max processes - 8,000 per player. I wanted to simulate a truly infinite number; I looked at the core size and decided that one process per memory cell should be enough. Maximum program length - 100 instructions. I was considering entering the tournament myself, but there's a bit of a problem here; since I am running the tournament, I can look at anybody's code and (in theory) write programs based on their weaknesses. So I have decided that if I do enter, I will first post my code here so that everybody can see it. -Bill (wms@iwarp.intel.com) Subject: 2D Core War, was Re: Version 3.01 of CoreWar Pro (PC) available From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 5 Dec 91 19:51:35 GMT Message-ID: <1991Dec5.195135.17741@vuse.vanderbilt.edu> In article <1991Dec5.043605.495@descartes.waterloo.edu> Chris Beauregard writes: >>P.S.: Coming soon to soda: 2DCORE V1.0, a two-dimensional Core War system for >>PC-compatibles > > This is interesting... > > Could you maybe post the standards for this system? At least a rough outline. >I think a lot of us would be interested in picking it over... I'm glad I was able to stir up some discussion before casting my ideas in stone, er, code. 2DCORE still exists only on paper, but since I am going to use my "1D" system as a template the actual implementation will be fairly painless. > How are you setting up the core, and all that? Just a standard grid? For display, the Y-axis will be scaled to the monitor width, the X-axis to the height (core(X,Y) => screen(Row,Column)). The only real change is the topology of the Core: a torus (Imagine rolling up a piece of paper to a tube and sticking the ends together). The dimension of the Core will be adjustable within the limits of available memory (probably to a max of 32K cells: 181x181 grid). X- and Y-axis can be adjusted independently for a square or rectangular grid; e.g. coresize(1,8192) would emulate a 1D core. >Chris Beauregard | If all the world's a stage, what In article <31186@nntpd.lkg.dec.com> John Hallyburton writes: > >I'm taking MAD's advice and waiting to see if the itty-bitties can be beaten >before declaring support for 2-D CW. BUT in the interests of not getting >shut out, First of all, it is certainly not my intention to "shut out" anyone. I doubt very much that the idea of a 2D CoreWar has matured sufficiently to warrant any standardization effort. I'm writing my 2D CoreWar system because I think it's a neat idea, and because I'd like people to play with it and perhaps come up with better ideas. It helps "beating out itty-bitties" if you have something faster than paper and pencil to run your programs with. > I hope 2DCORE implements a "PC increment vector" rather than, say, >just a "right turn" instruction. Thus, "PCI #1 #2" increments the "X PC" by 1 >and the "Y PC" by 2. Although I suggested PCI myself in a recent post, I no longer think it's such a great idea: (1) It discourages "odd-shaped" programs, because an execution cycle is wasted for every "corner" a program's flow of control takes. (2) More importantly: the implied ability to specify X- and Y-increments >1 breaks what Mark Durham in a recent post called "the speed of light", i.e. one address/execution. I dread the idea of an imp racing through core at arbitrary speeds and trajectories. Instead.... My thinking was to add an extra 3-bit "direction-field" to each instruction. Values from 0 to 7 would specify which of the 8 adjacent cells flow-of-control proceeds to (unless, of course, a jump is executed). E.g.: 3 2 1 \ | / ;two-dimensional imp, moves diagonally 4- * -0 ;core(0,0) is upper, left / | \ MOV [0,0] [1,1] 7 5 6 7 ^direction field Note that the direction field is *not* a third operand; it should be conceived as part of the opcode in that addressing mode characters are not allowed before it. If it *was* implemented as a direction operand, objection (2) above would still apply. > Of course, a matching "Assemble/Load this program 1-by-2" >pseudo-op would be needed as well. > John Hallyburton 43 55'N 71 45'W Here's what I have in mind: Preface instructions in your 2D redcode file with a coordinate relative to the first instruction, which is [0,0]. I.e. for a piece of code layed out diagonally: [0,0] start mov #init addr 7 [1,1] cmp #[0,1000] counter .. To make thinks a little less tedious to write, two consecutive instruction labeled with "program coordinates" will set the default for the following lines of code, i.e. [2,2], [3,3] in the example. As a last thought: Why do I think 2D CoreWar is such a neat idea? Because simple-minded programs such as Dwarf and Imp have no chance of competing successfully (Imp would only overwrite one "line" of the grid; and Dwarf would need a double-loop with boundary-check to bomb all of core, which takes away its primary advantage: speed). -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: Re: 2D Core War, was Re: Version 3.01 of CoreWar Pro (PC) available From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: 6 Dec 91 03:31:38 GMT Message-ID: <1991Dec6.033138.28025@descartes.waterloo.edu> In article <1991Dec5.195135.17741@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >> How are you setting up the core, and all that? Just a standard grid? > >The only real change is the topology of the Core: a torus... ^^^^^ We call it a donut... >First of all, it is certainly not my intention to "shut out" anyone. I doubt >very much that the idea of a 2D CoreWar has matured sufficiently to warrant >any standardization effort. I'm writing my 2D CoreWar system because I think >it's a neat idea, and because I'd like people to play with it and perhaps >come up with better ideas. It helps "beating out itty-bitties" if you have >something faster than paper and pencil to run your programs with. Who needs a reason other than that? I write a lot of useless programs just for the sake of seeing what they'd do... >E.g.: 3 2 1 > \ | / >;two-dimensional imp, moves diagonally 4- * -0 >;core(0,0) is upper, left / | \ >MOV [0,0] [1,1] 7 5 6 7 > ^direction field You'll have to bear with me if I'm slow today, but why the [0,0] [1,1]? As far as I can see, you're moving the current cell one cell in direction 7. Wouldn't MOV 0,1,7 accomplish the same thing? I'd say it would be much cleaner to write... >> Of course, a matching "Assemble/Load this program 1-by-2" >>pseudo-op would be needed as well. > >Here's what I have in mind: Preface instructions in your 2D redcode file with >a coordinate relative to the first instruction, which is [0,0]. I.e. for a >piece of code layed out diagonally: > >[0,0] start mov #init addr 7 >[1,1] cmp #[0,1000] counter >.. > >To make thinks a little less tedious to write, two consecutive instruction >labeled with "program coordinates" will set the default for the following >lines of code, i.e. [2,2], [3,3] in the example. I think [2,2] then [3,2] would be nicer. Keep the program linear, along one axis, until the programmer decides to start screwing around...If you tried a 8192,1 core, it would generally work... But that's just nit-picking... >Because simple-minded programs such as Dwarf and Imp have no chance of >competing successfully (Imp would only overwrite one "line" of the grid; and >Dwarf would need a double-loop with boundary-check to bomb all of core, which >takes away its primary advantage: speed). >Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu I mentioned this a while ago, but I'd like to bring it up again for consideration. The Chris Beauregard approach to a 2D core... Use a torus shaped core, but instead of and x-y grid, you would use the typical 1D core with a variety of streams. Essentially a pile of 1D cores sandwiched together. The direction opcode (or whatever you're calling it) in this case would be the stream offset for data movements, jumps, etc. In this case, the typical imp would be ;imp MOV 0,1,0 ^ means don't change streams... This imp would be limited to whatever stream it started in. While it would still be fast, it sure as hell wouldn't be as effective with, say, fifty streams to choose from. The typical Dwarf wouldn't hack it either... A gemini which copied itself sideways through the streams would become ;stream gemini ;sorry, this is old code. I don't have a modern gemini handy... ;to work from, and I don't feel like remembering the improved... source dat 0,0 ;dat instructions don't allow streams... dest dat 0,0 start mov @source,@dest,1 ;move the element from this stream to the ;dest in the stream one over cmp source,#11,0 ;this stream... jmp cleanup,0,0 add #1,source,0 add #1,dest,0 jmp start,0,0 cleanup mov #0,source,1 ;set source in the other stream to zero mov #0,dest,1 ;same with dest jmp start,0,1 ;jump to the copy in the other stream end start This method would not change the direction of the programs execution. It would always be in the same direction, but perhaps in different streams... This means that a single instruction imp would be stuck in just that one stream. Really easy to avoid. I can see a really neat attack program now. Copy ahead, bomb sideways... I personally think that this would be much, much easier to implement. You just have to modify the assembler for that stream change, and then set your current implementation up for the extra streams...As far as I can tell, you don't even need to change the standard instruction set. One thing to note. I think the third operand is gonna be essential in just about any implementation, but it 'stream' method of 'grid' method...If anyone has an alternative to that, I'd like to see it... I'm not saying it's the most fun, or leads to the best programs. Just tossing another idea on the fire... -------------------------------------------+--------------------------------- Chris Beauregard | If all the world's a stage, what cpbeaure@descartes.waterloo.edu | do we do when the audience starts "If you can't beat 'em, take 'em with ya!" | throwing stuff? Subject: Are there Standards for the Timer ? From: S_BLEYER@rzmain.rz.uni-ulm.de (Mike Bleyer) Date: 6 Dec 91 07:09:51 GMT Message-ID: <1991Dec6.070951.18185@wega.rz.uni-ulm.de> Hello ! I've been testing some new warriors of mine in competition with others and came up with a question. My core has the size of about 8000 cells, and the Timer is set to 10000 rounds. I think the Timer should be at least twice the core size, so that a program is able to bomb the whole core at least once (bombing requires 2 rounds for 1 bomb, move and jump). Now does anyone know if there are any standards for the Timer settings ? Or official rules or something ? The same question for scoring in a tournament with pairs: Loosing scores 0 points, tieing scores 1 and winning 2 or 3 ? I think that a tie should score 0 as well because the object of the game is to win. Writing a program that survives is very easy (just split up), but actually killing the other is hard and therefore should be awarded more points. What do you think about that ? Mike -------------------------------------------------------------------------- / Mike Bleyer on Internet | Don't eat. Don't sleep. | S_Bleyer@RZMain.RZ.Uni-Ulm.DE | Don't do your math assignment. | Meet Smacks on IRC ! | Play Core Wars ! -------------------------------------------------------------------------- Subject: King of the Hill - Tournament imminent! From: wms@iwarp.intel.com (William Shubert) Date: 6 Dec 91 08:34:27 GMT Message-ID: <1991Dec6.083427.17774@iWarp.intel.com> I do have enough entries to perform a tournament. I was hoping for Friday morning, but the tournament is not fully automated (yet) and work is getting real hectic so I don't think I'll have time to run it until Saturday or Sunday. As soon as I do run a tournament I'll mail the results to all contestants and post a summary to this newsgroup. So everybody who wants to enter but hasn't yet - Do so! Hurry! In addition, I promised to post here my entry. I call it the Leech, because it does pretty much the same thing as vampire but it's smaller. Actually, I like larger, more complex Redcode programs, but alas the leech eats them like popcorn. The leech is tremendously optomized for minimum space and maximum speed. PS - Saw Terminator 2 tonight again. Now THAT was fault-tolerant coding. ;redcode ;Name Leech ;Author William Shubert ;A modification of the Vampire (written by Robert Martin). ; Basically, like a vampire but much smaller. Faster and more vicious, too. ;Algorithm: Drop bites in memory, spreading them well. By arranging code ; correctly, I use 3 out of every 4 words. This enables me to drop the ; bites in every fourth word. However, dropping them in every 33rd 4-word ; space gives a fairly good spread through memory. ; Each bite is a jump to the "drain" part of code. To be real nasty, I make ; the competitor kill itself. The drain runs through code, dropping a DAT ; instruction in each place and splitting constantly. Eventually the ; drainer will overwrite itself. It is important that it FIRST kills the ; "SPL" instruction then the "MOV"; if the MOV died first the splitter would ; live on forever and cause a tie. ;Notice that by using "bmove" to both add to the jump address of a bite and ; subtract from the location where the bite lands I make the leech as fast ; and as small as a Dwarf. Also, instead of adding an extra "DAT" statement ; for the location where the draining clear is being used I use the B location ; of the SPL instruciton. This saves an instruction and makes me a smaller ; target for other figters. ;I believe that this is the smallest, fastest, and nastiest single-process ; vampire possible. It can be improved by producing multiple leeches. Good ; idea for a future project. However, this will improve the win ratio ; against Dwarves, etc. while decreasing the win ratio against other ; vampire-style programs. ;Label description: ; bdist is the distance in memory that will separate each bite. ; bite1 is how far away to drop the first bite. ; dstart is the starting address for draining. Since the drain uses a ; predecrement addressing mode, dstart will NOT be wiped out. The first ; address before it will be wiped out. ; bmove, when added to the bite, produces a new bite with both the new address ; to place the bit and the new JMP address for the bite itself. ; leech is the start address. Notive I do a MOV then an ADD unlike the Dwarf; ; this may just give me an extra instruction sometimes. ; bite is both the "jump to drain" instruction and the destination address for ; this instruction. ; drain is the start of the function where a fighter will kill itself. If ; some part of this routine is corrupted, hopefully the program forced to ; jump here will kill itself even if it can't kill all it's brethren. ; clrloc is both the SPL (which is necessary to ensure that the drain process ; will move faster than the other enemy processes) and the target for ; draining. ;OK, enough of these comments. Start the leech code. bdist equ 33*4 ;In an 8000 word core, this will hit every 4th ; word eventually; in the meantime it will ; get a good scatter. bite1 equ bite-128 ;Drop the first bite somewhere useful. dstart ;Start "draining" here. bmove dat #bdist,#-bdist dat #0 ;A bite will land here eventually, so I can't ; use this location. leech mov bite,@bite add bmove,bite jmp leech bite jmp drain-bite1,bite1 ;A bite will land here, but it will ; cause no change since it will write itself. drain mov bmove, In article <1991Dec6.033138.28025@descartes.waterloo.edu> cpbeaure@descartes.waterloo.edu (Chris Beauregard) writes: >In article <1991Dec5.195135.17741@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >>E.g.: 3 2 1 >> \ | / >>;two-dimensional imp, moves diagonally 4- * -0 >>;core(0,0) is upper, left / | \ >>MOV [0,0] [1,1] 7 5 6 7 > >Wouldn't > >MOV 0,1,7 > >accomplish the same thing? I'd say it would be much cleaner to write... Not in the scheme I'm proposing. Perhaps I should've explained myself better: the direction field does not influence the direction in which the address is MOVed, but how the X-PC and Y-PC are incremented after execution. According my little diagram above "7" means: X-PC' := X-PC + 1 Y-PC' := Y-PC + 1 The direction of the MOVe is implicit in the A- and B-operands, and happens to coincide with the direction of execution (that's how imps work after all) Chris continues to lay out his idea of 2D Core War: > Use a torus shaped core, but instead of and x-y grid, you would use the >typical 1D core with a variety of streams. Essentially a pile of 1D cores >sandwiched together. > The direction opcode (or whatever you're calling it) in this case would be >the stream offset for data movements, jumps, etc. > > In this case, the typical imp would be > >;imp >MOV 0,1,0 >;stream gemini >;sorry, this is old code. I don't have a modern gemini handy... >;to work from, and I don't feel like remembering the improved... >source dat 0,0 ;dat instructions don't allow streams... >dest dat 0,0 >start mov @source,@dest,1 ;move the element from this stream to the next Wait a minute, am I missing something? If "1" in the above line denotes the "stream offset", how do we move from the current to the stream *before*? mov @source,@dest,-1 ? Ok, now: How does a move from the next to the current stream get accomplished? Impossible? Methinks that you need *two* stream offsets, one for each operand: mov @source,@dest,0,1 ; move from current to next stream mov @source,@dest,0,-1 ; move from current to previous stream mov @source,@dest,1,0 ; move from next to current stream a.s.o. You may notice that this corresponds exactly to my version of 2D Core War, only the notation is different. I would write (replacing "stream" by "row"): mov @source,@dest+[1,0] ; move from current to next row mov @source,@dest+[-1,0] ; move from current to previous row mov @source+[1,0],@dest ; move from next to current row I left out the direction field in my example, since it defaults to "0" (execute from left to right). > This method would not change the direction of the programs execution. >It would always be in the same direction, but perhaps in different streams... Agreed, and that's the only thing that's different between our approaches. > I personally think that this would be much, much easier to implement. >Chris Beauregard | If all the world's a stage, what Disagreed, see above. Comments? -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: Re: 2D Core War, was Re: Version 3.01 of CoreWar Pro (PC) available From: kwhyte@dickson.uchicago.edu (Kevin Whyte) Date: 6 Dec 91 21:42:42 GMT Message-ID: <1991Dec6.214242.7726@midway.uchicago.edu> The "2-d" proposal with streams is exactly the same thing as the "paging" proposal I made earlier (and perhaps hastily). The main difference was there I proposed to limit the ability to affect other streams to the ones 1 in front and 1 behind. For this, we don't need new fields, only new addressing modes, + and -. To distinguish this from sign we use $ for direct, and put the +/- before the usual symbol. For example, mov $0 $1 is a standard imp, as is mov $0 $+1 but mov $0,+$1 moves the current instruction one forward and into the next page. This is really no different from adding the other two fields, and restricting them to be -1,0,1. It is, however, backwards compatible. Personally, I still like the idea, but it needs testing. It seems clear that it will take quite a while for programs to find one another. This scheme also makes imps much less useful since they never leave the page they start in. The experimentation with the instruction which allows a program to see whether any given page has anything executing in it leads me to withdraw that suggestion. On the other hand, the spl modification I suggested seems to work well. The way I finally implemented it was as follows: spl a b splits off a process starting at a, which will execute 1 time for every b times the parent does. (b=0 means just jump). now, one surprising aspect of this is the following: If we have a program which splits off an imp stomping process (say w/50% of the time) then splits off an imp and starts bombing core, we can determine easily when the imp dies. The idea is, say every 100 bombing cycles, to compare the bombing process to the stomping process in speed. If the imp is alive, the stomping will be faster, otherwise they'll be equal. if done correctly one can even determine approximately where the imp died, and the bomb that part of memory. This results in a fairly effective warrior and opens up whole new strategies to consider! If enough people are interested, we can hash out some suggested modifications to corewar. The author of KotH (wms@iwarp.intel.com) told me that eventually he intends to have two tourneys going, one ICWS '88 and the other with rule changes the net comes up with. Sounds cool to me! Kevin kwhyte@math.uchicago.edu Subject: Load Effective Address ? From: bostrov@prism.cs.orst.edu (Vareck Bostrom) Date: 7 Dec 91 03:05:01 GMT Message-ID: <1991Dec07.030501.8414@CS.ORST.EDU> Hi! I don't corewar much but I do program in assembly on the MC680x0 , the iAPX86, and the MC56001 DSP, and I saw this group, read it, saw that a new corewar program (CoreWar pro) was available from soda, so I nabbed it and fired it up. In no time I was having a blast, writing simple programs and what not. As I moved into the more complex programs that I wanted to write, I found that I needed something like the Load Effective Address instruction. Is there anything like this? Say I had the (sample) code: ar1 dat 0 ar2 dat 0 ar3 dat 0 Now I want to get the abs. address of the label "a1", if it were a 68000 I'd say: LEA ar1,a1 or MOVEA.L #ar2,a1 (loading the address into register a1). What do I do in redcode? please send your wise replys to: bostrov@prism.cs.orst.edu Thanks! PS. CoreWar Pro 3.1 (3.01 ??) Subject: Re: 2D Core War, was Re: Version 3.01 of CoreWar Pro (PC) available From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: 7 Dec 91 13:27:28 GMT Message-ID: <1991Dec7.132728.25387@descartes.waterloo.edu> In article <1991Dec6.205504.1745@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >In article <1991Dec6.033138.28025@descartes.waterloo.edu> cpbeaure@descartes.waterloo.edu (Chris Beauregard) writes: >>In article <1991Dec5.195135.17741@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >>>E.g.: 3 2 1 >>> \ | / >>>;two-dimensional imp, moves diagonally 4- * -0 >>>;core(0,0) is upper, left / | \ >>>MOV [0,0] [1,1] 7 5 6 7 >>Wouldn't >> >>MOV 0,1,7 >> >>accomplish the same thing? I'd say it would be much cleaner to write... [Obvious expanation deleted...duh] Yes, I actually figured this out at some point. It took a while though... Yes, it would certainly work... >Chris continues to lay out his idea of 2D Core War: >accomplished? Impossible? Methinks that you need *two* stream offsets, one >for each operand: At some point, I actually realized this. I was looking at all the opcodes, and I noticed we'd have some serious ambiguities with things like DJN,JMN,etc. I actually tried to post something about this, but I was phoning in and cut cut off...a few times actually. >You may notice that this corresponds exactly to my version of 2D Core War, >only the notation is different. I would write (replacing "stream" by "row"): > >mov @source,@dest+[1,0] ; move from current to next row >mov @source,@dest+[-1,0] ; move from current to previous row >mov @source+[1,0],@dest ; move from next to current row Hmmm.. Just a quick question. How is the @dest+[1,0] working? Is it added to both, or what? I just don't see it. >> This method would not change the direction of the programs execution. >>It would always be in the same direction, but perhaps in different streams... >Agreed, and that's the only thing that's different between our approaches. Possibly true. But it's a biggy. It alters the whole philosophy of the programs written in either type. >> I personally think that this would be much, much easier to implement. >Disagreed, see above. Even with the two operands, you don't have to worry about things like direction of execution. The only major changes you have to make are to the assembler and the interpreter...as in how it processes the instructions. No major change to the flow of the thing. Your method would require a little more code aerobics. I can't say how much more though. I'd have to look at it in detail... >Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu -------------------------------------------+--------------------------------- Chris Beauregard | If all the world's a stage, what cpbeaure@descartes.waterloo.edu | do we do when the audience starts "If you can't beat 'em, take 'em with ya!" | throwing stuff? Subject: Re: 2D Core War, was Re: Version 3.01 of CoreWar Pro (PC) available From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 7 Dec 91 17:43:55 GMT Message-ID: <1991Dec7.174355.23640@vuse.vanderbilt.edu> In article <1991Dec7.132728.25387@descartes.waterloo.edu> cpbeaure@descartes.waterloo.edu (Chris Beauregard) writes: >In article <1991Dec6.205504.1745@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: > Just a quick question. How is the @dest+[1,0] working? Is it added to >both, or what? I just don't see it. 'dest+[1,0]' is simply an expression evaluated by the loader (such as @last-first+1 in 1D CW). In 2D CW 'dest' is a X,Y-coordinate; in the Gemini code: dest+[1,0] = [0,-1]+[1,0] = [0+1,-1+0] = [1,-1] This leads me to an erratum: Looking over Chris' Gemini code one more time, I realized that our two versions of 2D instructions are not equivalent. The intended semantics of mov @source,@dest,0,1 is evidently: move address pointed to by source to address pointed to by dest (in the same stream) offset by one stream (row). Whereas mov @source,@dest+[1,0] means: move address pointed to by source to address pointed to by "dest+[1,0]" (dest in the next row). Sounds confusing, let me try again: Chris' streaming instruction applies the stream offset after the effective addresses have been evaluated, whereas my version first calculates a new address (dest+[1,0]) and fetches the effective address from there. In this regard, Kevin's paging method (using +/- page selectors) appears to operate similar to Chris' stream offset. Am I right, Kevin? Just for comparison I'm including my version of 2D-Gemini: ;direction field defaults to "0": execute from left to right source dat [0,0] ;dat instructions don't allow streams... dest dat [1,0] ;next row start mov @source,@dest ;move the element from this row to the ;dest in the row one over cmp source,#[0,11] ;this row... jmp cleanup add #[0,1],source add #[0,1],dest jmp start cleanup mov #[0,0],source+[1,0] ;set source in the other row to zero mov #[1,0],dest+[1,0] ;set dest in the other row to one jmp start+[1,0] ;jump to the row in the other row end start I am certainly biased, but this appears to be a rather natural extension of linear Core War. As Kevin pointed out (sorry, don't have the article handy), his page method is equivalent to Chris' streaming method (except for the scope). Both extensions are similar (at least in intend) to Jon Newman's "address space" extension, which could be described as a "moving page frame". Neither employs [X,Y]-addressing and can therefore be considered 2D. What I had in mind is something truly two-dimensional, with programs of arbitrary "shape" (wedges, rectangles, stars) that move off in arbitrary directions and produce patterns similar to Conway's Life. A welcome side-effect of my proposal is that the grid is parcelled into streams or pages (which can be horizontal, vertical or diagonal rays depending on a program's direction of execution), but again, as others have pointed out, you don't need to go to 2D solely for that. -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: King of the Hill Results From: wms@iwarp.intel.com (William Shubert) Date: 8 Dec 91 02:20:40 GMT Message-ID: <1991Dec8.022040.12873@iWarp.intel.com> The King of the Hill tournament is over! There were 14 programs entered from 9 people. Each program played each other program 10 times and itself 5 times, for a total of 140 scores per program. First, here is a list of the entrants in order of how well they did: THE WINNER IS... 1. Program "slowdown1" (length 9) by "Mike Bleyer" (contact address "s_bleyer@rzmain.rz.uni-ulm.de") 280 points 2. Program "Sonic Kobold" (length 4) by "David Bofinger" (contact address "DXB105@phyvs1.anu.edu.au") 268 points 3. Program "Leech" (length 9) by "William Shubert" (contact address "wms@iwarp.intel.com") 242 points 4. Program "Dervish" (length 4) by "David Bofinger" (contact address "DXB105@phyvs1.anu.edu.au") 220 points 5. Program "Vlad" (length 27) by "David Bofinger and Tim Allen" (contact address "DXB105@phyvs1.anu.edu.au") 206 points 6. Program "Golden Horde" (length 96) by "David Bofinger" (contact address "DXB105@phyvs1.anu.edu.au") 202 points 7. Program "Influenza" (length 3) by "David Bofinger and Tim Allen" (contact address "DXB105@phyvs1.anu.edu.au") 199 points 8. Program "SLUICEGATE" (length 15) by "blojo@xcf.berkeley.edu (Jon Blow)" (contact address "blojo@xcf.berkeley.edu") 179 points 9. Program "Splitbomb3" (length 35) by "Kent Peterson" (contact address "FAC_PETERSON@vax1.acs.jmu.edu") 137 points 10. Program "Evade7" (length 49) by "Kent Peterson" (contact address "FAC_PETERSON@vax2.acs.jmu.edu") 128 points 11. Program "Memory 2.0 ICWS" (length 36) by "Chris Beauregard" (contact address "cpbeaure@descartes.waterloo.edu") 126 points 12. Program "wannabe2" (length 24) by "Kevin" (contact address "kwhyte%zaphod@gargoyle.uchicago.edu") 121 points 13. Program "Imp" (length 1) by "A. K. Dewdney" 111 points 14. Program "TinyTarget" (length 1) by "S. Lee ODEGARD" (contact address "n8243274@henson.cc.wwu.edu") 98 points A summary of the wins and losses for each program is below. Each contestant should receive a listing of the performance of their program against each competitor. PROGRAM W/ L/ T Score slowdown1 82/ 24/ 34 280 Sonic Kobold 85/ 42/ 13 268 Leech 71/ 40/ 29 242 Dervish 60/ 40/ 40 220 Vlad 56/ 46/ 38 206 Golden Horde 46/ 30/ 64 202 Influenza 44/ 29/ 67 199 SLUICEGATE 36/ 33/ 71 179 Splitbomb3 18/ 39/ 83 137 Evade7 26/ 64/ 50 128 Memory 2.0 ICWS 22/ 58/ 60 126 wannabe2 11/ 41/ 88 121 Imp 0/ 29/111 111 TinyTarget 0/ 42/ 98 98 Well, it was lots of fun (even though I didn't win). As soon as enough new entries arrive I can do a rematch. All entrants will remain in the tournament unless I get a request from the author to remove them. As has been mentioned here I think that this kind of tournament would be an ideal way to try out variants of Corewar. For now, though, everybody keep sending in your contestants! One last note: Because of Mark Durham's concern that the tournamt may have had too-short execution runs, I printed out a list of the time it took for each non-tieing fight to end. I found that only 15 fights, 1.53% of all fights that took place (2.69% of the fights that ended without a tie), took more than 40,000 rounds to end. I feel that this indicates that extending the maximum fight length will probably not have a significant effect on the score. Besides, my poor sun 3 took most of the day to run the contest as it was! -Bill (wms@iwarp.intel.com) Subject: Corewars improvements From: bediger@isis.cs.du.edu (bruce allen ediger) Date: 8 Dec 91 17:46:21 GMT Message-ID: <1991Dec8.174621.6973@mnemosyne.cs.du.edu> It strikes me that the most needed improvement to corewars is a "linear" addressing scheme. That is, in current cores the memory is 3 bytes wide: address 0 opcode operandA operandB 1 opcode operandA operandB 2 opcode operandA operandB . . . Where real computers are only one byte wide: address 0 opcode 1 operandA 2 operandB 3 opcode 4 operandA 5 operandB and so forth. The current arrangement prevents some really slicks tricks from being used. A "1 bytes wide core" would also prevent IMPS from being so effective. I don't think that a 1 instruction IMP could be made. Subject: _Real_ core wars From: bediger@isis.cs.du.edu (bruce allen ediger) Date: 8 Dec 91 18:17:04 GMT Message-ID: <1991Dec8.181704.7596@mnemosyne.cs.du.edu> Are there instances of two real programs that do the corewars type of battle in a real computer core? This is almost certainly possible, but it would be easier under an OS that supports "lightweight processes" or threads. Here is C code that (under Unix anyway) moves itself around in the address space. If you get a segmentation violation or something, try increasing the SIZE #define: I'm not sure they are up-to-date for tis version of the copyup() function. ----- #include #include #include int main(ac, av) int ac; char **av; { int i, j; int copyup(); int bcopy(); void funk(); void f2unk(); void f3unk(); /* check to see if cmd line has a number on it */ if (ac < 2) { printf("not enough arguments\n"); exit(99); } /* install 3 different signal handlers - avoid core dumps */ if ((i = (int)signal(SIGSEGV, funk)) == -1) { perror(" SIGSEGV signal failed"); exit(33); } if ((i = (int)signal(SIGILL, f2unk)) == -1) { perror(" SIGILL signal failed"); exit(33); } if ((i = (int)signal(SIGBUS, f3unk)) == -1) { perror(" SIGBUS signal failed"); exit(33); } /* * I did this to unbuffer the comments during recursion */ setbuf(stdout, NULL); /* * print out addresses of original functions so there is something to * reference during recursive function copying and calling */ printf( "main = 0x%x, copyup 0x%x, bcopy 0x%x, malloc 0x%x, printf 0x%x, free 0x%x\n", main, copyup, bcopy, malloc, printf, free); /* check argument for legitimacy */ if ((i = atoi(*(av + 1))) < 1) { printf(" recursions = %d, recursions must be > 1\n", i); exit(99); } printf(" going for %d recursions\n", i); /* * call text segment version of function with names of functions used * in it since it calls no functions directly. */ #ifdef NeXT /* * on NeXT (68040, ca 1991) need to flush cache. this trap does it. * may not be necessary here before the first call. */ asm("trap #2"); #endif j = copyup(1, i, printf, copyup, bcopy, malloc, free); printf("copyup at 0x%x returned %d\n", copyup, j); return 1; } #ifdef RS6000 #define SIZE 616 #endif #ifdef NeXT #define SIZE 228 #endif #ifdef hp9000s300 #define SIZE 276 #endif #ifdef mc68020 #define SIZE 0x100 #endif #ifdef sparc #define SIZE 0x170 #endif #ifdef mips #define SIZE 0x150 #endif int copyup(i, j, xptr, yptr, bptr, mptr, ffptr) int i, j; /* * since this subroutine calls no functions by name, need to send it * everything as a pointer. */ int (*xptr) (); /* pointer to printf() */ int (*yptr) (); /* pointer to this routine */ int (*bptr) (); /* pointer to bcopy() */ char *(*mptr) (); /* pointer to malloc() */ void (*ffptr) (); /* pointer to free() */ { int (*fptr) (); /* pointer to next copy of this * subroutine */ int k; if (i == j) { (*xptr) ("function at 0x%x got to %d'th copy\n", yptr, i); return i; } else (*xptr) ("function at 0x%x, i = %d, j = %d\n", yptr, i, j); /* * this is where it allocates empty memory in data segment for a new * copy of itself. SIZE gets used here. Note the clever casting of * the returned value from malloc. */ if (!(fptr = (int (*) ())(*mptr) ((unsigned)SIZE))) { (*xptr) ("ran out of memory allocating new function\n"); return -1; } /* * this is really a call to memcpy(). this is where the current copy * of the subroutine is copied to somewhere else in the data segment */ (*bptr) (yptr, fptr, (int)SIZE); /* * semi-recursive call to the freshly copied version of this * function. xptr, bptr, mptr, ffptr never change, they are the * addresses of the entry points to printf(), memcpy(), malloc() and * free(). fptr is the address of the current copy of the function. */ #ifdef NeXT /* * on NeXT (68040, ca 1991) need to flush cache. this trap does it. * I wonder if it ever has to be moved in the -S output before * assembly. */ asm("trap #2"); #endif k = (*fptr) (i + 1, j, xptr, fptr, bptr, mptr, ffptr); (*xptr) ("function at 0x%x got %d back from function at 0x%x\n", yptr, k, fptr); /* free() memory malloced above */ (*ffptr) (fptr); return (k + 1); } /* * signal handlers. these are pretty crude, but I havn't played with them * much */ void funk(sig, code, scp, addr) int sig, code; struct sigcontext *scp; char *addr; { (void)fprintf(stderr, " SIGSEGV: sig = 0x%x, code = 0x%x, addr = 0x%x\n", sig, code, addr); exit(99); } void f2unk(sig, code, scp, addr) int sig, code; struct sigcontext *scp; char *addr; { (void)fprintf(stderr, " SIGILL: sig = 0x%x, code = 0x%x, addr = 0x%x\n", sig, code, addr); exit(99); } void f3unk(sig, code, scp, addr) int sig, code; struct sigcontext *scp; char *addr; { (void)fprintf(stderr, " SIGBUS: sig = 0x%x, code = 0x%x, addr = 0x%x\n", sig, code, addr); exit(99); } ----- Subject: More on KotH From: wms@iwarp.intel.com (William Shubert) Date: 8 Dec 91 21:16:39 GMT Message-ID: <1991Dec8.211639.5900@iWarp.intel.com> A few more notes on the recent tournament: If anybody has any suggestion for improvements in how the tournament could be run, please mail them to me. If anybody submitted an entry and either didn't get results or didn't see their entry in the tournament, let me know. By the time I was done the whole thing was 99% automated so if there was a bug and an entry got dropped on the floor I would never know. Keep submitting your entries! -Bill (wms@iwarp.intel.com) Subject: Re: More on KotH From: snewman@Neon.Stanford.EDU (Steven Newman) Date: Mon, 9 Dec 1991 00:50:02 GMT Message-ID: <1991Dec9.005002.22630@CSD-NewsHost.Stanford.EDU> Will any information about the winning programs (or any of the submitted programs) be posted besides their name and score? It seems like the tournament would be more interesting in the long run if we could learn from the successful entrants; and if losing programmers got more feedback than just a low score. In most tournaments, participants come out with at least *some* information about why they did well or poorly and how to improve for next time. Of course, there's always the risk that any successful program will be immediately drowned in a slew of copycats, with or without minor modifications. I doubt that anything can be done about this except to appeal to people's sense of honor; trying to enforce a "uniqueness requirement" would be an exercise in frustration. At any rate, coming up with clever improvements on other people's programs should be what KotH is all about; and if too many people start copying any given program, then you'll see other programs that are specifically designed to win against that program (KotH is really a sort of ecology). - Steve Newman (snewman@cs.stanford.edu) Subject: KotH suggestions From: ajz@mentor.cc.purdue.edu (T. Tim Hsu) Date: 9 Dec 91 05:57:24 GMT Message-ID: <28812@mentor.cc.purdue.edu> This is a note about releasing the code to the public domain. I say that every person's entry BELOW a certain rank should be considered "public domain" and released to the network. The other "top" entries should only have their attack scheme described. Thus, in the recent KotH, I would say that entries ranked #1 and #2 should have their attack scheme described while the other entries should have their source code revealed. An example of a description of an attack, I'll describe W. Shubert's Leech program. Leech: Tosses a JMP statement into every 4th location of memory placing each successive JMP opcode 100-150 locations apart. The JMP points to a SPL statement which writes a DAT into every memory location and jumps back to the SPL statement. Eventually, the "captured" process will overwrite itself. This way, everyone would have an idea of how the top programs win without giving away too much. One more thing. I ran Leech against XTC (either the 1990 contest winner or else a very high placer) and it lost hands down with XTC getting a 5-2-3 record against it. The ties only occurred because XTC has a bad habit of not being able to completely kill off its enemy some of the time. -- Ting Hsu UUCP ...pur-ee!ajz@mentor.cc.purdue.edu ARPA ajz@mentor.cc.purdue.edu FAX 1 317 494 0566 BITNET xajz@PURCCVM Subject: Re: KotH suggestions From: wms@iwarp.intel.com (William Shubert) Date: 9 Dec 91 17:39:22 GMT Message-ID: <1991Dec9.173922.3135@iWarp.intel.com> T. Tim Hse has suggested some sort of way to find out the algorithms of opponents. I agree that this would be nice. He says everybody below the top ten should become public domain...I disagree; I refuse to make public somebody else's code. So here's a compromise: From now on I'll occasionally glance through any new programs submitted and look for ";summary" comment lines, and by hand (or maybe I'll write a shell script to do it) I'll pull those out and post them with the tournament results. If you've already submitted a program, you can re-submit it with the ";summary" bit. You may notice that in the results posting I included the length (in instructions) of all programs submitted. Also several people have said they want their programs instantly to be run against the current "hill". OK, I'll do it. It'll take some coding, though, so it may be a week or so. When I do this any programs NOT in the top ten will be immediately dropped from the list. T. Tim Hse (ajz@mentor.cc.purdue.edu) also said: >One more thing. I ran Leech against XTC (either the 1990 contest winner >or else a very high placer) and it lost hands down with XTC getting a 5-2-3 >record against it. The ties only occurred because XTC has a bad habit of >not being able to completely kill off its enemy some of the time. Great! If you have the code...send it in the KotH! Actually, several programs beat Leech regularly. Slowdown1 beat it 9 out of 10. Sonic Kobold beat it 8 out of 10. Influenza (essentially a two-liner) beat it 9 out of 10 times. The only reason Leech ended up 3rd was because I beat a bunch of larger programs 10 out of 10 times. -Bill (wms@iwarp.intel.com) Subject: Re: KotH suggestions From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 9 Dec 91 20:10:57 GMT Message-ID: <1991Dec9.201057.25310@vuse.vanderbilt.edu> In article <1991Dec9.173922.3135@iWarp.intel.com> wms@iwarp.intel.com (William Shubert) writes: >10. Sonic Kobold beat it 8 out of 10. Influenza (essentially a two-liner) >beat it 9 out of 10 times. The only reason Leech ended up 3rd was because I >beat a bunch of larger programs 10 out of 10 times. > -Bill (wms@iwarp.intel.com) Am I the only one to feel deeply frustrated about this? The larger (and mostly more "sophisticated") programs are overrun by brain-less two-liners, simply because the former represent a larger target. Sure hope the next standard includes something that encourages intelligent programming. Pardon the outburst, Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: 2D Core War From: tp1l+@andrew.cmu.edu (Thomas W. Pope) Date: 10 Dec 91 02:11:38 GMT Message-ID: Instead of using the parallel stream idea of the core, what if we move back to a 2D plane. The traditional vector notation could be used to represent any address or offset. In traditional Core War, the execution flow is linear by default, unless specified by the current instruction, but in 2D we have a choice of 8 directions for the flow. What if, instead of making the flow constant, we allowed the program to change it at will? Using the standard 'compass' we have: 7 8 9 [-1,-1] [ 0,-1] [ 1,-1] \ | / \ | / \|/ \ | / 4--+--6 or, with vectors: [-1, 0]-- + --[ 1, 0] /|\ / | \ / | \ / | \ 1 2 3 [-1, 1] [ 0, 1] [ 1, 1] assuming that the upper left corner of the grid is 0,0 So, let's assume that the execution stream starts in the [1,0] direction, looping when the x counter is out of bounds. Then, the command: MOVE [0,0] [1,0] would be an effective IMP in the current row. Now, let's introduce a new command, TURN. The syntax would be: TURN [direction] where direction is one of the vector directions above. From that point on, program execution should follow the path specified with the TURN command. An effective imp travelling in the [1,1] direction could be created with the following code: TURN [1,1] ---------------- ---------------- ---------------- -------------- MOVE [0,0] [1,1] ---------------- ---------------- -------------- ---------------- ------(1)------- ---------------- First the turn command is encountered, then execution proceeds to the move command. The location specified by (1) is loaded with the move command and execution jumps to it. With this implementation, you could have a program that generated (with good use of split and turn) imps that moved in all 8 cardinal directions. This also allows for arbitrary shaped programs spreading in many different directions. One comment, the turn command should change execution direction only in the current process. To operationally define what I ean by process, the split command creates a new process when it is executed. Now for the comments stage... There is one problem with this implementation, it partially defeats the spirit of Core War. Actually, any 2D implementation other than parallel streams (which is actually 1 1/2D) will do the same. My point is as follows: Core Wars is a linear based game, with strong definitions of front and back. A program (primarily) needs to worry about attack from addresses less than its location. It's much easier to make an imp than a reverse-imp. A subset of my implementation would be a linear core, with the option to flip execution direction in a process, thus allowing a program to split off a reverse imp. This would change program design quite a bit, as you now have to worry about imps from the front and back (and similar programs) Unforunatly, when we move into 2D we lose an easy definition of what is forward and what is backward. Maybe the subset {8, 9, 6, 3, 2} of the cardinal directions could be considered forward, and thus possible execution flows, while the others would be considered backward. I guess what I'm trying to say is that adding a dimension to Core Wars requires some serious re-evaluation of how we all approach the actual programming. 2D Core Wars will be more than just a superset of the game, it will be a new game entirely... ...just my $.0000000000000000000002 +-----------------------------+------------------------------------------+ |****** Thomas W. Pope *******|_/~~~~~~~~~\__/~\_________/~\__/~~~~~~~\__| |Internet: tp1l@andrew.cmu.edu|_____/~\_______/~\_______/~\___/~\____/~\_| +-----------------------------+_____/~\________/~\_/~\_/~\____/~~~~~~~\__| |All opinions are Mine! |_____/~\_________/~\/~\/~\_____/~\________| |But... For a small fee... |_____/~\__________/~~~~~~\_____/~\________| +-----------------------------+------------------------------------------+ Subject: Re: KotH suggestions From: fraserc@dcs.glasgow.ac.uk (Campbell Fraser) Date: 10 Dec 91 10:36:03 GMT Message-ID: <1991Dec10.103603.23219@dcs.glasgow.ac.uk> In article 101 Stefan somebody writes >In article <1991Dec9.173922.3135@iWarp.intel.com> wms@iwarp.intel.com (William >Shubert) writes: >>Actually, several programs beat Leech regularly. Slowdown1 beat it 9 out of >>10. Sonic Kobold beat it 8 out of 10. Influenza (essentially a two-liner) >>beat it 9 out of 10 times. The only reason Leech ended up 3rd was because I >>beat a bunch of larger programs 10 out of 10 times. >> -Bill (wms@iwarp.intel.com) >Am I the only one to feel deeply frustrated about this? The larger (and >mostly more "sophisticated") programs are overrun by brain-less two-liners, >simply because the former represent a larger target. Sure hope the next >standard includes something that encourages intelligent programming. >Pardon the outburst, Stefan I doubt if you are as frustrated as I am. In Core Wars '86 standard it was far easier to write large and sophisticated programs which would not lose to small sophisticated programs never mind brain-less two liners. I had a whole suite of programs with lengths ranging from 100-300 lines in length which beat everything from dwarf/dervish/7 League Boot (as my friend named his) to programs in the nature of XTC but far superior (written by another friend). They absolutely do not convert easily to '88 standard. Incidentally, I'm a newcomer to the '88 standard and all its limitations which support small brain-less programs. Did anybody in the 1990 ICWS tournament use the SLT instruction ? If not, why not ? It is an immensely powerful instruction, and one I welcome despite the fact that it weakens my large programs. I just don't know, bitch bitch bitch.... -- +------------------------------------------------------------+ | Mail : Campbell Fraser, Department of Computing Science, | | The University, Glasgow G12 8QQ, Scotland, UK. | | e-mail : fraserc@dcs.glasgow.ac.uk | Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: gblock@csd4.csd.uwm.edu (Gregory R Block) Date: Wed, 11 Dec 1991 00:21:18 GMT Message-ID: <1991Dec11.002118.8550@uwm.edu> >From article <91344.16:58:18.291611.DURHAM@ricevm1.rice.edu>, by DURHAM@ricevm1.rice.edu (Mark A. Durham): >Perhaps the simplest thing to encourage large programs and take the >sting out of smaller programs would be to change how time is allocated >to tasks. If additional tasks each got their own cycles this would >remove the "slowness" from large programs. Thus, a program with two >tasks versus a program with a single task would execute as follows: > >A A' B A A' B A A' B . . . >------ ------ ------ > ^ (machine cycle) > >rather than the current situation > >A B A' B A B A' B . . . >--- ---- --- ---- > >I know that I have written several programs that would benefit from >this change. Also, SPL 0 bombs would be rendered virtually impotent. > >MAD This, in my opinion, is the way it should have always been: It's the way it works. It works well, too. When the task is created, it isn't executed until the next "round" giving time for task creation. Once the task is created, it should run as if it was another redcode program, because it is. It's a separate task, not a subroutine or something... I really don't understand WHY ICWS has it defined the way it is. Could someone explain that? Greg -- ---------------------------------------------------------------------------- AmigaDos 2.0, the choice of a nude generation | gblock@csd4.csd.uwm.edu ---------------------------------------------------------------------------- Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 11 Dec 91 01:23:57 GMT Message-ID: <1991Dec11.012357.3950@vuse.vanderbilt.edu> In article <91344.16:58:18.291611.DURHAM@ricevm1.rice.edu> DURHAM@ricevm1.rice.edu (Mark A. Durham) writes: >I know that I have written several programs that would benefit from >this change. Also, SPL 0 bombs would be rendered virtually impotent. > >MAD Somewhere in my shoebox with Core War systems I have one that implements this task switching scheme as an option. It's written by someone in Denmark whose name escapes me, dates back to 87 and is not quite ICWS-86 compliant, but it comes with full C-source (Turbo C?). If there's interest, I'll put it on soda. But this isn't why I hit 'F': In my opinion, allocating time to a program in proportion to the number of tasks it has spawned is a terrible idea. Under the current standard, stationary, single task programs that bomb the Core systematically do very well. With the alternate tasking scheme, MICE- like programs that proliferate without bounds will dominate the game instead. Not a good trade. We've all discussed this to death a few weeks ago, but I think Jon Newman's "address space" (limiting the addressable range of Core) and "descendant count" (bounding the number of tasks a child-task can spawn) extensions are steps in the right direction. This may be common knowledge, but I also find that my large warriors do somewhat better in a large Core, say 32,000. To really make a difference, you'd want it much larger still, but alas not everybody has 20 Megs of RAM to play with :-) -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: cedman@golem.ps.uci.edu (Carl Edman) Date: 11 Dec 91 01:42:53 GMT Message-ID: In article <1991Dec11.002118.8550@uwm.edu> gblock@csd4.csd.uwm.edu (Gregory R Block) writes: From article <91344.16:58:18.291611.DURHAM@ricevm1.rice.edu>, by DURHAM@ricevm1.rice.edu (Mark A. Durham): > I know that I have written several programs that would benefit from > this change. Also, SPL 0 bombs would be rendered virtually impotent. This, in my opinion, is the way it should have always been: It's the way it works. It works well, too. I beg to differ. Unless I'm missing something important here this change seems terribly counter-productive. Consider a program the first 10 instructions of which are SPL 1s (I'm not even using SPL 0s, just to make the counting easier.). Those 10 SPL 1s will have created 1024 tasks in the first 10 cycles, each of the 1024 tasks executing every single cycle. Next put those 1024 tasks into a loop which plasters the entire core with DAT #0s. At 2 cycles/bomb and 1024 tasks, you'll bomb 512 cells every cycle. Given a 8000 cell core, you'll need no more than 16 cycles to completely set to DAT #0 the entire core for a grand total of 26 cycles (less if you were smarter about the bombing, used for SPLs and SPL 0s instead of SPL 1s). There is virtually no defense against a program like that. Corewar would degenerate into a mindless conflict of the speed of process creation. No viable program could stop splitting before reaching the process limit without incuring an enormous disadvantage. In corewar power is processing power. Being able to arbitrarily create more processing power for your side without cost or limit completely destroys the game. Carl Edman Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: gblock@csd4.csd.uwm.edu (Gregory R Block) Date: 11 Dec 91 03:14:01 GMT Message-ID: <1991Dec11.031401.29614@uwm.edu> >From article , by cedman@golem.ps.uci.edu (Carl Edman): > entire core with DAT #0s. At 2 cycles/bomb and 1024 tasks, you'll bomb > 512 cells every cycle. Given a 8000 cell core, you'll need no more > than 16 cycles to completely set to DAT #0 the entire core for a grand > total of 26 cycles (less if you were smarter about the bombing, used > for SPLs and SPL 0s instead of SPL 1s).... Interesting, though deadly. You seem to have left out several safeguarding possibilities, though. > Corewar would degenerate into a mindless conflict of the speed of > process creation. No viable program could stop splitting before > reaching the process limit without incuring an enormous disadvantage. > In corewar power is processing power. Being able to arbitrarily create > more processing power for your side without cost or limit completely > destroys the game. Then again, one could say that only the MAIN task can spawn. That way, it would take far more time to pull something like that off. Getting a REAL task is generally pretty important in letting larger programs have a better chance, IMHO. However, allowing children to have children... ;) I say all children should be neutered. ;D That's one idea, anyways. Another is to put some kind of a respectable ceiling on the number of tasks that may be spawned. There's no reason that it should HAVE to work like Windows. ;) Greg -- ---------------------------------------------------------------------------- AmigaDos 2.0, the choice of a nude generation | gblock@csd4.csd.uwm.edu ---------------------------------------------------------------------------- Subject: Encouraging larger programs From: ajz@mentor.cc.purdue.edu (T. Tim Hsu) Date: 11 Dec 91 03:48:46 GMT Message-ID: <29037@mentor.cc.purdue.edu> I'll explain why the previous suggestion, that all programs share equal time as if they were seperate warriors was probably not used in ICWS. All programs would become divide and conquer programs. For example, an 8 line program that multiplies can potentially fill up the core in 8*log2(8000) = ~100 cycles if it were given 1000 processes. Since SPL's will barely slow it down (unless you hit it early on) now that the ICWS is changed, there's nothing that you can really do to it. That's barely enough time for a 100 line program to execute once. Or better yet, I'd build a DWARF clone that SPL to ITSELF. This 4 line program could bomb 1/4 of core in 4*log2(2000) = ~45 cycles, and it's an incredibly small target to boot. Since the number of processes has now become the key factor in the survival of programs, I would expect that ALL programs would multiply to fill up their entire alotted processes, at least initally. Before I make a suggestion, I'll just state that I also don't agree with the PCT statement much. It would seem to think that the ideal program under this environment would be a VERY small SPL bombing program complimented by a PCTing program. What it would do is initially split off a program whose sole job is to PCT itself and it's sister "attack" program. This sister attack program would then decrement the targeted location in core (in an attempt to remove any PCT's there - decrement, since decrementing a location is very simple and usually does not waste an extra instruction) and then it would write an SPL there. Any SPL bomber would work, but smaller ones could more easily be PCTed. ---------- My suggestion is to simulate a cache memory. Well, not quite a cache memory, but pretty close. What would happen is that every time the program accesses a memory location, be it a write, read, or fetch operation, that memory location is then converted into fast ram. Next we allote the program say a maximum of 100 locations that can be fast ram at any given time. When the program starts to read/write to more than this maximum number, the least recently accessed "fast" ram location that the program used now gets converted back into slow ram. Other things I would do are..... 0) I would make the slow ram operate 10 times slower than the fast ram. Thus, at each clock cycle, you could execute 1 instruction that was in the "cache" or 1/10 of an instruction in the "main memory". 1) Initially make the fast ram occupy the same space as the program. 2) Allow a command to convert contiguous blocks of memory to slow ram or fast ram (maybe, at most, 10 locations at a time). This is so that routines that copy themselves out of harms way can do so in a reasonable amount of time. It also allows for programs to do create their own replacement algorithms instead of relying on the LRU (least recently used) algorithm. 3) Given two warriors A and B in the core, warrior A will percieve warrior B's fast ram locations as slow ram locations. That is, a given warrior only perceives its own fast ram locations. 4) Although all program can SPL, the additional copies do NOT increase the available fast ram that the program receives. Therefore, programs like Mice get only 100 locations total of fast ram even though it could have 60+ processes running around. This seems to reward intelligence pretty well, I think. I would imagine that the standard attack routine would now be a convert slow->fast ram on 8 locations, examine some of those locations for a program, blanket the area with SPL if there is a program there, go on if there isn't. Likewise, your program could blanket an empty area with bogus commands in hopes that your opponent will mistake the bogus commands for your program, thus potentially buying you some time while it SPLs those locations. If you were even more ingenious, you could write 2 programs. The first would only do coversions from slow->fast ram while the other would examine those locations. This way, the slow ram access and the decision making routines could be done almost in parallel. Since all instructions are 2 opcode instructions, my last suggestion would be for a way to determine what opcode A was and what the instruction was. That way, an intelligent program could deterimine that a SPL bomb occurred and fix it, or better yet, hunt down a program by following it's JMP bomb back to its source. This is getting long winded, so I'll stop my rambling here for the night... -- Ting Hsu UUCP ...pur-ee!ajz@mentor.cc.purdue.edu ARPA ajz@mentor.cc.purdue.edu FAX 1 317 494 0566 BITNET xajz@PURCCVM Subject: Re: Encouraging larger programs From: snewman@Neon.Stanford.EDU (Steven Newman) Date: Wed, 11 Dec 1991 05:45:10 GMT Message-ID: <1991Dec11.054510.4009@CSD-NewsHost.Stanford.EDU> First of all, let me throw my vote in against the "unlimited allocation of processor time" idea. It would absolutely encourage mindless SPL 0 snarfing of tasks until the process limit was reached. This would not benefit subtle programming. As far as I'm concerned, the main problem with writing sophisticated programs - in particular, multitasking programs - is that they're so vulnerable to vampire or SPL 0-style attacks. In effect, under ICWS'88, splitting off a subprocess is just granting a vampire the right to allocate jillions of processes in your time slot. The more independent processes you create, the more vulnerable you are. Setting a low process limit doesn't do much to alleviate this, although if the limit were low enough (say 64) you could write your program to soak up the entire limit when it starts - but this is just a hack and doesn't address the real problem. The process count modification that has been proposed is one way to address this problem, but it strikes me as being a bit of a hack as well. The basic problem, it seems to me, is that any minor little subprocess has the right to replicate itself and take away most of the time slots from the rest of that program. This is just plain wierd. It would make more sense if when a process split, each fork only got 50% of the time that would have been allocated to the original process, rather than giving each fork a full share in the global pool (as is currently done). So the first SPL that a program executed would result in two processes, each getting 50% of the time slices. If one of these processes then forks, you would have two processes getting 25% of the time (each) and one getting 50% of the time. This scheme was described in a bit more detail a few weeks ago (I forget who posted it). Some questions then arise - e.g. when a subprocess dies, is its time slice gone forever, or is a proportional share added to each of the surviving processes of that program? Also, you could implement "disproportionate forks", where one subprocess got a larger share of the forking process' time than the other, but that's probably making things more complex than necessary. Under this scheme, programs like the vampire would still be useful, but they would lose their overwhelming advantage over any multitasking program. In fact, more sophisticated types of vampires would probably become dominant, because it would be almost impossible to kill a widely dispersed replicating program in any way except to gradually steal away more and more of its processes, until finally you have slowed it down to the point where you can kill it before it can replicate any more. As far as other proposals to encourage sophisticated programs, I very much like the address space limitation proposal. It makes Core Wars much more "exploratory", i.e. programs have to go looking around in person, as it were, to find the enemy, instead of just shooting out bombs from some remote hideaway. I would like to play with extremely small address space limits, e.g. as small as 128 or so. This would make it feasible for a program to "defend territory" by viciously bombing a buffer zone too wide to be crossed directly. One note: it is important for programs to be able to do arithmetic using numbers larger than the address space limit, so that they can keep track of where they've been and where they're going. Ting Hsu's suggestion of "cache memory" to make it more expensive for programs to go bombing around is interesting, but maybe a bit complex. I suspect that the address space limitation is a simpler way of getting the same result. A compromise might be to leave off the address space limitation, but to make writes (and possibly reads) progressively more expensive as the range increased. Finally, some way for programs to analyze the contents of memory (i.e. to read all 5 fields of a cell, not just the B-value field) would definitely be nice. - Steve Newman (snewman@cs.stanford.edu) Subject: Very Large Programs From: dxb105@csc1.anu.edu.au Date: 11 Dec 91 05:54:04 GMT Message-ID: <1991Dec11.165404.129@csc1.anu.edu.au> I find the suggestions of how to encourage larger programs rather ironic. I submitted a program to both the CoreWars competitions and had it knocked back as too long. Admittedly it wasn't particularly smart, but it was large. :-) (The program, "Horde", was just an array of 64 dwarfs, with a binary "tree" of SPL commands to boot it up. There's a lot you can do with Hordes, some can be DAT bombers, some SPL bombers, some ("Chekas") can correct particular common forms of damage in the rest of the Horde, others can methodically erase memory) ------------------------------------------------------------------------------ David Bofinger AARNet: dxb105@phys.anu.edu.au Snail: Dept. of Theoretical Physics, RSPhysS, ANU, ACT, 2601 ------------------------------------------------------------------------------ Subject: Re: Encouraging larger programs From: kwhyte@dickson.uchicago.edu (Kevin Whyte) Date: 11 Dec 91 06:49:01 GMT Message-ID: <1991Dec11.064901.15540@midway.uchicago.edu> It seems people (myself included) are falling into the trap that MAD predicted. Everybody has their own ideas on what is the best way to encourage more sophisticated behavior. Ok, it seems to me that there is almost universal agreement about: a> core sizes should be larger b> some sort of restriction on read/write/jump range should be implemented ( caches, paging, direct range limit, etc) c> spl should be somehow changed (descent count, fractional allocation to children, MAD's suggestion, etc) So why don't we decide exactly what we want, and try it. I mean, people should think hard about the proposals they have seen on the above three points, and whatever ideas they may have, and post (or if prefered send me mail, as a "vote") Then authors of Corewar programs can include these features and upload the programs to soda. Then we can get on with writing warriors under the new rules, and can exchange them over the net, to see how the rules work out. Kevin Subject: Implementing a memory-distance measure From: n8243274@henson.cc.wwu.edu (steven l. odegard) Date: 11 Dec 91 08:12:17 GMT Message-ID: <1991Dec11.081217.27592@henson.cc.wwu.edu> In light of suggestions for core-war, the following will implement a 'speed of light' for core programs, and incorporate a number of other discussions for improvements that have been discussed. ----- Additional addressing mode ----- In addition to pre-decrement indirect, indirect, relative, and immediate addressing modes ( < @ . # ), there will be post-increment indirect ( / ). For an example: MOV /A B The B-operand of the memory at A is fetched and incremented and restored. However the B-operand originally fetched at A is used as a relative address for the left operand of the MOV instruction. The effect of the instruction illustrated is thus: MEM( relative_address( right_operand( relative_address( A ) ) ) ) := MEM( relative_address( B ) ) ; right_operand( relative_address( A ) ) := right_operand( relative_address( A ) ) + 1 ----- The instruction register and other process data is now also is in memory ----- The program counter and other information pertinant to the process running is implemented by a pair of dat statements: * link: dat /ir #link ir: dat #lim #pc _ir_ is the location of the instruction register. _link_ is a link to the next process on the queue, which is maintained as a circular linked list in the core memory. _lim_ is the memory addressing limit explained later, and _pc_ is the location of the currently executing instruction. The process instruction cycle is as follows: MARS maintains the location of *. The left operand of * specifies the next instruction to implement. The right operand specifies the next location for *, (here illustrated is just itself). ----- Memory distance measure ----- A fair method to encourage programs to relocate themselves is to establish a memory distance measure for each step of a running process. The distance measure will be the total of the absolute value of all of the memory refrences made by the interpreted instruction, including the program counter and links. For example, the following program has just finished the IR at _oldlink_, and is now executing the IR at _link_, which refrenses the mov instruction at _instruct_ : oldlink: dat <-1 #3 ; the link to execute is at 3 -- -- * link: dat /4 #14 ; instruction register at 4, next IR at 14 -- -- -- ; 1000 is the allowed limit of this measure ir: dat #1000 #3 ; the instruction to execute is at 3 -- -- instruct: mov <3 /4 ; an example of a complex indirect move -- movefrom: -- ; entire contents of this memory copied from a: dat #0 0 ; location is one cell above (predecrement) b: dat #0 1 ; location of move to is one cell below moveto: -- ; entire contents of this memory copied to -- nextir: -- ; memory location of next instruction register The distance measure of this instruction is the sum of the following distances: 3 -- link from oldlink 4 -- ir from link 3 -- instruct from ir 3 -- a from instruct 1 -- movefrom from a (absolute value) 4 -- b from instruct 1 -- moveto from b ----- 19 -- total distance measure for the instruction executed. ----- Memory distance equalizing ----- MARS will execute the current process until the total of all memory distance measures of the instructions executed by that process exceed those used by the opponent. If the memory distance measure of an instruction would exceed _limit_ (the left-hand operand of _ir_), that instruction is not executed, and the process is credited only with _limit_. If the opponent's first instruction placed a bomb 1000 cells away from its executing program, I'd be able to execute instructions until my distance measure also exceeded about 1000. However if the opponent's bomb was a mov 10000 10000 instruction, and it landed in my program, I would not execute that instruction because the left-hand operand of my _IR_ is not greater than 10000, and I would credited only with 1000, my current limit for memory distance. ----- Inherit protection ----- All of the links and instruction registers I am employing cannot be changed by the opponent process. Conversely, I cannot change any of the links and instruction registers of my opponent. Any attempt to write to a cell so deignated by my opponent would not take effect (though I'd still be credited with the memory distance). Similar considerations apply also to the registers for other processes I own. ----- Semantics ----- The instructions otherwise are the same as for the ICWS-88, but the SPL instruction is modified to specify not the location of the next instruction but the location of the link register for the next instruction. The spawning process must first set up the link and instruction registers. Similarly, the END pseudo-operand specifies not the location of the first instruction to execute, but the location of the link register for the first instruction. If there is no END, then the link and instruction registers are established at the memory locations immediately before the program statements, and are set to point to the first instruction of the program. ----- Example battle program ----- The following program will spawn a process that executes in reverse! MOV 0 -1 ; >a 'revurse imp'; begin reading at _start_. start: DAT /1 #0 ; >link register of the first process. DAT #8000 #1 ; >instruction register of the first process. JMP 4 ; skip past data statements. JMP -4 ; for newly made revurse process, skip data statements. second: DAT <1 #0 ; >link register of the second process. DAT #8000 #-1 ; >instruction register of the second process. ; the instruction is JMP -4 because of predecrement. SPL second ; start up the second process. The link fields are ; set up automatically. MOV 0 1 ; a 'forward imp' END start ; >end of program, start executing at start. This is an interesting battle program. Note that there is no need to modify the link fields unless one wishes to disable all other self-owned processes. Indeed, self-modification of the link fields is usually not possible. This however illustrates the change this new schema has for imps, forward and revurse. As the imps move further and further away from the 'core', they receive progressively more and more memory distance credit, allowing the opponent more and more close-range instructions. ----- Self relocation ----- A possible strategy for self-relocation is to set up a a child process and execute a dat statement, killing the parent. dist: equ -100 ; next process set up -100 from current begin: dat /1 #0 ir: dat #1000 #1 mov /here /there ; djz -1 size ; copy the entire contents of here to there mov pristine ir+dist ; copy a fresh instruction register to there. spl begin+dist ; spawn to the ir of the above statement. size: dat #endg-begin ; now quit; >number of instructions to move. here: dat #begin there: dat #begin+dist pristine: dat #1000 #1 ; pristine instruction to move endg: dat #endg end begin -- S. Lee ODEGARD n82432742@henson.cc.wwu.edu Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: l69@nikhefh.nikhef.nl (CHEAF/Sterrenkunde) Date: 11 Dec 91 12:25:16 GMT Message-ID: <1459@nikhefh.nikhef.nl> In article <91344.16:58:18.291611.DURHAM@ricevm1.rice.edu> DURHAM@ricevm1.rice.edu (Mark A. Durham) writes: >I know that I have written several programs that would benefit from >this change. Also, SPL 0 bombs would be rendered virtually impotent. > >MAD I'm not really a redcode expert, but I know that you can write programs that are immune for SPL 0 bombs. A program that makes a copy of itself and then repairs itself can work very nicely (provided the size of the core is large enough). Alan. Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: cedman@golem.ps.uci.edu (Carl Edman) Date: 11 Dec 91 17:39:24 GMT Message-ID: In article <1991Dec11.031401.29614@uwm.edu> gblock@csd4.csd.uwm.edu (Gregory R Block) writes: From article , by cedman@golem.ps.uci.edu (Carl Edman): > Corewar would degenerate into a mindless conflict of the speed of > process creation. No viable program could stop splitting before > reaching the process limit without incuring an enormous disadvantage. Then again, one could say that only the MAIN task can spawn.... That would be slightly less catastrophal. But under such a rule every single of my programs would start like this: start: SPL real SPL real SPL real SPL real SPL real SPL real SPL real SPL real SPL real SPL real JMP start real: real program Under such a rule I would need about 100 cycles to create 100 tasks and about the same time to completely pave the core with DAT #0 the core with those 100 tasks. Even if it should miss something in the first loop, the second loop will execute twice as fast, the third three times as fast a.s.o. No enemy program can defend itself against such an onslaught. I still hold that CPU is and should be precious. Giving it away for free destroys the game. Carl Edman Subject: Re: KotH suggestions From: pwh@bradley.bradley.edu (Pete Hartman) Date: 11 Dec 91 19:24:49 GMT Message-ID: <1991Dec11.192449.13043@bradley.bradley.edu> In <1991Dec9.201057.25310@vuse.vanderbilt.edu> stst@vuse.vanderbilt.edu (Stefan Strack) writes: >In article <1991Dec9.173922.3135@iWarp.intel.com> wms@iwarp.intel.com (William Shubert) writes: >>Actually, several programs beat Leech regularly. Slowdown1 beat it 9 out of >>10. Sonic Kobold beat it 8 out of 10. Influenza (essentially a two-liner) >>beat it 9 out of 10 times. The only reason Leech ended up 3rd was because I >>beat a bunch of larger programs 10 out of 10 times. >Am I the only one to feel deeply frustrated about this? The larger (and >mostly more "sophisticated") programs are overrun by brain-less two-liners, >simply because the former represent a larger target. Sure hope the next >standard includes something that encourages intelligent programming. But the current standard encourages efficient programming, which some would consider the greater good. -- Pete Hartman Bradley University pwh@bradley.bradley.edu The real question for 1988 is whether we're going to go forward to tomorrow or past to the -- to the back! Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: jcours@kaa.eng.ohio-state.edu (Jeffrey Cours) Date: 11 Dec 91 20:33:41 GMT Message-ID: <1991Dec11.203341.19118@ee.eng.ohio-state.edu> I'm afraid I'm a little out of date on the current Core War standard (I'm having trouble getting the recent version of Core War I just FTP'd down to my Mac to un-archive properly), but last night an idea for a program design occurred to me and brought a question with it. First, the question: is there a way for a program to tell how many "friendly" processes it or its children have active at any given time? (In this case, I'm defining a friendly process to be one that either the program started via SPL or one of its children started the same way). My idea was to have a program that split itself into several sub-programs, each one spaced around the core at equal intervals. Each sub-program is responsible for bombing its own section of the core and for updating a flag in the next sub-program in the chain. If sub-program i notices that sub-program i-1 hasn't updated i's flag, i stops bombing, rebuilds i-1, and splits off to it. Ideally, i should also be able to stop the old process i-1 from executing, regardless of where it's gotten in the core. This scheme would of course require adding an instruction that lets any process arbitrarily kill off any other friendly process, but it could be more resistant to vampires and it might lead to larger, more fault-tolerant programs since each section of the program could check all the others and kill any process that started to go haywire. Thoughts? Ideas? Suggestions? Thanks, Jeff Subject: Trial tournament under address range limit (was Re: encouraging ..) From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: Wed, 11 Dec 1991 22:57:57 GMT Message-ID: <1991Dec11.225757.14385@vuse.vanderbilt.edu> In article <1991Dec11.064901.15540@midway.uchicago.edu> kwhyte@dickson.uchicago.edu (Kevin Whyte) writes: >Ok, it seems to me that there is almost universal agreement about: > > a> core sizes should be larger > b> some sort of restriction on read/write/jump range should > be implemented ( caches, paging, direct range limit, etc) > c> spl should be somehow changed (descent count, fractional > allocation to children, MAD's suggestion, etc) > >So why don't we decide exactly what we want, and try it... A lot of the proposed extensions *have* already been implemented. a> most every Core War system allows a Core larger that 8K, although 32K seems to be the ceiling in current implementations. b> at least two systems (Core! by Jon Newman and CoreWar Pro by myself) implement the address space limitation. Since the idea is quite old (didn't A.K.Dewdney in fact mention it himself?) and the modification so trivial to implement, I strongly suspect there are more out there. c> the same two systems mentioned above also implement descendant count. And Kevin seems to be working on "fractional time-slice allocation". Instead of continuing the debate on speculative grounds, I think it's time for a field test. None of us can truthfully say they understand fully what implications their proposed extension will have on programming strategy. So let's stop talking for a moment and start coding some warriors. I'm proposing a TRIAL TOURNAMENT UNDER ADDRESS SPACE LIMITATION There appears to be some agreement that some form of address space restriction (be it straight field normalization, or some more complicated paging/ streaming scheme) is desirable, since it encourages mobility. Let's start with field normalization, because it doesn't change Redcode syntax, and because there are already implementations of it for the Mac and PC (virtually any MARS can be made to support the address space limit by adding a single line of code). It can be expected that the experience gained from this tournament will be applicable to the more complicated paging schemes as well. If there's enough input, I will hold an informal, trial tournament on my home PC using these parameters: Coresize: 32000 Address space: 4000 (fields normalized to -2000..1999) Task limit: 1000 Max. cycles: 100000 The tournament will be held middle to end of next week. If you'd like to contribute a warrior, send email by Thursday evening to stst@vuse.vanderbilt.edu. If there are more than 10 contributors, the tournament will take place. The code of the top 5 or so contestants will be posted, and we can take this as a starting point for further discussions. I'll post tomorrow if there was enough interest. Deadline for the actual submissions will be about a week from now. -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: KotH, limited addressing From: wms@iwarp.intel.com (William Shubert) Date: 12 Dec 91 00:55:28 GMT Message-ID: <1991Dec12.005528.16954@iWarp.intel.com> KotH blew up again. Sorry to everybody who got mail. I thought I had fixed it, I ran some tests, it seemed to work OK, I ran the tournament, it started dropping the wrong scores again. I have two choices: 1) Work on KotH. Get it in shape as soon as possible. 2) Re-install the old version. Work on KotH some more. Which would people prefer? About limited addressing: I personally dislike this idea, for one reason. I love Corewar because there are so many possible attack strategies. If you limit your addressing range, it FORCE every competitive program to be mobile. A program which just sits will only win if it's opponents impale themselves against it. Also, small programs will be total non-winners. I think that it would be nice if small programs could win, but if more complex programs could beat them. If the SPL -> the children share the parent's processing time idea is implemented, a Dwarf would STILL be a viable program. However, a program which split into multiple copies would be better because the Dwarf would have to kill all copies. This is true today, but if (under ICWS 88) a program splits it will be almost instantly killed by a Vampire or Slowdown-style program. -Bill (wms@iwarp.intel.com) Subject: Re: Encouraging larger programs From: ebrandt@jarthur.claremont.edu (Eli Brandt) Date: Thu, 12 Dec 1991 04:16:22 GMT Message-ID: <1991Dec12.041622.20898@muddcs.claremont.edu> In article <1991Dec11.064901.15540@midway.uchicago.edu> kwhyte@dickson.uchicago.edu (Kevin Whyte) writes: > a> core sizes should be larger Perhaps there could be a (small!) set of standard cores. People running CW on a 286 box will not be happy with an ICWS-standard size-200000 core, but those who run it on YMP clusters should have a standard large core. Also, it makes a difference whether your coresize is, say, a power of two as opposed to a prime as opposed to a product of small distinct primes. However, we don't want coresize proliferation. Perhaps there could be small: 8192, for backward compatibility medium: in the 30k range large: 100-200k Any comments on desirable number-theoretic properties for coresizes? > b> some sort of restriction on read/write/jump range should > be implemented ( caches, paging, direct range limit, etc) Range limits seems the simplest and most elegant. I think people could agree on this one. > c> spl should be somehow changed (descent count, fractional > allocation to children, MAD's suggestion, etc) This is harder. I like fractional allocation (when a thread dies, you lose its slice), but can advantages to others. What was the MAD SPL? >Kevin Eli ebrandt@jarthur.claremont.edu Subject: KotH is back From: wms@iwarp.intel.com (William Shubert) Date: 12 Dec 91 05:14:59 GMT Message-ID: <1991Dec12.051459.3938@iWarp.intel.com> OK, I fond the bug. I had a mistake in a sed script that treated program #1 and program #10 as the same. Oops. Because so many programs were dropped through the cracks while things were buggy, I cleaned out everything and started again. Please, please, PLEASE re-submit your programs. I got a lot of nifty looking submissions that just got lost when things were broken. Because things have changed, here's what to expect from the new KotH: 1) Submissions - To submit a program, add the line ";redcode" the the VERY BEGINNING of your program. Then add ";name " and ";author " after. Mail this program to "wms@iwarp.intel.com". Please also add a ";strategy" comment. I may pull this out by hand at some date so people can get some idea of how the best programs submitted work. 2) What to expect - Within a few minutes, you should get mail back telling you either that your program compiled correctly and has been entered into the tournament OR that something went wrong. If something goes wrong, an error message describing the problem will appear. In an hour or so, you should get a SECOND piece of mail describing your program's performance against all other programs on the hill. If your program makes it onto the hill, every time somebody submits a new program your will get a report describing how your program did against this new contender. You will also get a complete listing of the top 10 programs at this point. 3) The rules of this game: King of the Hill is full ICWS '88 with these exceptions: A comma is required between argument A and B. Parenthesis are allowed in argument calculations. In addition, the games have the following constants: coresize = 8,000 instructions Max. processes = 8,000 per program If neither program dies within 80,000 cycles a tie is declared. Each program will play every other program 40 times. Ties give 1 point, wins 3 points, and losses zero points. An example submission: ;redcode ;name Dwarf ;author A. K. Dewdney bomb dat #0 dwarf add #4,bomb mov bomb,@bomb jmp dwarf end dwarf Enter! -Bill (wms@iwarp.intel.com) Subject: Re: Bug in MADgic Corewars implementation? From: ajz@mentor.cc.purdue.edu (T. Tim Hsu) Date: 12 Dec 91 06:25:12 GMT Message-ID: <29151@mentor.cc.purdue.edu> In article <1991Dec12.051710.27944@uwm.edu> gblock@csd4.csd.uwm.edu writes: >Well, it doesn't... I just tested it running Imp and Dwarf. Dwarf >lost, and Imp just kept going... and going... and going... but Dwarf >had been trampled. I would have thought that any documentation you read about core wars would have stated that it is theoretically (and realistically) impossible for Imp to win by it's own accord. The only way for Imp to win is if the opposing program overwrites itself. When Imp overwrites a location in which the other program sits upon, the other program will be "converted" into an Imp (figure this one out by yourself, if you can't, then core wars is a bit over your head), but it will not die. On rare occassions Imp will get subverted, but its pretty rare. -- Ting Hsu UUCP ...pur-ee!ajz@mentor.cc.purdue.edu ARPA ajz@mentor.cc.purdue.edu FAX 1 317 494 0566 BITNET xajz@PURCCVM Subject: Re: KotH is back From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 12 Dec 91 06:40:23 GMT Message-ID: <1991Dec12.064023.471@vuse.vanderbilt.edu> In article <1991Dec12.051459.3938@iWarp.intel.com> wms@iwarp.intel.com (William Shubert) writes: > If your program makes it onto the hill, every time somebody submits a new >program your will get a report describing how your program did against this >new contender. You will also get a complete listing of the top 10 programs at >this point. > -Bill (wms@iwarp.intel.com) > I'd find it more challenging if I would only receive listings of programs that my entry was able to beat. After all, part of the fun of tournaments is *not* knowing what your opponent's strategy is. By the way: Great job, Bill. If anything useful came out of r.g.c sofar, it's KotH. -Stefan Subject: Improving the Koth From: S_BLEYER@rzmain.rz.uni-ulm.de (Mike Bleyer) Date: 12 Dec 91 12:41:50 GMT Message-ID: <1991Dec12.124150.9686@wega.rz.uni-ulm.de> I just had an idea about improving CoreWars and preventing the deadly threat from programs bombing with SPL 0 (like mine). If we would introduce a new instruction which could check how many tasks are currently waiting to execute on the same memory cell (the effect of SPL 0), a program could then stop all these processes itself (with a DAT), thus making itself faster again ! That check instruction could be programmed to check for other things as well, e.g. the opcode thats in a cell,... (this would encourage intelligent programs too) Another basic suggestion for a larger variety of progams : Why don't we introduce an auto increment ">" mode, so programs can start at the bottom and bomb up through the core (At the moment, everyone boms down because the code is most efficient). What if someone who has time and is interested and has the necessary equipment (meaning computer power) would run an experimantal King of the Hill where we could test all our new ideas on some common types of programs and see how it works out ? Any volunteers ? Mike -------------------------------------------------------------------------- Mike Bleyer on Internet | Got the chips and enhancements - S_Bleyer@RZMain.RZ.Uni-Ulm.DE | Got the attitude right - Meet Smacks on IRC ! | Got the metal beneath my skin - ------------------------------| I`m chippin' in... (Cyberpunk 2020) Subject: Re: Improving the Koth From: wms@iwarp.intel.com (William Shubert) Date: 12 Dec 91 17:42:32 GMT Message-ID: <1991Dec12.174232.14731@iWarp.intel.com> Mike Bleyer posted: > What if someone who has time and is interested and has the necessary > equipment (meaning computer power) would run an experimantal King of the > Hill where we could test all our new ideas on some common types of programs > and see how it works out ? > Any volunteers ? Actually, this was my intention when I created KotH. First, let me say thanks to everybody for bearing with me during the bugs; things are going great now, a bunch of new submissions are in, etc. Second, I plan on (soon) making it possible to submit "redcode experimental" program by having the first line be: ;redcode-x These will be entered into a SECOND tournament that will go on simultaneously and will be a modified version of corewar. Since KotH is essentially stable now, I guess it's time to decide what kind of experiment to try first. Somebody else is already offering to try out a tournament based on having an addressing mode smaller than the core size. That's great; I'm not too interested in that anyway (for reasons I posted in an earlier message). So pretty much here's my suggestions (in the order of how much I like them): 1. Have the children of a SPL share the parent's CPU time to make larger programs less vulnerable. 2. Add ">" addressing mode (POST-increment) for symmetry (plus now with "<" and ">" you can build a stack!) 3. Fill out the comparison tests - right now we have "a == b" and "a < b"; why just these two? I'd like a full set of "a != b", "a > b", "a <= b", and "a >= b". This would mean more instructions, but they would fit in with the rest and make the assembly more orthogonal. I'll take any mail advice you want to send me. Tell me what you want to try out and why; please do it through mail. I'll try to make the change that is most wanted. -Bill (wms@iwarp.intel.com) PS - Right now people who submit two similar programs get them both on the KotH top ten. Should I remove any copies? The top 10 list right now: W/ L/ T Name Score 269/ 80/ 91 slowdown1 898 277/102/ 61 slowdown2 892 250/ 92/ 98 Leech 1.1 848 250/119/ 71 XTC 821 174/111/155 Dwarf 677 188/195/ 57 Schizo 621 125/227/ 88 WIMPer 463 108/236/ 96 DAC (Divide And Conquer) 420 11/ 98/331 Imp 364 47/233/160 WIMPer 301 The #1 program, slowdown1 (by Mike Bleyer) was kind enough to have some strategy lines. Here they are: ;strategy Slowdown1's strategy is: bomb with splits,(make 'em slow) ;strategy bomb with dats, (everyone should be dead by now) ;strategy start a dwarf (to tie in case someone survived) Subject: More instructions/addressing modes From: ajz@mentor.cc.purdue.edu (T. Hsu) Date: 12 Dec 91 23:16:34 GMT Message-ID: <29208@mentor.cc.purdue.edu> First let me say that we do not really need all the comparison statements, we would only need..... comparison current command proposed command A == B CMP A B ------- A < B SLT A B ------- A <= B ------- SLE A B A != B ------- SNE A B This is because (A < B) is the same as (B > A) and likewise (A <= B) is the same as (B >= A), thus the only reason the greater than comparison would be needed is to allow for tighter code in a small percentage of programs. I would also like to see > be used as a post-increment indicator. -- Ting Hsu UUCP ...pur-ee!ajz@mentor.cc.purdue.edu ARPA ajz@mentor.cc.purdue.edu FAX 1 317 494 0566 BITNET xajz@PURCCVM Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: markc@smsc.sony.com (Mark Corscadden) Date: 13 Dec 91 00:41:37 GMT Message-ID: <1991Dec13.004137.29616@smsc.sony.com> In article cedman@golem.ps.uci.edu (Carl Edman) writes: >... >In corewar power is processing power. Being able to arbitrarily create >more processing power for your side without cost or limit completely >destroys the game. > > Carl Edman How about assigning an internal "process power" register to each executing process? The initial contestant processes would each start with, say, 100 "points" in their process power register (PPR). When you fork a process, the PPR value at the time of the fork is split between parent and child. If you wanted to get complicated you could allow the parent to control how much of the PPR is given to the child. Don't allow forking once the PPR value is down to 1. This way you severly limit the new processing power that can be created just by forking. An unrelated effect would be that you can only be killed at most 100 times before you are dead for sure. Mark Corscadden markc@smsc.sony.com work: (408)944-4086 Subject: Re: More instructions/addressing modes From: blojo@soda.berkeley.edu (Jon Blow) Date: 13 Dec 1991 05:30:52 GMT Message-ID: ajz@mentor.cc.purdue.edu writes: > comparison current command proposed command > A == B CMP A B ------- > A < B SLT A B ------- > A <= B ------- SLE A B > A != B ------- SNE A B If we're going to have a suite of commands such as this, we might as well rename CMP to something more homogenous like SEQ. CMP was created before there were any other comparison operators. I like the idea of postincrement indirect. Amazing nobody thought of it before. (Preincrement indirect had been suggested a few times, as I recall.) I strongly dislike the idea of finagling the amount of processor time newly-spawned processes get. People have been suggesting these sorts of schemes for a long time and they're all just *too darn complicated*, and it's still doubtful that they'll actually make Redcode more interesting. Redcode should stay simple. I fail to understand why so many people think that increasing the size of the core will be the panacea of all our woes. As long as Redcode stays the way it is, it will be faster to bomb blindly than to be intelligent about one's surroundings. If it's faster to blindly bomb 8000 locations than to survey them, it's going to be just as faster to blindly bomb 800000 locations. Except, of course, that battles would take much longer to complete, which is something I'm sure we all want./ I think it would be nice if the core were a little larger. It would be even nicer if it were of an unpredictable size. Making it bigger, though, is not going to solve any concrete problems. We really need to think intelligently about what the changes we propose will do to the system. There are some changes that I think make Redcode more interesting or conceptually "pure", like INV. I like INV a lot, but I would also hesitate to suggest it become part of the standard, because I think it will make intelligent programs even harder to write. While I'm on about changes to Redcode, a couple things I'd like to see: * ADD and SUB should add and subtract entire instructions, not just their B fields. I've always thought that restricting their effects to B fields was fairly cheezy, and besides, it's easy enough to create an instruction which is zero except for its B-field, even if DAT is not specified to be opcode 0. * I'd like to see an implementation of some sort of range-restriction as has been discussed quite often. Preferably a simple one, wherein reads are unrestricted and writes are subject to an access horizon which is significantly smaller than the core size (say, CORESIZ/16 or so.) -Jon Subject: MICE From: ajz@mentor.cc.purdue.edu (T. Tim Hsu) Date: 13 Dec 91 07:02:07 GMT Message-ID: <29262@mentor.cc.purdue.edu> Just to make sure that people out there have it, here is MICE, the program that won the 1986 ICWST. It made a meger 336 points out of 1200 total in the KoTH which is a good sign that core wars programs have progressed beyond 1986. This program just multiplies itself quicking throughout the entire core. ;redcode ;name MICE ;author Chip Wendell ; ; MICE ; by: ; Chip Wendell ; ; ; org org ptr dat #0 , #0 start mov #12 , ptr loop mov @ptr , This is FERRET, the winner of the 1987 ICWST. It made a meger 381 points out of 1200 in the KoTH. A good sign that current core wars programs have progressed further than 1987. It examines the core for possible instructions. If it finds one, it places an SPL 0 bomb there. After a while, it gives up on looking for another program and just bombs the entire core with DATs, hoping to kill off any SPLed programs before it kills itself off. ;redcode ;name FERRET ;author Robert Reed III ; ; 2ND ICWS COMPETITION ENTRY ; ; NAME : FERRET ; ; PROGRAMMER : Robert Reed III, Windsor Locks, CN ; ; ORG START START MOV #4908,B F CMP This is Cowboy, the 1988 winner of the ICWST. It makes about 480 points out of 1320 in the KoTH and is currently ranked 8th place. It's typical score is 90/140/210. The important score to notice here is the 210 ties that it has. The rest of the programs in the KoTH typically have less than 40 ties. This goes to show that the other programs in the KoTH are offensive programs whose only defense is their small size, while Cowboy has an active defense. Cowboy is a 50 instruction, two part program. The first part of it is that of a SPL bomber (actually, it bombs the core with JMPs to an SPL routine). The second part of the program is defensive. This second part builds two "fences" which it then checks for continuity. The moment one of those fences is breached, it looks for a location in memory and then proceeds to copy itself to that location to start all over again. Although I am thoroughly pleased that Cowboy made the KoTH since it suggests that large programs are worthwhile, it does say a few things about the contestants since Cowboy is a 3 year old program. ;redcode ;name Cowboy ;author Eugene P. Lilitko ; ;Cowboy ;by Eugene P. Lilitko ;Union of Soviet Socialist Republics ; ;The snare for the opponent's processes. ;Bison commits suicide when all 64 processes are captured. ; FIRE DAT # FIRE BEG DAT # BEG FENCE MOV SUCCESS , SWITCH DEMON SUB # 1 , BISON HELP SPL DEMON BOMBING MOV FIRE , < FIRE JMN HELP , BISON MOV BOMB , HELP BOMB DAT # BOMB BISON DAT # 64 COUNT JMP FENCE ;Welcome to the snare! ; WELLC1 JMP < WELLC1 WELLC2 JMP @ WELLC2 ;The main code. Traps are set, inviting the opponent to jump ;into the snare. When the bison are captured, SWITCH is changed ;to the instructions of SUCCESS. ; START MOV REST , SWITCH GBOMB MOV # 575 , FIRECNT MOV # 64 , BISON SPL RADAR CONT MOV # 4098 , WELLC1 MOV # -4099 , WELLC2 LOOP MOV WELLC1 , @ WELLC2 MOV WELLC2 , @ WELLC1 ADD # 7 , WELLC1 SUB # 7 , WELLC2 SWITCH DJN LOOP , FIRECNT ;All right! There are bison in the snare. The captured bison invite free ;bison into the trap. Cowboy must help them! ; NEW MOV BOMB , FIRE MOV BOMB , KILL SHOOT MOV FIRE , < FIRE JMZ SHOOT , KILL FORWARD JMP NEW SUCCESS MOV GBOMB , SUCCESS REST DJN SHOOT , COPY+3 ;The defense process. Build a set of pickets, test for a breach of the ;pickets, and switch to defensive action when the pickets are breached. ;Defense occurs when Cowboy is copied to a new place in memory, and the ;copy begins operating properly. ; RADAR MOV # 638 , FORWARD MOV # -638 , BACK MOV # 25 , COUNT MAKE MOV COUNT , < FORWARD MOV COUNT , < BACK DJN MAKE , COUNT TEST MOV # 638 , FORWARD MOV # -638 , BACK MOV # 25 , COUNT COMPARE CMP < FORWARD , < BACK BACK JMP ALARM KILL DJN COMPARE , COUNT FIRECNT JMP TEST ALARM MOV BOMB , SWITCH MOV # 50 , BEG MOV # 3310 , FORWARD COPY MOV @ BEG , < FORWARD DJN COPY , BEG MOV NEW , BOMBING ADD # 11 , FORWARD FINISH JMP @ FORWARD END START -- Ting Hsu UUCP ...pur-ee!ajz@mentor.cc.purdue.edu ARPA ajz@mentor.cc.purdue.edu FAX 1 317 494 0566 BITNET xajz@PURCCVM Subject: XTC From: ajz@mentor.cc.purdue.edu (T. Hsu) Date: 13 Dec 91 08:16:24 GMT Message-ID: <29266@mentor.cc.purdue.edu> This is XTC, the program that won the 5 year ICWST bout in 1990. From my results that I received last night, it states that XTC is the current KoTH with around 922 points out of 1320. It has a typical score of 306/130/4. XTC is a search and destroy program. It has a 2 instruction search routine with a very wide distance between subsequent searches. Thus, it does a very good job of running systematically through core looking for possible programs. When it finds one, it then blankets that location along with 23 locations around it with SPL -1, and then latter with DATs. Although I expected XTC to do well (even though I didn't enter it in the KoTH), it does say a few things when the net can't top a year old program. Of course, I can't complain much since I'm in the same boat. ; ; Warrior: Ecstacy ; File name: xtc.red ; Tournament: ICWST'90 ; Standard: CWS'88 ; Author: Stefan Roettger / Sandstrasse 3 / W-8525 Uttenreuth / Germany ; ; This warrior was originally designed for core size=8192 but it ; also runs very well with core size mod 4 = 0 (e.g. 8000). ; Although it runs under the 1988 standard there are no changes ; necessary to make it run under 1986 standard. ; The startegy used by XTC is the following: ; The warrior compares every fourth core location to zero by ; incrementing a search pointer by #412. To avoid being hit ; by itself every fourth instruction has a B-Operand equal to ; zero. If a supposed foe is found 23 core cells around this foe ; are set to 'SPL -1 -1' by a simple copy loop. This causes the ; foe to be slowed down quite well but not yet kills him. If all ; spawns have been treated like that they are subsequently killed ; by shooting some deadly 'DAT 0' instructions at them. ; Empirical studies have shown the the warrior XTC by far outruns ; nearly all warriors of ICWST 86 and ICWST 88. For example it ; defeats ferret in 70% and mice in 90% of all cases. ; The reasons for this are: ; -XTC is very small cause of tricky programming ; -XTC's search loop is very very quick ; -The method by which XTC kills foes is highly reliably. ; All this makes XTC my warrior of choice. :-) ; Please start XTC at the label 'loop'. loop add #412 ptr ptr jmz loop trap mov ptr dest cnt mov #23 cnt kill mov @trap With all the recent arguing over small-braindead vs large-intelligent programs I decided to try and write a large program to see if it was possible for a large program to beat a small one. My results are somewhat mixed. Large programs have the disadvantage of being easy to hit (big targets), too big to copy quickly, and slow to execute. In designing this program I chose to "offload" the expense of copying to the opposing warrior, while excuting a small subverting loop. The bonus is, even if the program is damaged it is more likely to be damaged in the copy/bomb routines rather than the scan/subvert simply because they are larger. The effect of this is, the program will go on scanning/subverting only this time, the opposing warrior will die from excuting damaged code. With all these effects, Retrovirus still loses alot. For instance a lucky hit by mice kills it, but I think it kills mice far more often. It kills chang1, commando, raidar, and most of the others in the redcode.tar.Z on soda.bereley.edu. Still, a large program can never fully defend itself against something like mortar simply because the address range is unlimitied. I think address range limitations (CORESIZE/16) will provide a much more interesting game since programs will have to send out scouts on bombing missions. The strain that the unlimited addressing puts on the game can be summarized as follows: start mov b @a add a b mov @a a jmp start a dat #5 b dat #8 (optimized version of mortar) It is very hard to hit this program and it succeeds in beating lots of programs in the first 1000-2000 cycles. I have tried self-repairing programs but they are no good simply because you can't tell whether another one of the error-correcting tasks has died. For instance, task1, task2, and task3 are constantly comparing programs 1, 2, and 3 looking to fix errors. If task3 gets hit, task1 and task2 will detect the damage and fix it, but they have no way of knowing whether task3 died or not. If they SPLit off another task3, and task3 is still running, two copies will be running at the same time which is chaos on non-reentrant code. (unless you implement a stack) If the address range limitation is added to the standard, I hope some environment variables are defined so corewars program can adapt to changing sizes. (e.g. mov #ADDRESS_RANGE ptr, fence mov #0 ptr, djn fence ptr) In fact, I think corewars should get a better preprocessor (EQU is good, but how about somethinglike #ifdef, and more env vars like CORESIZE, __ICWSVERSION__, etc to make programs more portable.) I think limited address ranges will solve the large vs small problem! An address range of +/- 500 on a coresize of 8000 seems adequate to stop programs like mortar from being so offensive. -------------------------------------------------------------------------- ;;Retrovirus v1.0 ;;By Ray Cromwell (rjc@gnu.ai.mit.edu) ;;USA ;;December 1991 ;;Technique: Subvert other program, so that it impstomps and copies ;; our virus for it. ;; (not optimized, yet) ;; Idea came from Tierra (artificial life program), ;; see comp.theory.cell-automata for more details. rnaoffset equ virusrna-memptr exoff equ (833-(endprog-startprog)+(execaddr-dest)) pend equ endprog-ptr ;; ;; Impstomp. Opposing warrior usually executes this. ;; startprog dat #0 impstomp mov #0 startprog imp2 mov #0 startprog mov #0 startprog mov #0 startprog jmp impstomp ;; ;; Constants and pointers ;; jmp0 jmp 0 jmp1 jmp 1 jmp5 jmp 5 jmpvec jmp 600+rnaoffset ;make sure jmp points to "virusrna" routine memptr dat #-600 tmp dat #0 imp mov 0 1 size dat #0 ptr dat #0 dest dat #0 delta dat #0 ;; ;; Startup ;; start mov stopper virusrna ;inialize some constants ; and vectors mov jmp5 tmp ; sub jmp0 tmp ;Find jmp5-jmp0 mov jmp1 delta ; sub jmp0 delta ;Find jmp1-jmp0 ;; ;; Scan loop ;; mainloop cmp dabomb @memptr ;scan for nonzero code jmp subvert ;if non zero, subvert it! s4 sub #5 memptr ;sub 5 from ptr add tmp jmpvec ;add 5 to jmp instruction tjmp jmp mainloop ;loop ;; ;; Bombing after subversion ;; mov njmp tjmp ;fix vector mov memptr delta ;temporary register add #60 delta ;fudge for time-delay bombit cmp @delta tagid ;about to bomb us? jmp bomb ;bomb! sub #(endprog-startprog+6) delta ;skip us! bomb mov dabomb Hey, here's another idea on encouraging "intelligent" programs and preventing small, "dumb" bombers: Make the core size change at random ! My program Slowdown (see below) for example, was specifically designed for a core size of 8000 cells. Any other sizes (especially smaller ones) could have desastrous effects, it could destroy itself... So if the core size would be unpredictable ( in a certain range of course - lets say +-500), programs would have to behave much more intelligent (larger) because they couldn't calculate with the core size to just bomb through the core ! By the way, here's Slowdown1, so everyone can look at it: (real programmers need no comments, the code speaks for itself) ;redcode ;Name slowdown1 ;Author Mike Bleyer start: mov split,@count sub #6 , count jmn start, count bomb: mov count, In article <1991Dec13.004137.29616@smsc.sony.com> markc@smsc.sony.com (Mark Corscadden) writes: In article cedman@golem.ps.uci.edu (Carl Edman) writes: >... >In corewar power is processing power. Being able to arbitrarily create >more processing power for your side without cost or limit completely >destroys the game. > > Carl Edman How about assigning an internal "process power" register to each executing process? The initial contestant processes would each start with, say, 100 "points" in their process power register (PPR). When you fork a process, the PPR value at the time of the fork is split between parent and child. If you wanted to get complicated you could allow the parent to control how much of the PPR is given to the child. Don't allow forking once the PPR value is down to 1. That is an excellent idea. In fact, it is one which has been frequently proposed in this group (by others and me, too) in a slightly different form. :-) What was suggested was that in each split each child gets half the cycles the parent would have. (you really don't need a PPR in the code itself to implement that - there are simpler ways). This would (among other things) make SPL 0 bombs no more effective than DAT #0 bombs. In addition the idea that all effects should be local i.e. that what happens to one process should not affect the speed of another process running at the other end of the core is rather pleasing at least to me. An additional modification which has be proposed frequently together with the above one, is not to redistribute the processing power of a process which has been killed but to completely lose it. Currently killing an enemy process really doesn't do much harm to the enemy unless the process is the last. If it isn't you just cause the other enemy processes to run faster, in effect cancelling out any gain you made by killing the process in the first place. I think there ought to be some penalty for getting one of your processes killed. This way you severly limit the new processing power that can be created just by forking. An unrelated effect would be that you can only be killed at most 100 times before you are dead for sure. Well, I'm not so certain about the number 100. There already are enough arbitrary constants in corewar. I think unlimited splitting ought to be possible. Carl Edman Subject: Re: Retrovirus1.0 and large programs From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: 13 Dec 91 19:02:25 GMT Message-ID: <1991Dec13.190225.5219@descartes.waterloo.edu> In article <21021@life.ai.mit.edu> rjc@hal.gnu.ai.mit.edu (Ray) writes: > I have tried self-repairing programs but they are no good simply because >you can't tell whether another one of the error-correcting tasks >has died... I think it depends on how you approach programming the error detection and corection routines. I like to take the overkill approach. I wrote something called Fist, based somewhat on Five Musketeers (on the R.MArtin version...I'll have to modify and see how it handles ICWS'88). Essentially, you take five copies of a program, and have to compare themselevs to each other. A Fist program will compare itself to another, and if the comparison breaks down, it will check another program. If this second breaks down, it assumes itself is damaged and waits to be killed. If the second comparison works, it replaces the target of the first comparison. And none of this recopy shit. It bombs the entire target area, then copies. I find that while it's a little slow, it tends to be very good in determining what is corrupt. The only problem occurs when the targets of both searchs are corrupt. Then problem occur... -------------------------------------------+--------------------------------- Chris Beauregard | Star Trek is the unix cpbeaure@descartes.waterloo.edu | of television. "If you can't beat 'em, take 'em with ya!" | - Me Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: solman@athena.mit.edu (Jason W Solinsky) Date: 14 Dec 91 19:53:41 GMT Message-ID: <1991Dec14.195341.4547@athena.mit.edu> In article <1991Dec11.002118.8550@uwm.edu>, gblock@csd4.csd.uwm.edu (Gregory R Block) writes: |> From article <91344.16:58:18.291611.DURHAM@ricevm1.rice.edu>, by DURHAM@ricevm1.rice.edu (Mark A. Durham): |> > A A' B A A' B A A' B . . . |> > ------ ------ ------ |> > ^ (machine cycle) |> > |> > rather than the current situation... |> > |> > I know that I have written several programs that would benefit from |> > this change. Also, SPL 0 bombs would be rendered virtually impotent. If this were done then it would be automatically in your favor to create as many tasks as possible. It would take ages for the game to be decided. The way to slow an opponent down to the point at which he would die instantly would be by creating thousands of copies of your self. The winning programs would still have to be small because a program that did non reproduce quickly enough would instantly die. Meanwhile you would have hundreads of thousands of tasks in an 8192 cell core. That simply wouldn't be any fun. Subject: Re: Encouraging larger programs From: solman@athena.mit.edu (Jason W Solinsky) Date: 14 Dec 91 21:17:30 GMT Message-ID: <1991Dec14.211730.6688@athena.mit.edu> I'm glad to see that Mr. Newman agrees with me about how we should split up process time. I have a proposal. Since we can't possibly figure out how good an improvement is without trying it out for a while, why doesn't one of the people running a KOTH program teach his mailhandler to send all entries with a ";modified rules" comment line to a second tournament with different rules. Initially start off with one set of rules and then every two months we could vote on changes. For example, we could initially start off allotting 50% of the parent processes's cycles to each of its daughters. Two months latter, after we've seen what kinds of programs perform best, everbody can submit proposals for changes (That is, everybody who is willing to do the work required to enact the change.) Any proposal with twice as many Yes votes as No votes could be added to the rules. This way, the game would evolve into a form which encourages larger programs, but which is not dominated by a single type of program. At the same time, the tournament with the '88 standard rules would continue. Any thoughs? Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: solman@athena.mit.edu (Jason W Solinsky) Date: 14 Dec 91 22:30:22 GMT Message-ID: <1991Dec14.223022.8604@athena.mit.edu> In article <1459@nikhefh.nikhef.nl>, l69@nikhefh.nikhef.nl (CHEAF/Sterrenkunde) writes: |> I'm not really a redcode expert, but I know that you can write programs |> that are immune for SPL 0 bombs. A program that makes a copy of itself |> and then repairs itself can work very nicely (provided the size of the |> core is large enough). |> |> Alan. HOW? I've thought up thousands of schemes that repair themselves and they don't work because if a single SPL 0 instruction hits you, although your program will be repaired, it will run at such a slow speed that it is useless (unless you catch it right away, but this favors small programs too much and also doesn't survive a vampric drain attack). Repairing the program is not good enough, it can never get caught in the first place. THAT is why I favor changing to SPL command to a 50%-50% process. Subject: Re: Corewars improvements From: wms@iwarp.intel.com (William Shubert) Date: 15 Dec 91 02:05:06 GMT Message-ID: <1991Dec15.020506.10206@iWarp.intel.com> box@sal-sun123.usc.edu (Montgomery Box) said: > Correct me if I'm wrong, but it was my impression that most instructions >in maching code on a computer were 2 bytes long, and that the op-code, and the >operands were combined into 1 word. If this is true, then Corewars is more >correct than your adjustment. Well, look, this is a silly discussion because there are TONS and TONS of different ways computer have their instructions arranged in memory. The VAX had (mostly) 1-byte opcode + at least 1 byte per argument, the x86's have their arguments mushed in with their opcodes sometimes, the 680x0's would have two bytes of opcode plus 1 or 2 bytes per non-register argument (most of the time), and most RISC processors will always fit the whole instruction into one machine word. But this is REALLY REALLY silly because if you want to play Corewar on a realistic machine you can always do so by just using a real machine. -Bill (wms@iwarp.intel.com) Subject: Re: Encouraging larger programs From: snewman@Neon.Stanford.EDU (Steven Newman) Date: Sun, 15 Dec 1991 04:36:29 GMT Message-ID: <1991Dec15.043629.3307@CSD-NewsHost.Stanford.EDU> Jason Solinsky writes: > I had thought that by fractional allocation it was meant that when a > thread dies, its brother or brother's descendants get their fraction > doubled! Are there more people who thought of the idea like [reference > to previous article describing one of the schemes below]? There are at least four ways to implement "fractional allocation", i.e. redefining SPL so that a process cannot steal time from other processes by SPLitting (it just subdivides its own time allocation): 1. When a process dies, its time slice is lost. The total processor time allocated to that side is reduced. 2. When a process dies, its time slice is divided up among the remaining processes (on that side), weighted by how much time they were already receiving. 3. When a process dies, all existing processes (on that side) get an equal share of its time slice (not weighted by how much time they were already receiving). 4. When a process dies, its time slice is given to its sibling process (the process that was created by the same SPL instruction as the dead process). If the sibling has since split, its descendants share the time in some manner. Option (4) appears to be what Mr. Solinsky is suggesting. It has an interesting symmetry, but strikes me as being fairly complicated - exactly how is time allocated if the sibling process has split? What if some of the siblings descendants have died? What if they have all died - do we move back up the ancestor tree, and if so, then how? If a simple solution can be found than this might be worth considering. Option (3) seems contrary to the spirit of the whole thing. The whole idea was to not allow a single thread to get a disproportionate share of the processor time. Options (1) and (2) are both fairly simple. Under option (1), you'd get wars of attrition - parallel programs chipping away at each other, killing off each other's share of the processor a little bit at a time, until eventually the more efficient competitor would have an overwhelming advantage in speed and could kill off the second program before it could repair itself. I think that this could be rather interesting. Under option (2), you couldn't kill a parallel program by chipping away at it; and SPL 0 or vampire programs would lose their deadly effect against parallel programs. To kill a properly written parallel program under option (2), you'd either want to "harvest" the other program's time using a vampire approach, or slowly "paralyze" it with JMP 0 bombs. Either way, the idea is to deal with the enemy one process at a time - but without killing them, because that would just free up the time to be used by other enemy processes. Eventually, you somehow decide that you've captured or paralyzed almost all of the enemy's time, and then switch into a "victory" mode where you bomb core with DAT 0s. Both options (1) and (2) seem to lead to complex and interesting behavior. I'd love a chance to try an experimental KotH using either approach. Comments? - Steve Newman (snewman@cs.stanford.edu) Subject: Re: Encouraging larger programs From: solman@athena.mit.edu (Jason W Solinsky) Date: Sun, 15 Dec 1991 07:03:09 GMT Message-ID: <1991Dec15.070309.23682@athena.mit.edu> In article <1991Dec15.043629.3307@CSD-NewsHost.Stanford.EDU>, snewman@Neon.Stanford.EDU (Steven Newman) writes: |> Jason Solinsky writes: |> |> There are at least four ways to implement "fractional allocation", i.e. |> redefining SPL so that a process cannot steal time from other processes by |> SPLitting (it just subdivides its own time allocation): |> Both options (1) and (2) seem to lead to complex and interesting behavior. |> I'd love a chance to try an experimental KotH using either approach. |> Comments? |> - Steve Newman (snewman@cs.stanford.edu) I'm afraid I don't see how two and four are different unless I missunderstand your definition of "on that side". My method of implementing four would be as follows: The program counters would be arranged in a tree like this: * / \ / \ / \ A(xx0) * / \ / \ / \ * B(x11) / \ / \ / \ D(001) C(101) Originally there was process A which split off process D. Process D split off process B and then process C. First the order of execution would be A then AD then ADAB and finally ADABACAB Each node (represented by the star) points to a LEFTCHILD, RIGHTCHILD, and PARENT and stores DATABIT. Each leaf contains a PROGRAMCOUNTER which is that process's program counter and a pointer to PARENT. Assume that initially all the DATABITs are set to zero. Each time the program encounters a node it looks at the DATABIT. If it is a zero, the program goes to the LEFTCHILD and sets DATABIT to one. If it is a one, the program goes to RIGHTCHILD and sets the DATABIT to zero. If the program encounters a leaf, it executes the instruction pointed to by PROGRAMCOUNTER, updates PROGRAMCOUNTER and goes to the root. Suppose that the current element being examined is pointed to by LOOKHERE. If LOOKHERE points to a leaf (that is the LEFTCHILD of its parent [analagous routines could be executed for a rightchild. to determine which is being dealt with, the program can store the last DATABIT it read])that executes an SPL, A new node is created and pointed to by NEW. (forgive the pascal type notation here but its easier when dealing with pointers) NEW.RIGHTCHILD could be set to the new process and NEW.LEFTCHILD to the old process. NEW.PARENT would be set equal to LOOKHERE.PARENT and finally LOOKHERE.PARENT.LEFTCHILD would be set to NEW. NEW.DATABIT could be set however you want depending on whether you want the new process to execute before the old or visa-versa. LOOKHERE would then be set to the ROOT. If the process pointed to by LOOKHERE (again we assume LOOKHERE = LOOKHERE.PARENT.LEFTCHILD and LOOKHERE.PARENT=LOOKHERE.PARENT.PARENT.LEFTCHILD) executes a DAT 0 then we let LOOKHERE.PARENT.PARENT.LEFTCHILD=LOOKHERE.PARENT.RIGHTCHILD and set LOOKHERE to the root. The whole routine takes no more than eleven or twelve lines of C or Pascal to implement (assuming that the lines executing each command have already been written). Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: f90angu@fy.chalmers.se (Andreas Gunnarsson) Date: 16 Dec 91 06:29:18 GMT Message-ID: <1991Dec16.062918.26854@fy.chalmers.se> In article <1991Dec15.012454.13934@athena.mit.edu> solman@athena.mit.edu (Jason W Solinsky) writes: >In article <1991Dec11.203341.19118@ee.eng.ohio-state.edu>, jcours@kaa.eng.ohio-state.edu (Jeffrey Cours) writes: >|> >|> My idea was to have a program that split itself into >|> several sub-programs, each one spaced around the core at equal intervals. >|> Each sub-program is responsible for bombing its own section of the core and >|> for updating a flag in the next sub-program in the chain. If sub-program i >|> notices that sub-program i-1 hasn't updated i's flag, i stops bombing, >|> rebuilds i-1, and splits off to it. >I thought of the same thing. These programs could get pretty complicated... This is the way my program Schizo works. It splits itself off and bombs while it is checking its twin. If the twin stops working, it rebuilds it. Since it is my first redcode program ever, I got a bit surprised how well it managed on KotH. The drawback of this kind of program is that the coresize must be known to know how big the bomb section of each program is. -- ============================================================================== 73 es 88 de SM7TLS f90angu@fy.chalmers.se Andreas Gunnarsson I won't be able to read email 19-31 december I'm sorry you wasted your time reading this kind of nonsense Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: rjc@geech.gnu.ai.mit.edu (Ray) Date: 16 Dec 91 15:46:51 GMT Message-ID: <1991Dec16.154651.13100@mintaka.lcs.mit.edu> In article <1991Dec16.062918.26854@fy.chalmers.se> f90angu@fy.chalmers.se (Andreas Gunnarsson) writes: >In article <1991Dec15.012454.13934@athena.mit.edu> solman@athena.mit.edu (Jason W Solinsky) writes: >>In article <1991Dec11.203341.19118@ee.eng.ohio-state.edu>, jcours@kaa.eng.ohio-state.edu (Jeffrey Cours) writes: > >This is the way my program Schizo works... This technique would work great, except that if you get bombed by an spl0 you are slowed down to a halt. I found a way to neutralize the 2 instruction scanning loops that programs like XTC use. Just bomb the core with DAT #0,#1 's instead of DAT #0,#0. Any program that is looking for non-zero locations will waste its time bombing ghosts. I'm still frustrated by the way ICWS'88 favors small, non-moving, single-threaded programs over more intelligent programs. I have a 3 instruction program that beats all my other programs, plus a lot of those on Koth. :-( >-- >============================================================================== >73 es 88 de SM7TLS f90angu@fy.chalmers.se Andreas Gunnarsson > I won't be able to read email 19-31 december > I'm sorry you wasted your time reading this kind of nonsense Subject: Changes to the Corewar standard From: rjc@geech.gnu.ai.mit.edu (Ray) Date: Mon, 16 Dec 1991 16:03:30 GMT Message-ID: <1991Dec16.160330.13557@mintaka.lcs.mit.edu> I think the current corewars standard favors small _non-moving_ single threaded programs that bomb with SPL0. With these types of programs the difference between the winner and the loser is the scanning routine and the coresize. I think it can be mathematically proven (although I can't do it) that there exists an optimum scanning/bombing loop for each coresize which cannot be beaten except by lucky hits. XTC seems to have the optimum scanning routine for a coresize of 8000. I think we have pushed corewars to the limit and it's time to change it. Instead of sporatically implementing changes on different corewar systems let's take a vote. Here of some of my proposals (most of you already know them) 1) Addressing limitation of CORESIZE/16. (in a coresize of 8000, you can only address a maximum of -250,250 or -500,500 with indirection) What happens to programs that try to address outside this range? What will a mov #0 4000 do? 2) SPL task creation change. Each decendent gets 50% of parent's timeslice. 3) System Variables - CONSTANTs inserted into your program at assemble time. CORESIZE - Size of core ADDRESS_SIZE -CORESIZE/16, CORESIZE/8, or CORESIZE, whatever you choose to implement 4) New Instructions INV PCT 5) New Addressing modes POST Increment '>' (A stack! mov data,,data2) 6) Status Registers It's almost impossible to tell how many tasks you are running or if any have died. I propose a new instruction, MSR (MOVE STATUS REGISTER), which writes the number of tasks you currently have running to a memory location. Using this instruction you can tell when you have been spl bombed. Optionally this instruction could tell only the number of decendents of the current task. Under this new standard, programs can be either mobile or stationary, either method is ok. Under ICWS'88 small, non-moving, spl0 bombers are preferred. I can already envision many neat programs you could write under this standard. Here's an example idea: Offense - Send out small fast moving scouts. When scouts find an enemy program, they SPLit off a (slower) moving program that runs back to the main program and reports the position of the enemy program. Meanwhile, the scouts are bombing the enemy's defenses with imps or reverse imps. The imps will confuse the enemy program (which would probably maintain a fence at the edges of it's address size). When the slow moving messenger program reaches the main program, it deposits a "password" in the fence, then a location, then it dies. The defense routine sees this password, shuts down all other tasks, and sends out a HEAVY bomber to the location specified. Defense - fence around the address size looking for programs which are within bombing range. This program is many times more complicated than it should be, however such a program would still survive sometimes. Under ICWS'88 a program like this is dead within a few cycles. My favorite program is COWBOY because it has a little complexity to it. Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: wms@iwarp.intel.com (William Shubert) Date: 16 Dec 91 17:33:07 GMT Message-ID: <1991Dec16.173307.22172@iWarp.intel.com> Andreas Gunnarson posted: >The drawback of this kind of program is that the coresize must be known to >know how big the bomb section of each program is. I'm not sure if all assemblers are as strict as mine, but in KotH you don't have to know. Watch this: divs equ 2 divdist equ (-1 / divs) + 1 Now, let's see...divdist = (-1 / 2) + 1 = (7999 / 2) + 1 = 3999 + 1 = 4000 (!) Obviously, setting divs to 4, for example, will make divdist 2000. -Bill (wms@iwarp.intel.com) Subject: Re: KotH - question From: wms@iwarp.intel.com (William Shubert) Date: 16 Dec 91 20:49:28 GMT Message-ID: <1991Dec16.204928.26522@iWarp.intel.com> OK, I guess I might have to periodically re-post submission info. No problem. Entry rules for King of the Hill Corewar: 1) Write a corewar program. KotH is fully ICWS '88 compatible, EXCEPT that a comma (",") is required between two arguments. 2) Put the line ";redcode" at the top of your program. This MUST be the first line. Anything before it will be lost. Additionally, adding ";name " and ";author " will be helpful in the performance reports. Do NOT have a line beginning with ";address" in your code; this will confuse the mail demon and you won't get mail back. In addition, it would be nice if you have lines beginning with ";strategy" that describe the algorithm you use. 3) Mail this file to "wms@iwarp.intel.com". 4) Within a few minutes you should get mail back telling you whether your program compiled correctly or not. If it did compile correctly, sit back and wait; if not, make the change required and re-submit. 5) In a hour or so you should get more mail telling you how your program performed against the current top 10 programs. If no news arrives in an hour, don't worry; entries are put in a queue and run through the tournament one at a time. A backlog may develop. Be patient. MORE ON KOTH COREWAR IMPLEMENTATION Core size: 8,000 instructions Max processes: 8,000 per program Duration: After 80,000 cycles per program a tie is declared. Example program: ;redcode ;name Dwarf ;author A. K. Dewdney bomb dat #0 dwarf add #4,bomb mov bomb,@bomb jmp dwarf end dwarf That's it! OK, now I've already implemented the process-splitting-divides-parent's-cpu- time idea. I just have to change to demons to run two tournaments at once. In addition, people have complained that when they have programs on the top 10 they get inundated with status reports evert time somebody submits a new entry. I realize that this is a problem and will fix it before I start the second tournament. -Bill (wms@iwarp.intel.com) Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: jonn@microsoft.com (Jon NEWMAN) Date: 16 Dec 91 22:14:20 GMT Message-ID: <1991Dec16.221420.8704@microsoft.com> In article <1991Dec11.203341.19118@ee.eng.ohio-state.edu> jcours@kaa.eng.ohio-state.edu (Jeffrey Cours) writes: > > My idea was to have a program that split itself into >several sub-programs, each one spaced around the core at equal intervals... > >Thoughts? Ideas? Suggestions? Sounds suspiciously similar to my own self-repairing fighter, "Five Musketeers". Look for it in the directory of "Jon's Standards" fighter programs associated with my Macintosh Core War simulator "Core! 1.1". BTW, such a program sounds _less_ resistant to vampires, rather than more. All you have to do is to capture one process and tell it to kill off all its kin. -- jonn@microsoft.com This is not the official opinion of Microsoft Corporation. Bill Rules! Subject: Re: Large vs small From: earl@elec.canterbury.ac.nz Date: 17 Dec 91 02:38:23 GMT Message-ID: <1991Dec17.143823.1@elec.canterbury.ac.nz> Some thoughts... Back in 1987, in the heady days of original Core war, even before the advent of SPL, I wrote a my own "Red Code" system for our large VAX so that our post-grads could play Core War. A decision was made right from the start that instead of just two players' programs fighting it out, I would let EVERYONE fight simultaneously in the 50,000 core arena. Thus there were many battles where up to twenty-five programs were participating together. And to minimize the luck factor, each battle would be played fifty times. Battles were fought once a week (run overnight) and the program that won the most times would be deemed the winner (and the lucky owner would get a chocolate fish, or a 50 block diskquota increase - I was Sysman!). What happened initially was that stupid programs like Dwarf would win all the time - sophisticated programs never stood a chance. So, to help large programs survive, I created a "firing window" (like what seems to be being proposed in this newsgroup at the moment). The size of this window was CORESIZE/10 or CORESIZE/no.of players whichever was smaller. This was of course relative to the current program counter. Programs were allowed to "look" anywhere in the Core (MOV -20000 A) but only allowed to "bomb" in their window. Bombs thrown outside this window would be forced back inside with wraparound (using modulus the windowsize). This worked fine. Now programs had to shift themselves around the core to get within striking range of the others. The most intelligent programs won all the time. There were also some special instructions (of the format SPC #n, X). These would give your program (depending on the value of "n") information to the questions:"How many opponents are left?", "How many opponents in my Firing Window?" and "How many instructions have been executed since this battle began?". And then SPL arrived. Aaargh! SPL with twenty players! We would never get a result. Not unless I let the thing run all week chewing up vast quantities of CPU, and even then you'd probably get a draw. Nope, there had to be a better way. So the ENS (enslave) instruction was invented. This would let one player "capture" another player's "program counter". The victim would be deemed killed and the victor (he who had planted the ENS) would have two. For ENS to work, you could not just fire "dumb" ENS bombs all over the place, either. ENS required a bit of work - both you and your victim had to run through the same instruction. When the victim ran over the ENS, they would stop (like JMP 0) until you ran over it too. Then you would carry on the the next instruction, they would die, and your new slave would JMP to operand specified with the ENS. This worked fine. Now the programs who used ENS most effectively would win. Since what we were playing now was no longer true Core War (well, it never was really), I invented some more instructions and concepts. First of all come the interrupts and pickets. A program would lay a line of pickets on the far edge of its firing window and whenever any of these pickets were bombed, an interrupt would occur to the player who laid the picket. This player's program would do an automatic jump to a relevant routine to deal with the peril. The routine would end with RTI (return from interrupt). Which would return the PC, context intact, back to the original code. Then came the "player in my window" interrupt. Then the "player ran over this statement" interrupt. Closely followed by the contraversial "someone jumped over my picket" interrupt. Now programs could actually "see" (and "hear" too, I guess). No longer were they dumb entities crawling around their world, blindly striking at each other, but true creatures reacting to stimulus and fighting intelligently to the death. - - - - The gist of this missive is to give you a few ideas for the evolution of Core Wars proper. I am not suggesting that my totally non-standard Core War implementation is an better than the current world standard. That is up to those who play. But I do hope that this is read with an open mind. Anyway it seems from the way the newsgroup is heading that you will be introducing the firing window concept soon. Good thing too I say. Andrew Earl EARL@elec.canterbury.ac.nz Subject: Re: Encouraging larger programs (was Re: KotH suggestions) From: cpbeaure@descartes.waterloo.edu (Chris Beauregard) Date: 17 Dec 91 03:08:07 GMT Message-ID: <1991Dec17.030807.25186@descartes.waterloo.edu> In article <1991Dec16.221420.8704@microsoft.com> jonn@microsoft.com (Jon NEWMAN) writes: >Sounds suspiciously similar to my own self-repairing fighter, >"Five Musketeers". Look for it in the directory of "Jon's Standards" >fighter programs associated with my Macintosh Core War simulator >"Core! 1.1". Nice program, too. I've based a few of my own on the musketeers idea. Unfortunately, the damn thing is just way to spread out to be really good, especially with things like the SPL 0 bombs, and various inproved vampiric bombing routines (I'd note that Memory can burn the musketeers pretty often... one of the reasons I wrote it actually...) As well, five processes are a little hard on the bombing run. Other major problems with the musketeers that I tried to correct in my own modifications are the fact that it doesn't check to see what's there before it copies over its brother. SPL 0 bombs there, and all hell breaks loose. I always write my programs to clear their target area before moving... Just out of curiosity, have you submitted it to the hill? I expect it would get its butt kicked, but how long it might last... Well, whatever. I'm outta here 'til after christmas sometime. I'll probably pop up at a new address too... >jonn@microsoft.com -------------------------------------------+--------------------------------- Chris Beauregard | Star Trek is the unix cpbeaure@descartes.waterloo.edu | of television. "If you can't beat 'em, take 'em with ya!" | - Me Subject: Re: Encouraging larger programs From: mjeffery@reed.edu (Mark Jefferys) Date: 17 Dec 91 07:09:23 GMT Message-ID: <1991Dec17.070923.9042@reed.edu> In article <91350.23:31:18.232103.DURHAM@ricevm1.rice.edu> DURHAM@ricevm1.rice.edu (Mark A. Durham) writes: % >>divs equ 2 % >>divdist equ (-1 / divs) + 1 >>Now, let's % see...divdist = (-1 / 2) + 1 = (7999 / 2) + 1 = 3999 + 1 = 4000 (!) % This is fine if you know the size of core at the time of % assembly. But what if you want to write an assembler that % does not depend on core size? (Can it be done? Yes. The % object file needs to support negative numbers and the % MARS loader needs to make the appropriate conversions.) [...] % After all, if we all know KotH has a core size of 8000, what % is the point of writing a long fancy equation to express % half core size? Just use % % HALF EQU 4000 % QUARTER EQU 2000 % EIGHTH EQU 1000 % % and so on. This is much clearer. % % MAD The difference is that this second method requires you to know the coresize at writing time, which is a lot earlier that assembly time. On many corewars systems, assembly is performed right before loading, so that assembly usually does know what the core size is. --- Mark Jefferys Internet: mjeffery@reed.edu Subject: KotH *EXPANSIONS* From: wms@iwarp.intel.com (William Shubert) Date: 17 Dec 91 07:14:12 GMT Message-ID: <1991Dec17.071412.9871@iWarp.intel.com> OK, changes have come. First, I have altered the game so that there are three "information-loads" possible: ;redcode verbose This is what everything USED to be. Mail on every new entrant. ;redcode This is what everybody is NOW. You only get mail when a challenger to the hill arrives IF the challenger makes it onto the hill. ;redcode quiet Here you only get mail when YOU make it onto the list or when you get shoved off. If anybody wants their programs already on the list to change to "verbose" or "quiet" send me mail. In the meantime just add "verbose" or "quiet" to the ";redcode" line of your program to get that automatically. If you get mail that you don't think that you should get let me know. Now for the good stuff. If you want, enter your program with ";redcode-x" and PRESTO! YOU'RE IN THE EXPERIMENTAL TOURNAMENT! Now what does this mean? 1> When a process splits, it's children share it's CPU time. 2> When a process dies, it's CPU time is given to it's sibling, or it's siblings descendants if the sibling has split. 3> ALL ADDRESSING MODES ARE ALLOWED. So "add #4, #5" will become "add #4, #9" after execution. This is just a pet peeve of mine, like no commas; why NOT allow these modes? The regular tournament is same as always. In the ;redcode-x tournament I have started it with two fighters; Leech 2.0 (which is Leech without the "SPL" instruction in the drain) and Twin Dwarves which is just two dwarves right next to each other bombing in opposite directions. OK, OK, so these are lame fighters but it's late and I'm tired. -Bill (wms@iwarp.intel.com) By the way, the current top-10 on the ICWS '88 hill: W/ L/ T Name Score 280/154/ 6 B-57a 846 256/141/ 43 dodgem5 811 265/175/ 0 gnat2a 795 215/204/ 21 Bouncer 666 205/206/ 29 Leech 1.1 644 198/207/ 35 parasite 629 192/202/ 46 slowdown1 622 197/231/ 12 El Rey 603 179/254/ 7 Minidwarf 544 158/259/ 23 Ecstacy 497 And the strategy of the #2 program, dodgem5: Program "dodgem5" (length 76) by "Steve Newman (snewman@cs.stanford.edu)" (contact address "snewman@neon.stanford.edu"): ;strategy Write out a bunch of flag values and wait for the enemy ;strategy to bomb one. Analyze enemy's bomb location. Copy a dwarf ;strategy type program to a location that appears safe and transfer ;strategy control to it. Large size is due to a simple one-shot ;strategy redundancy mechanism that helps resist damage in early stage ;strategy of play. Subject: Re: Good ideas From: snewman@Neon.Stanford.EDU (Steven Newman) Date: Tue, 17 Dec 1991 08:27:59 GMT Message-ID: <1991Dec17.082759.5348@CSD-NewsHost.Stanford.EDU> Mark A. Durham writes: > One way to take the sting out of SPL 0 without changing task time allocation > would be to establish "ownership" of instructions. Trying to execute an > instruction which your program did not "own" would result in the task > dying. Thus, SPL 0 bombs would be no more lethal than ordinary DAT 0 bombs. This strikes me as very dangerous. You've crossed the line from making self-replicating programs too vulnerable to making them too powerful. I don't see any way of killing a moderately fecund program under these rules. You can't subvert it, because any attempt to modify the program (i.e. SPL 0 or JMP 0 bombs to paralyze it, vampire-style subversion, etc.) will kill it. You can't kill it normally (i.e. with DAT bombs), because each dying process transfers its "manna" to the remaining processes, which replicate to replace it. Note that I'm not assuming any special "control registers" that give information about the number of executing processes and so forth - just a program that continually replicates itself while also spending some energy on attack. So a decent replicating program can never be killed. It might never win, but it will never lose, so eventually you'd end up with a lot of replicating programs that always tie each other (barring extreme flukes). I do agree with almost everything else in Mark's posting. We definitely need to do something... I have a program ("gnat2a") currently sitting near the top of the Hill (it was at the top for a few hours) that is TWO INSTRUCTIONS LONG (more or less). Here is the full source: start MOV <-19,<-19 JMP start,<-20 JMP -1,<0 JMP -1,<0 JMP -1,<0 JMP -1,<0 END start (The extra JMP -1,<0 instructions are to keep it from damaging itself too seriously when the bombing run sweeps over itself; watch it run if you don't see how this works.) It's ridiculous that a program this tiny should be successful. It's just a stupid little trick - a 2-line program that's able to bomb memory at 1.5 times the speed of light. But under the current rules, the sort of sophisticated programs that could deal with gnat2a as the mere annoyance it ought to be get immediately stomped by vampires. Some sort of change to SPL has to be part of the answer. Incidentally, I'd like to take this opportunity to thank William Shubert for setting up the KotH server. It's made Core War much more interesting, for me at least. Will we be seeing the ;strategy lines of the current hill occupants sometime soon? - Steve Newman (snewman@cs.stanford.edu) Subject: hard-coding core size (was Re: Encouraging larger programs) From: snewman@Neon.Stanford.EDU (Steven Newman) Date: Tue, 17 Dec 1991 08:39:51 GMT Message-ID: <1991Dec17.083951.5744@CSD-NewsHost.Stanford.EDU> [discussion of programs that depend on the size of core, constants for the core size, etc.] Of course, many programs depend on the size of core in other ways. Probably half of all bombing programs depend on the fact that coresize is divisible by 4, or they'd write all over themselves (Leech and XTC are two particularly well-written examples of this). Many programs take advantage of very tricky (implicit) arithmetic involving the core size, e.g. assuming that if you bomb at a certain interval you'll move through all of core with a nice spread and end up back at a certain point that will cause you to bomb yourself in a very precise way so as to move from one activity to another without needing an explicit loop counter or conditional instruction. XTC is a beautiful example of this - look at how it switches from dropping SPL 0 bombs to DAT 0 bombs. If there was a point to all that, it was that there are types of programming that are very effective if you know the core size when you write the program, but are nearly impossible if you don't know the core size when you write the program, no matter how much help the assembler gives you. About the only workaround would be to support conditional assembly based on compile-time constants like CORESIZE, assuming a small number of possible core sizes. (Or, you could simply avoid this sort of tricky programming, but that's no fun!) - Steve Newman (snewman@cs.stanford.edu) Subject: Changing the split command From: fraserc@dcs.glasgow.ac.uk (Campbell Fraser) Date: 17 Dec 91 13:31:16 GMT Message-ID: <1991Dec17.133116.6682@dcs.glasgow.ac.uk> In Article 186 in rec.games.corewar DURHAM@ricevm1.rice.edu (Mark A. Durham) writes >One way to take the sting out of SPL 0 without changing task time allocation >would be to establish "ownership" of instructions. Trying to execute an >instruction which your program did not "own" would result in the task >dying. Thus, SPL 0 bombs would be no more lethal than ordinary DAT 0 bombs. I should just point out that this must be an absolute NO NO. Many very effective programs work because they drop clever bombs on their foes. These bombs can be far more sophosticated than a spl 0. Take XTC for example. Its bomb is still pretty primitive but certainly more advanced than spl 0. I also suggest that beating mice under this scheme would be nigh on impossible. Please everyone, stop trying to destroy the instruction and instead work out how to beat it. Its actually pretty easy. Campbell Fraser -- --------------------------------------------------------------- fraserc@dcs.glasgow.ac.uk | --------------------------------------------------------------- | Mail : Campbell Fraser, Department of Computing Science, | Subject: Question about Spilt From: JJJ101@psuvm.psu.edu Date: 17 Dec 91 14:19:05 GMT Message-ID: <91351.091905JJJ101@psuvm.psu.edu> Quick question: Suppose program 1 has 3 procs A1 A2 and A3 program 2 has 1 proc B The current execution (I think) would be: A1 B A2 B A3 B A1 B A2 B A3 B A1... ______________| | Now suppose A1 here executes a SPL and process A4 is spawned Can someone demonstrate what the next few CPU slices would look like? Thanks -- ..................................................................... James "Stush" Jesensky . ..................................................................... ABCDEFGHIJKLMNOPQRSTUVWXY and f*ck*ng Z . ..................................................................... jjj101@psuvm.bitnet . . jjj101@psuvm.psu.edu . . jesensky@endor.cs.psu.edu . . jesensky@cs.psu.edu . "If it's too slow, . jesensky@math.psu.edu . You're too young." . jjj@arlvax.bitnet . . jjj@arlvax.psu.edu . . ..................................................................... Subject: Far Addressing From: JJJ101@psuvm.psu.edu Date: 17 Dec 91 14:27:19 GMT Message-ID: <91351.092719JJJ101@psuvm.psu.edu> There's been a lot of support for limiting how far a process can reference in the core. For example, in a 8000 word core, allowing a process to only address +-1000 words. This requires a program to move around in the core or send out scouts, and gives larger programs a more fair chance. Another way would be to implement far and near addressing, with far addressing much more costly. Here's two quick ideas how this could be done. 1. Near addressing (say +-1000) is the same as it always ways. A far address reference now requires 3 CPU cycles. If a process attempts to reference a far address with an instruction, the PC is not updated for 2 cycles. On the third cycle, the actual instruction is executed and the PC updated. 2. Each process has a SEG1 and SEG2 register. Each instruction now has a far and short version. (Suppose the far version is prefixed with an underscore.) Example: mov 1,2 ; Near move _mov 1,2 ; far move The far instruction: _MOV A B is converted to: MOV (1000*SEG1+A) (1000*SEG2+B) Issuing a far instruction clears SEG1 and SEG2 so the cost of far addressing is loading the registers. (Comment: SEQ1=0 implies the current addressing space) Just some ideas. Method one will work with all current redcode, so I would favorite it. (Method two would require a lot of rewritting--both of corewar systems and recode warriors.) -- ..................................................................... James "Stush" Jesensky . ..................................................................... ABCDEFGHIJKLMNOPQRSTUVWXY and f*ck*ng Z . Subject: Re: Good ideas From: rjc@geech.gnu.ai.mit.edu (Ray) Date: 17 Dec 91 15:38:37 GMT Message-ID: <1991Dec17.153837.22247@mintaka.lcs.mit.edu> In article <1991Dec17.082759.5348@CSD-NewsHost.Stanford.EDU> snewman@Neon.Stanford.EDU (Steven Newman) writes: >I do agree with almost everything else in Mark's posting. We definitely >need to do something... > >It's ridiculous that a program this tiny should be successful. It's just >a stupid little trick - a 2-line program that's able to bomb memory at >1.5 times the speed of light. But under the current rules, the sort of >sophisticated programs that could deal with gnat2a as the mere annoyance >it ought to be get immediately stomped by vampires. Some sort of change >to SPL has to be part of the answer. I feel the same way. I submitted 2 programs (Minidwarf, and D Crement) which do essentially the same thing. They are basically 2-3 instructions long with some sugar on top. D Crement does what gnat2a does except I tried to get fancy in later revisions, like using djn to DECREMENT the b-field of programs, and when they are decremented to 0, SPL bomb them, then DAT them. (it worked for many programs which put their constants and data at the end and use positive offsets like mov dat,@3 which decrement fairly quickly. I screwed it up in later versions by trying to get even more elaborate. Simplicity seems to work best) Minidwarf is essentially an '88 version of the original dwarf. start mov bomb,@-50 jmp start,Incidentally, I'd like to take this opportunity to thank William Shubert >for setting up the KotH server. It's made Core War much more interesting, >for me at least. Will we be seeing the ;strategy lines of the current >hill occupants sometime soon? KoTH is great. I look forward to C-Robots server too. C-robots isn't nearly as simplistist as Corewars :-(, programs need a little more intelligence. I still want a limited-addressing range corewars. It makes the scanning routines much more interesting and harder to write since programs can move about like subs at sea without instantly being able to see the whole ocean. For know ;recode-x is enought to re-kindle my interest. > - Steve Newman (snewman@cs.stanford.edu) PS: SPL is very useful. I don't want it to die, I just want to see SPL 0 effectively neutralized. Subject: Re: Failed return address From: neur0mancer@maple.circa.ufl.edu (Neuro Mancer) Date: 17 Dec 91 18:51:36 GMT Message-ID: <1991Dec17.185139.17087@math.ufl.edu> In article <1991Dec17.044728.7238@iWarp.intel.com>, wms@iwarp.intel.com (William Shubert) writes: >Help! King of the Hill got a submission from somebody with a return address >of: >NEUR0MANCER%MAPLE@pine.circa.ufl.edu > >When KotH tried to send a response the postmaster rejected it. Not being too >knowledgeable about non-"name@loc.here" type addresses, who is this person? >Can they possibly change things so their return address works? > -Bill (wms@iwarp.intel.com) I wondered what was taking so long. That address is the one that usually works. There are some more of my addresses in my .sig. I have no idea how to change things around so that my retuen address works. But I realized soon after I mailed out my program that it was the wrong version. There's no problem with submitting more than one program, is there? ====== neur0mancer%maple.decnet@pine.circa.ufl.edu neur0mancer@oak.circa.ufl.edu (maybe) 73@arms.uucp (checked least often) Subject: Re: Encouraging larger programs From: herbison@ultra.enet.dec.com (B.J.) Date: 17 Dec 91 22:07:16 GMT Message-ID: <31773@nntpd.lkg.dec.com> In article <1991Dec15.043629.3307@CSD-NewsHost.Stanford.EDU>, snewman@Neon.Stanford.EDU (Steven Newman) writes: |>There are at least four ways to implement "fractional allocation", i.e. |>redefining SPL so that a process cannot steal time from other processes by |>SPLitting (it just subdivides its own time allocation): 5. When a process dies, its time slice is given to the processes belonging to the opponent, weighted by the time they are receiving. 6. When a process dies, its time slice is given to the processes belonging to the opponent, split equally between the processes. To the victor belongs the spoils. If the death of a process is defined in this manner, it might also be useful to implement a `graceful termination' that allows a process to decide to terminate (having fulfulled its task) and returning the time to its side. B.J. Subject: Expanding SPL From: JJJ101@psuvm.psu.edu Date: 17 Dec 91 22:42:57 GMT Message-ID: <91351.174257JJJ101@psuvm.psu.edu> There's been a lot of talk about changing the SPL instruction. One alternative is to introduce more instructions to create child processes. A possible idea: SPL A (Spilt) Same as the '88 standard FRK A (fork) Acts like SPL, but the child and parent share their CPU slice. SPW A (spawn) SPW suspends the current process by removing it from the process queue and placing it in a waiting queue. A child process is given the parents CPU slice. When the child process terminates, the parent is given back its CPU slice, and continues execution. THD A (thread)A child created by THD is not given full process status. Instead, it is considered a thread. Threads are not allowed to have offspring. If a thread executes a SPL, FRK, THD, or SPW instruction, it should be treated as an NOP. Threads share their parent's CPU slice. JOI (join) The current process is placed in the waiting queue. (Like spawn). It is awaken when one of it's children from a FRK or THD instruction terminates. (Note: SPL and JOI do not go together) If no children exist, treat it as a NOP. -- . James "Stush" Jesensky . Subject: Re: Expanding SPL From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: Wed, 18 Dec 1991 06:19:02 GMT Message-ID: <1991Dec18.061902.20552@vuse.vanderbilt.edu> In article <91351.174257JJJ101@psuvm.psu.edu> JJJ101@psuvm.psu.edu writes: >A possible idea: >SPL A (Spilt) Same as the '88 standard... >FRK A (fork) Acts like SPL, but the child and parent share... >SPW A (spawn) SPW suspends the current process by removing it... >JOI (join) The current process is placed in the waiting queue... The concept of a "waiting queue" is interesting. I have taken sort of the opposite approach by introducing the SSP (Suspend) and RLS (Release) instructions in my system, CoreWar Pro. SSP suspends (i.e. puts into a waiting queue) all processes *except* the process executing SSP. Processes remain suspended until either (a) the process that executed SSP terminates or (b) it executes a RLS instruction. The SSP/RLS combination is very powerful in that it allows a form of "preemptive multitasking", i.e. a process is able to temporarily grab all time slices allocated to the program. The motivation behind SSP/RLS is of course to confer some resistance against vampyric capture and SPL-bomb slowdown: a monitoring "master" process scans its "slave" processes for some sign of subversion by the enemy, executes a SSP, kills the subverted processes by first overwriting their code and then executing RLS, and finally restores the program to its uncompromised state. >THD A (thread)A child created by THD is not given full process... THD is subsumed by Jon Newman's descendant count modification: THD A has the same effect as SPC A #0 (split a process to A, allocating zero child processes to it). I very much like the idea of introducing new opcodes for new split-variants instead of "overloading" SPL with new semantics. There's no reason why you shouldn't be able to use SPL, SPC (SPlit-descendant count) and FRK (or whatever you want to call share-slice-with-parent) in the same program. >. James "Stush" Jesensky . -Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: Re: Good ideas From: f90angu@fy.chalmers.se (Andreas Gunnarsson) Date: 18 Dec 91 07:07:03 GMT Message-ID: <1991Dec18.070703.2916@fy.chalmers.se> In article <91350.23:56:35.483801.DURHAM@ricevm1.rice.edu>, DURHAM@ricevm1.rice.edu (Mark A. Durham) writes: |> [Text deleted] |> One way to take the sting out of SPL 0 without changing task time allocation |> would be to establish "ownership" of instructions.... I think the 2nd argument should be considered. A solution could be to still allow a program to execute code that belongs to another program, but when a SPL is executed, the new task belongs to the owner of the SPL and uses its time. To make it useless to drop bombs with the following code mov 1,1 spl 0 the owner of an instruction that is moved should be the owner of the mov instruction or the moved instruction, not the program that executes it. |> [Text deleted] -- ============================================================================== 73 es 88 de SM7TLS f90angu@fy.chalmers.se Andreas Gunnarsson I won't be able to read email 19-31 december I'm sorry you wasted your time reading this kind of nonsense Subject: Re: Expanding SPL From: JJJ101@psuvm.psu.edu Date: 18 Dec 91 14:13:23 GMT Message-ID: <91352.091323JJJ101@psuvm.psu.edu> In article <1991Dec18.061902.20552@vuse.vanderbilt.edu>, you say: > >In article <91351.174257JJJ101@psuvm.psu.edu> JJJ101@psuvm.psu.edu writes: >The concept of a "waiting queue" is interesting. I have taken sort of the >opposite approach by introducing the SSP (Suspend) and RLS (Release) >instructions in my system, CoreWar Pro. >-Stefan Yes, I'm familiar with CoreWar Pro. For those who aren't, here's some documentation. The EXC and PCT instruction might not be clear. I don't have time to explain them today, maybe Dr. Strack will post an explaination. (Note: This is not the current version of CoreWar Pro, but it's the only version I had on my harddisk here at work.) COREWAR PLUS V1.8: REDCODE+ INSTRUCTION SET ******************************************* (adapted from A.K.Dewdney) --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Data statement | DAT | B | Nonexecutable: B is data value | | | | | | --------------------------------------------------------------------- Store-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Move | MOV | A B | Move contents of A to B | | | | | | --------------------------------------------------------------------- | Add | ADD | A B | Add contents of A to B, | | | | | store result in B | --------------------------------------------------------------------- | Sub | SUB | A B | Subtract contents of A from B, | | | | | store result in B | --------------------------------------------------------------------- | Random | RND | A B | Generate random number (range 0..A)| | | | | and store it in B | --------------------------------------------------------------------- Branch-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Jump | JMP | A | Transfer control to A | | | | | (unconditional) | --------------------------------------------------------------------- | Jump if zero | JMZ | A B | Transfer control to A if contents | | | | | of B is zero | --------------------------------------------------------------------- | Jump if not zero | JMN | A B | Transfer control to A if contents | | | | | of B is not zero | --------------------------------------------------------------------- | Jump if greater | JMG | A B | Transfer control to A if contents | | than zero | | | of B is greater than zero | --------------------------------------------------------------------- Counter-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Decrement, jump | DJZ | A B | Subtract 1 from B and jump to A | | if zero | | | if contents of B is then 0 | --------------------------------------------------------------------- | Decrement, jump | DJN | A B | Subtract 1 from B and jump to A | | if not zero | | | if contents of B is then not 0 | --------------------------------------------------------------------- Process-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Split | SPL | A | Split execution into next | | | | | instruction and A | --------------------------------------------------------------------- | Halt | HLT | - | Terminate execution of | | | | | (sub)process | --------------------------------------------------------------------- | Suspend | SSP | - | Suspend execution of all other | | | | | subprocesses | --------------------------------------------------------------------- | Release | RLS | - | Release suspended subprocesses | | | | | | --------------------------------------------------------------------- Stack-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Gosub | GSB | A | Transfer control to A; push | | | | | current address onto stack | --------------------------------------------------------------------- | Return | RET | A | Pop return address from stack, add | | | | | A, and transfer control to it | --------------------------------------------------------------------- | Push | PSH | A | Push contents of A onto stack | | | | | | --------------------------------------------------------------------- | Pop | POP | A | Pop address from stack and move it | | | | | to A | --------------------------------------------------------------------- | Stacksize | SSZ | A | store the number of elements | | | | | currently on the stack in A | --------------------------------------------------------------------- Special-Instructions --------------------------------------------------------------------- | Instruction | Mnem| Args| Description | --------------------------------------------------------------------- | Protect | PCT | A | Write-protect address A against | | | | | next write attempt | --------------------------------------------------------------------- | Execute | EXC | A B | Execute instruction at B, update B | | | | | & transfer control to A if no error| --------------------------------------------------------------------- ADDRESSING MODES **************** --------------------------------------------------------------------- | Mode |Sym| Description | --------------------------------------------------------------------- | immediate | # | is data value | | | | | | direct | $ | is effective address ($ can be omitted) | | | | | | data-relative: | | | | indirect | @ | is address of effective address | | | | relative to data statement | | pre-increment | > | increment, is then address of effective | | | | address relative to data statement | | pre-decrement | < | decrement, is then address of effective | | | | address relative to data statement | | PC-relative: | | | | indirect | ^ | is address of effective address | | | | relative to program counter | | pre-increment | / | increment, is then address of effective | | | | address relative to program counter | | pre-decrement | \ | decrement, is then address of effective | | | | address relative to program counter | --------------------------------------------------------------------- SYNTAX CONVENTIONS ****************** - one instruction per line, empty lines are permitted - comments begin with a semicolon (;) and go to the end of the line - mnemonics can be upper, lower or mixed case - mnemonics and arguments can be separated by space(s), comma(ta) or tab(s) - execution begins at the first instruction - each file contains exactly one program The Redcode preprocessor language extends basic Redcode syntax with labels and symbol definitions (see RPP.HLP). -- ..................................................................... James "Stush" Jesensky . ..................................................................... Subject: Re: Question about Spilt From: DURHAM@ricevm1.rice.edu (Mark A. Durham) Date: Wed, 18 Dec 1991 16:28:36 GMT Message-ID: <164D8935C.DURHAM@ricevm1.rice.edu> >Suppose program 1 has 3 procs A1 A2 and A3 > program 2 has 1 proc B > >The current execution (I think) would be: > >A1 B A2 B A3 B A1 B A2 B A3 B A1... > ______________| > | >Now suppose A1 here executes a SPL and process A4 is spawned > >Can someone demonstrate what the next few CPU slices would look like? > Under ICWS'88, the new task A4 will execute after all other tasks have executed once, including A1. Execution is then: B A2 B A3 B A1 B A4 (repeat)... Under ICWS'86, the new task A4 would execute before all other tasks: B A4 B A2 B A3 B A1 (repeat)... You can see how SPL 0 is at least a little bit more manageable under ICWS'88 than under ICWS'86. MAD Subject: Re: Good ideas From: DURHAM@ricevm1.rice.edu (Mark A. Durham) Date: 18 Dec 91 16:35:35 GMT Message-ID: <164D894FE.DURHAM@ricevm1.rice.edu> OK. It is good to hear from people who think SPL should be left alone. It was not clear that there were any out there. What is clear now is that we need to take a poll to see whether people want to change SPL or not. If someone wants to take this poll for me, I will be pleased to let them. Otherwise I will collect votes once again. To be fair to all of those who have left their terminals for one reason or another, I will delay the (non-binding) vote until the second week of January. Volunteers or comments through Email, please. MAD Subject: Re: Expanding SPL From: drb@cs.brown.edu (Dan Bornstein) Date: 18 Dec 91 19:16:09 GMT Message-ID: <96625@brunix.UUCP> In article <1991Dec18.061902.20552@vuse.vanderbilt.edu>, stst@vuse.vanderbilt.edu (Stefan Strack) writes: |The concept of a "waiting queue" is interesting. I have taken sort of the |opposite approach by introducing the SSP (Suspend) and RLS (Release) |instructions in my system, CoreWar Pro. It seems to me though that SSP in the wrong hands (the enemy's of course) could be devastating: Enemy places JMP bombs to: SSP ; stop everything else MOV #1,FLAG ; indicate that we got the enemy LOOP JMP LOOP ; enemy loops forever Does this for a while, until *just one* process enters the loop. Then we DAT bomb core and then overwrite the JMP LOOP with a DAT bomb. Kaput. Am I far off base with this? -dan drb@cs.brown.edu Chocolate milk is the essence of creation. Subject: Validation Suite Update From: DURHAM@ricevm1.rice.edu (Mark A. Durham) Date: 19 Dec 1991 05:43:01 GMT Message-ID: <164D814D85.DURHAM@ricevm1.rice.edu> ; Proposed Validation Suite for ICWS'88 Memory Array Redcode Simulators ; --------------------------------------------------------------------- ; Author(s): Mark A. Durham ; Last Modification: December 18, 1991 ; Subscripts indicate changes in modes which do not change program ; behaviour. $ is used to mean direct mode for clarity. ; --------------------------------------------------------------------- ; PVS #1 start DAT #0, #0 END start ; Result: Failure on first cycle at start ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #2(a-d) start DAT #0, <1 change DAT #0, #2 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on first cycle at start ; Memory: change becomes DAT #0, #1 (one less than 2) ; --------------------------------------------------------------------- ; PVS #3(a-d) start DAT <1, <1 change DAT #0, #3 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on first cycle at start ; Memory: change becomes DAT #0, #1 (two less than 3) ; --------------------------------------------------------------------- ; PVS #4(a-c) start JMP 0, #0 ; b($,$) c($,@) END start ; Result: No failure ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #5(a-d) start JMP 1, <2 stop DAT #0, #0 change DAT #0, #2 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on second cycle at stop ; Memory: change becomes DAT #0, #1 (one less than 2) ; --------------------------------------------------------------------- ; PVS #6(a-c) start JMP @0, #0 ; b(@,$) c(@,@) END start ; Result: No failure ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #7(a-b) stop DAT #0, #2 ; b(<,#) start JMP @0, <0 END start ; Result: Failure on THIRD! cycle at stop ; Explanation: The A-field of JMP @0, <0 is evaluated BEFORE the ; B-field, and therefore the effective A-address is zero for the ; first cycle. The next cycle, the instruction is JMP @0, <-1. ; Again, the A-field is evaluated BEFORE the B-field, and ; therefore execution is transferred to stop after its B-field ; is decremented. ; Execution: start, start, stop ; Memory: start becomes JMP @0, <-1 (one less than 0) ; stop becomes DAT #0, #1 (one less than 2) ; --------------------------------------------------------------------- ; PVS #8(a-i) start JMP <2, #0 ; b,d,f,h(<,$) c,e,g,i(<,@) stop DAT #0, #0 change DAT #0, #0 ; b,c(#,#) d,e(#,<) f,g(<,#) h,i(<,<) END start ; Result: Failure on second cycle at stop ; Memory: change becomes DAT #0, #-1 (one less than 0) ; --------------------------------------------------------------------- ; PVS #9(a-d) start JMP <2, <2 stop DAT #0, #0 change DAT #0, #0 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on second cycle at stop ; Explanation: The A-field of JMP <2, <2 is completely evaluated before ; the B-field is evaluated. In this case, that means the jump will ; be 2 (from <2) plus -1 (from #0 decremented once) = 1 (stop). ; Memory: change becomes DAT #0, #-2 (two less than 0) ; --------------------------------------------------------------------- ; PVS #10(a-f) start MOV #0, 0 ; b(#,@) c($,$) d($,@) e(@,$) f(@,@) stop DAT #0, #0 END start ; Result: Failure on second cycle at stop ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #11(a-d) start MOV #1, <2 stop DAT #0, #0 change DAT #0, #1 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on second cycle at stop ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #12 start MOV 1, <1 stop DAT #0, #1 END start ; Result: Failure on second cycle at stop ; Memory: Unchanged! ; Explanation: This behaviour is open to interpretation. If one ; "completely" evaluates the A-operand first, one should make a copy ; of the instruction labelled "stop" as part of that evaluation. ; Then when the B-operand is completely evaluated as ; start + 1 + (1 - 1) = stop, the copy of the instruction labelled ; "stop" (prior to the decrement) is copied onto the instruction ; labelled "stop" (after the decrement), restoring "stop" to its ; initial state. ; There are those who would argue, and not without ; substantial basis, that there is no explicit reference in the ; standards to a "copy" and therefore the instruction labelled ; "stop" (after the decrement) should be copied onto itself. Thus ; stop would appear as "stop DAT #0, #0" after execution. ; Systems that "copy" the A-operand instruction include The MADgic Core ; and Core War Pro. ; --------------------------------------------------------------------- ; PVS #13 start MOV @0, <1 stop DAT #0, #1 END start ; Result: Failure on second cycle at stop ; Memory: Unchanged ; Explanation: See explanation under PVS #12 ; --------------------------------------------------------------------- ; PVS #14(a-b) start MOV <1, 1 ; b(<,@) stop DAT #0, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #0 (one less than one) ; Explanation: Here the decrement occurs before the copy. Therefore, ; DAT #0, #0 is moved onto itself. Note that @1 is evaluated as ; start + 1 + 0 = stop since the decrement occurred before the ; B-operand was evaluated. ; --------------------------------------------------------------------- ; PVS #15 start MOV <1, <2 stop DAT #0, #1 change DAT #0, #1 ; b(#,<) c(<,#) d(<,<) END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #0 ; change becomes a copy of start: DAT #0, #0 ; --------------------------------------------------------------------- ; PVS #16(a-b) start ADD #1, 1 ; b(#,@) stop DAT #1, #0 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #1, #1 ; --------------------------------------------------------------------- ; PVS #17 start ADD #1, <1 stop DAT #1, #1 END start ; Result: Failure on second cycle at stop ; Memory: Unchanged ; --------------------------------------------------------------------- ; PVS #18(a-d) start ADD 1, 1 ; b($,@) c(@,$) d(@,@) stop DAT #2, #0 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #4, #0 ; --------------------------------------------------------------------- ; PVS #19 start ADD 1, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #4, #1 ; Explanation: See the explanation for PVS #12 ; --------------------------------------------------------------------- ; PVS #20 start ADD @0, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #4, #1 ; Explanation: See the explanation for PVS #12 ; --------------------------------------------------------------------- ; PVS #21(a-b) start ADD <1, 1 ; b(<,@) stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #4, #0 ; --------------------------------------------------------------------- ; PVS #22 start ADD <1, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: start becomes ADD <3, <1 ; stop becomes DAT #2, #-1 (one decremented twice) ; Explanation: See explanation of PVS #12 ; --------------------------------------------------------------------- ; PVS #23(a-b) start SUB #1, 1 ; b(#,@) stop DAT #1, #0 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #1, #-1 ; --------------------------------------------------------------------- ; PVS #24 start SUB #1, <1 stop DAT #1, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #1, #-1 ; --------------------------------------------------------------------- ; PVS #25(a-d) start SUB 1, 1 ; b($,@) c(@,$) d(@,@) stop DAT #2, #0 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #0 ; --------------------------------------------------------------------- ; PVS #26 start SUB 1, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #-1 ; Explanation: See the explanation for PVS #12 ; --------------------------------------------------------------------- ; PVS #27 start SUB @0, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #-1 ; Explanation: See the explanation for PVS #12 ; --------------------------------------------------------------------- ; PVS #28(a-b) start SUB <1, 1 ; b(<,@) stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: stop becomes DAT #0, #0 ; --------------------------------------------------------------------- ; PVS #29 start SUB <1, <1 stop DAT #2, #1 END start ; Result: Failure on second cycle at stop ; Memory: start becomes SUB <-1, <1 ; stop becomes DAT #2, #-1 (one decremented twice) ; Explanation: See explanation of PVS #12 Subject: B-field of spl From: Date: Thursday, 19 Dec 1991 11:38:25 MST Message-ID: <91353.113825ASMQK@ASUACAD.BITNET> I have the following ideas to keep spl as a tool not a weapon. The assembler can generate a random number (CHECK) for each warriors. The spl command split the execution only if it's B-field id equal to CHECK. So if we want to split our program we can write: spl somewhere CHECK But our program possibly will not split because of an spl 0 0 bomb since 0 is not equal to CHECK. nandor sieben asmqk@asuacad Subject: SPL parents and mice From: kurt@crash.cts.com (Kurt Werle) Date: 19 Dec 91 19:49:17 GMT Message-ID: <1991Dec19.194917.16437@crash.cts.com> I don't have a copy of corewars yet (havent' written it :-), but it seems to me that if SPL is implemented where each child get 1/2 it's parents CPU time mice will once again become very hard to beat. If you kill a mouse, it's 'brothers' will become stronger as always, but if you 'catch' a mouse (eg. vampire) you will NOT weaken the others (only it's children mice). The only way a mouse will slow down is if it multiplies; that's the whole idea! I don't think we want that to happen. I DO like the diversified spl commands, though. Especially the thread one. If you want a program that can't be split, just use a thread and kill the parent process. I recall a large program from CoreWars! the mac program that had 3 dwarves, and picket tests, etc. It could use threads for all but the parent process (and keep the parent loop SMALL) to keep from getting vamped (which was one of it's big problems). (the program was > 80 lines). my 2 cents Kurt From: wms@iwarp.intel.com (William Shubert) Subject: Another failed KotH address Message-ID: <1991Dec19.214449.18980@iWarp.intel.com> Date: 19 Dec 91 21:44:49 GMT King of the Hill has been trying to contact somebody named Greg Titus. The address it's sending to is "t-gregt@microsoft.com". The mail has been bouncing because the machine "t-gregt@msft.UUCP" has been having problems. If Greg is out there and knows what is going on, could he contact me? -Bill (wms@iwarp.intel.com) Subject: Re: SPL parents and mice From: cedman@golem.ps.uci.edu (Carl Edman) Date: 20 Dec 91 04:10:33 GMT Message-ID: In article <1991Dec19.194917.16437@crash.cts.com> kurt@crash.cts.com (Kurt Werle) writes: I don't have a copy of corewars yet (havent' written it :-), but it seems to me that if SPL is implemented where each child get 1/2 it's parents CPU time mice will once again become very hard to beat. If you kill a mouse, it's 'brothers' will become stronger as always, but if you 'catch' a mouse (eg. vampire) you will NOT weaken the others (only it's children mice). The only way a mouse will slow down is if it multiplies; that's the whole idea! I don't think we want that to happen. No, that won't happen if the split command is changed the right way i.e. each child gets 50% of the CPU of the parent _and_ when a process gets killed its CPU share is lost. That way when you catch a mouse you do damage exactly proportional to the number mice which there are i.e. you don't kill all mice as it is currently (via SPL 0), nor do you do in effect no damage at all (as it would be if only DAT #0 was effective). In fact you could achieve the same effect even on an implementation which redistribute CPU power, by using JMP 0 bombs. Overall this change to SPL seems very fair to me. It limits the power of bombers, without making them completely ineffective, thus restoring balance. And balance is more than anything else which makes for good games and interesting new developments. I DO like the diversified spl commands, though. Especially the thread one. If you want a program that can't be split, just use a thread and kill the parent process. I recall a large program from CoreWars! the mac program that had 3 dwarves, and picket tests, etc. It could use threads for all but the parent process (and keep the parent loop SMALL) to keep from getting vamped (which was one of it's big problems). (the program was > 80 lines). Well, if for one do not like the proposals for half a dozen new versions of the SPL command. IMESHO there already are too many commands, particularily too many commands doing almost the same things (i.e. who ever uses the SUB command ?). Carl Edman Subject: Re: SPL parents and mice From: wms@iwarp.intel.com (William Shubert) Date: 20 Dec 91 05:53:56 GMT Message-ID: <1991Dec20.055356.28624@iWarp.intel.com> Well I think I can answer this question definitively. I just ran a bunch of fights of mice vs. Leech with parents splitting to share CPU time and Leech wins about 4/5 of the time. How? The mice run so slow just from their own splitting that Leech manages to capture almost all of them on it's own! Then once all but a few are captured the captured ones finish the job off by clearing the core before their brethren can breed. Along the subject of changes to Corewar, I also disagree more than one way to split is completely unnecessary. There should be one and only one way. The suggestion I saw recently - use the B op of SPL as an ID that must match - I like also, maybe more then the split-time idea. Why? Because vampires can STILL drain time if they're real smart or persistent (by trying IDs until one works or maybe searching the enemy code, trying one B op after another). Also, let's say all programs start with ID=0; then the command ID a,b sets ID to "b" if it is CURRENT "a", otherwise it's a no-op. This leaves tons of nifty ideas; for example, imagine two threads with IDs 1 and 2 execute this code: SPL proc1,#1 SPL proc2,#2 dat #0 This will take two processes executing the same code and make them jump to separate places! Anyway it might be worth trying. Which brings me this this: A list of what I have planned for KotH: 1) Try new instructions. Mark Durham had the clever idea of trying a bunch of 'em at once and automatically keeping track of how many people use each to decide which to keep. 2) Try setting a maximum write distance. 3) Try the SPL variant outlined above. 4) Add a usable interface. Right now my Corewar is designed for KotH so it's almost no fun at all to use interactively. If I just strap a cheesy X windows interface onto it I could distribute the source code each time a new Corewar variant is tried so people could try out their program ideas on exactly the system used for the tournaments. Anyway, these will all have to wait 'cause I'm going on vacation. See my next post. -Bill (wms@iwarp.intel.com) -- Hi! I'm a .signature virus. Copy me into yours and join the fun! Subject: Christmas Corewar From: wms@iwarp.intel.com (William Shubert) Date: 20 Dec 91 06:05:19 GMT Message-ID: <1991Dec20.060519.28825@iWarp.intel.com> Hello everybody and thanks for making King of the Hill work so well! There were some bugs there for a while but things are working smoothly now so thanks for hanging in. Recently I've been getting 5 to 10 entries per day and there's been a lot of variety. But hey, nothing lasts forever and I've been working for 6 months now without a single vacation so I need it. I will leave corewar up while I'm gone (I'm getting back January 5) but if anything goes wrong and the demons die that'll be it. Here's what you can do to help out while I'm gone: Feel free to submit programs, but if you don't get a response PLEASE DO NOT RESUBMIT YOUR PROGRAMS. If you get no response then something has gone wrong and there is NOBODY HERE TO PUT IT RIGHT. Resubmitting will just make a bigger mess for me to clean up when I get back. Please, PLEASE, PLEASE, if you have a program on the top 10 list do not submit a slight variant of it! Wait for your first program to fall off the list then try out the new one. This site only keeps mail for a few days so any posts over the next two weeks I won't see. If you want to let me know something please mail it in. Happy holidays everybody! Have nice vacations! And keep trying out your programs! You may have noticed that today I got the ";strategy" lines printed out in status reports. Include them in your programs! The current Hill: W/ L/ T Name Score 254/157/ 29 Leech 1.1 791 250/172/ 18 Parasite2 768 228/195/ 17 parasite 701 223/189/ 28 Ecstacy 697 223/214/ 3 dodgem6 672 162/162/116 Intangible Worm 88.1 602 195/241/ 4 El Rey 589 164/191/ 85 42 577 149/189/102 Virus 549 172/244/ 24 Killer 540 The program "42" is by Stefan Roettger, the author of Ecstasy. Nice to see he's around. Here's the ;redcode-x hill (splitting causes children to share the parent's CPU time): W/ L/ T Name Score 225/160/ 55 El Rey 730 210/142/ 88 Leech 2.0 718 205/135/100 Twin Dwarves 715 212/152/ 76 Minidwarf 712 201/146/ 93 slowdown-x 696 159/164/117 Splice2 594 88/ 68/284 Nova 548 140/200/100 Retrovirus 1.2 520 89/140/211 Modify2 478 85/156/199 host 454 Not as much action has been here as on the ;redcode hill - come on, feel free to submit any program to both hills! -Bill (wms@iwarp.intel.com) -- Hi! I'm a .signature virus. Copy me into yours and join the fun! Subject: are changes to SPL REALLY necessary? From: orb@ccwf.cc.utexas.edu (Norman Richards) Date: 20 Dec 91 16:54:19 GMT Message-ID: <64178@ut-emx.uucp> Am I the only one - or are there other people out there who think that changes to SPL are totally unnecessary? I definately see that SPL bombs and other forms of similar attacks are verytough - but would changing things really make things better? I dont think so - whatever you change it to - programs will be written to exploit it. Then - someone will think its obviously unfair or that there are of course better ways to do it (which is of course true because then all of this persons neat creations would do much better). I honestly don't see anything wrong with the way the SPL is implemented that wouldnt be cured by some form of memory paging or higher cost for further indexing memory type stuff. (hows that for being techinical :) No - I dont think it is the be all and end all of corewar solutions, but it does certainly seem to me that the main problems with SPL are things that just wont be changed with changing the implementation of SPL. There are just ALLWAYS going to be clever forms of attack using SPL no matter what you do. But - a neat balance would occur between SPL power (As well as other 'clever' forms of attack) and intellegence given that we address the overall 'problem' of any program being able to read/write anywhere in memory. (on the other hand - I also like the original idea of specifying the maximum number of subprocesses allowed by a SPL. If any changes were made this would seem to be the most sensible. Its just that I don't think that this addresses the heart of the problem.) ______________________________________________________________________________ orb@ccwf.cc.utexas.edu "Two roads diverged in the forest And I - I chose to climb the nearest tree. And that has made all the difference." Subject: Re: are changes to SPL REALLY necessary? From: stst@vuse.vanderbilt.edu (Stefan Strack) Date: 20 Dec 91 18:16:10 GMT Message-ID: <1991Dec20.181610.7905@vuse.vanderbilt.edu> In article <64178@ut-emx.uucp> orb@ccwf.cc.utexas.edu (Norman Richards) writes: > (on the other hand - I also like the original idea of specifying the maximum >number of subprocesses allowed by a SPL. If any changes were made this would >seem to be the most sensible. Its just that I don't think that this addresses >the heart of the problem.) But it does! The current problem with SPL is that it is overwhelmingly used as a weapon. The SPL/descendant-count instruction is a good antidote against it (a process created by SPL addr #0 is unaffected by SPL 0 type bombs) without being "too easy". It takes some clever programming to avoid having a SPL-resistant, self-replicating warrior succumb to its own process restric- tions. This is the kind of "intelligent" program I'd like to see encouraged! >orb@ccwf.cc.utexas.edu "Two roads diverged in the forest Happy Holidays, Stefan -- Stefan Strack, PhD {stracks@ctrvax|stst@vuse|stst@dmwsun.hh}.vanderbilt.edu Dept. Pharmacology, Vanderbilt Univ., Nashville, TN 37232-6600, USA Voice: +615-322-4890, Fax: +615-343-6532 "Real men don't use icons" Subject: Re: are changes to SPL REALLY necessary? From: solman@athena.mit.edu (Jason W Solinsky) Date: 21 Dec 91 02:24:50 GMT Message-ID: <1991Dec21.022450.14463@athena.mit.edu> In article <64178@ut-emx.uucp>, orb@ccwf.cc.utexas.edu (Norman Richards) writes: |> |> Am I the only one - or are there other people out there who think that |> changes to SPL are totally unnecessary? I definately see that SPL bombs I'm willing to bet that there are quite a few out there. I'm not one of them. Between January 10th and February 1st I will be taking a poll on this issue (as per a previous posting by MAD). I also hope to be able to poll people on how they would like SPL to change, although that is still uncertain. |> and other forms of similar attacks are verytough - but would changing things |> really make things better? I dont think so - whatever you change it to - |> programs will be written to exploit it. Then - someone will think its |> obviously unfair or that there are of course better ways to do it (which is |> of course true because then all of this persons neat creations would do much |> better). |> I honestly don't see anything wrong with the way the SPL is implemented that |> wouldnt be cured by some form of memory paging or higher cost for further |> indexing memory type stuff. (hows that for being techinical :) No - I |> dont think it is the be all and end all of corewar solutions, but it does |> certainly seem to me that the main problems with SPL are things that just |> wont be changed with changing the implementation of SPL. There are just |> ALLWAYS going to be clever forms of attack using SPL no matter what you do. The idea here is to increase the potency of longer programs, not to kill off the use of SPL as a mode of attack. I think a secondary goal is to keep everything simple. That's not accomplished by multiple SPL commands, and that's not accomplished by complicated memory addressing schemes. That's why I oppose all of these EXCEPT the limited addressing range restriction which keeps the code simple AND improves the diversity. Jason W. Solinsky Subject: Re: SPL parents and mice From: solman@athena.mit.edu (Jason W Solinsky) Date: 21 Dec 91 03:42:39 GMT Message-ID: <1991Dec21.034239.16674@athena.mit.edu> In article , cedman@golem.ps.uci.edu (Carl Edman) writes: |> ...it seems to me that if SPL is implemented where each child get 1/2 |> it's parents CPU time mice will once again become very hard to beat... |> |> No, that won't happen if the split command is changed the right way |> i.e. each child gets 50% of the CPU of the parent _and_ when a process |> gets killed its CPU share is lost.... This is why redistributing the parent's time is so important. Mice can be killed with or without redistribution (i.e. JMP 0 and vampires). If you just kill lost CPU slices, then a program can't terminate it's own processes. And DON't propose any of these ownership of memory things. The whole idea of corewars is that two programs are competing in neutral territory. |> Carl Edman Jason W. Solinsky Subject: Re: SPL parents and mice From: cedman@golem.ps.uci.edu (Carl Edman) Date: 21 Dec 91 16:42:03 GMT Message-ID: In article <1991Dec21.034239.16674@athena.mit.edu> solman@athena.mit.edu (Jason W Solinsky) writes: > This is why redistributing the parent's time is so important. I agree. Ownership of memory is a Bad Thing. Still, JMP 0 bombs under CPU redistribution are not perfect for several reasons: 1. They don't really kill the process. That means that to win, you have to have a second pass of DAT #0 bombing (and hope that you didn't miss even a single little enemy process - otherwise that single process again gets the total CPU power of the enemy). 2. JMP 0 bombs can be fixed i.e. an error-correcting program can notice the bomb, simply fix the spot where the bomb occured, and the bombed process is again fully in operation. Not any longer being able to terminate yourself might be a problem, though I'm not convinced it is. If it should turn out to be, a real terminate instruction TRM which redistributes might be added to redcode. An additional advantage of non-redistributing deaths, is that this might be a way to keep additional score during the course of a corewar. Each program starts out with a CPU power of 1 and as the programs fight each other slowly (or not so slowly sometimes) they wear down each others CPU power, until one of them finally drops to 0 and the other program wins. This is one stat I'd like to see in the graphical display of such a corewar implementation and maybe even have the remaining CPU of the winner recorded in the final tally. Carl Edman From: whatis@gnu.ai.mit.edu (Lupus Yonderboy) Subject: Core wars FAQ Message-ID: <21158@life.ai.mit.edu> Date: 21 Dec 91 22:22:31 GMT Can someone please send me the FAQ list, plus how to get information on (what appears to be) the CoreWars programming language(s)? This looks like it could become a new hobby (read: addiction) for me! :-) Steve Boswell whatis@gnu.ai.mit.edu From: nautilus@acm.rpi.edu (John M. Twilley) Subject: Needed: Unix CoreWar (text and K&R C) Message-ID: Date: 23 Dec 91 02:42:15 GMT I am running Unix on an old AT&T 3B2/400, and I was wondering if anyone had a *working* version of CoreWar that I could compile here. Currently, I only have access to one compiler, and that one is at iwarp.intel.com. :-) Any help would be appreciated; I do not know enough C to write this, yet. :-) -- John M. Twilley "There's a limit to stupidity, Jack, even for you." nautilus@acm.rpi.edu -- Ginger From: tkacz@CS.UWindsor.Ca (Peter Theodosius Tkacz) Subject: What is Core War Message-ID: <898@schoenfinkelcs.uwindsor.ca> Date: 24 Dec 91 03:30:15 GMT Could someone please tell me what Core War is. I just read one or two postings, because the system cleans out old postings after every few days. Coul you please email any answers to tkacz@server.uwindsor.ca Thank's. Peter From: rogue@cellar.org (Rachel McGregor) Subject: Is there an archive online Message-ID: Date: 29 Dec 91 07:48:36 GMT Is this newsgroup being archived at soda or another site? My site's feeds were disrupted as a result not only of holiday closings but because of a power problem at our upstream feed just before Christmas, so I'm sure I've missed several days' worth of articles. ---- Rachel K. McGregor : rogue@cellar.org : {tredysvr|uunet}!cellar!rogue "I'm not a journalist, but I play one on TV."