(tabs every 8 columns) DARWIN FOR 68000 ---------------- DARWIN is a computer game for assembly-language computer programmers. For more information, see my article in _Computer Language_, (April 1987 issue, p. 79). Or an earlier article in the computer recreations column of _Software--Practice and Experience_ (vol. 2, 1972, pp. 93--96). It has now been implemented for the 68000 microprocessor. Brief details are given in this document. But first, a copy of the rules for any computer. ==================================================================== The Rules of Darwin ------------------- The game is played in a region of computer memory called the _arena_ and is mediated by an _umpire_. The programs (_organisms_) of one player constitute a _species_. The organism currently in control may communicate with the Umpire by means of the three Umpire calls PROBE, KILL and CLAIM. PROBE is used to ask what is in a particular part of the arena, KILL to kill another organism and CLAIM to claim some empty space for the organism to reproduce itself. Here are the official rules for Darwin. (1) A species has a species number N, a size S(N), a start location G(N) and a set of protected locations P(N,1), P(N,2),..., P(N,R). (1.1) The number of protected locations, R, is an implementation-dependent function of the species size S(N). (1.2) Each of G(N), P(N,1),..., P(N,R) must be less than S(N). (1.3) S(N) must be less than an implementation-defined constant S. (2) The game is played in a region of core called the arena, of a size A that is implementation-dependent. (3) The game is managed by a program called the Umpire, which is outside the arena. (4) An organism of species N is a program within the arena, which obeys the following conditions: (4.1) It consists of S(N) locations, L, L+1,..., L+S(N)-1. (4.2) Its protected locations are L+P(N,1), L+P(N,2),..., L+P(N,R). (4.3) Its contents may be arbitrary, save that when executed starting at L+G(N): (4.3.1) It may read any location within the arena, but may not read any location outside it. (4.3.2) It may write to or call or jump to any location within itself or within an area claimed by CLAIM, or within an organism of the same species found by PROBE. (4.3.3) It may execute any of the three Umpire calls, PROBE, KILL and CLAIM. (4.3.4) It may not make use of input/output or of traps of any kind that might return control to it after it had lost control. Traps within the program may, however, be used. (4.4) Distinct organisms of the same species need not contain the same code. (5) PROBE is a call to the Umpire with two arguments, the species number, N, of the calling organism, and a location LOC within the arena. (5.1) If LOC is a protected location of an organism, control is transferred to that organism (at its start location). (5.1.1) The new organism receives no indication of how it obtained control. (5.1.2) The old organism receives no indication of how it lost control, other than the fact that when (if ever) it regains control, it is entered at its start location rather than at the return from PROBE. (5.1.3) On a transfer of control, all record of which locations have been probed is lost by the Umpire. (5.2) If LOC is not a protected location of some organism, then PROBE returns three numbers: HISNO, BOT and TOP. (5.2.1) HISNO is zero if LOC is empty, and otherwise the species number of the organism occupying LOC. (5.2.2) BOT and TOP are the limits (first and last + 1) of the largest contiguous block of memory surrounding LOC, which is empty except for the occupant of LOC, if any. (6) KILL is a call to the Umpire with two arguments as for PROBE. (6.1) LOC must be a location inside a block of memory probed by an organism of the calling species, and there must be an organism at LOC, distinct from the calling organism, but not necessarily of a different species (suicide is forbidden but cannibalism is allowed). (6.2) The effect of KILL is to destroy the organism at LOC. The carcass is left. (7) CLAIM is an Umpire call with two arguments as for PROBE. (7.1) LOC must be within a block of memory that has been probed by an organism of the calling species, and the S(N) locations starting with LOC must be empty, possibly as a result of an intervening KILL. (7.2) The effect of CLAIM is to cause the Umpire to record the presence of an organism of species N at LOC. (7.3) The calling organism may then write to or jump into the area CLAIM'ed (presumably it will copy itself there). (8) It is at the option of the implementation which infractions of the rules are detected. (8.1) A detected infraction of the rules results in extermination of the offending species. (8.2) In implementations where not all illegal actions are detected by the Umpire in the course of the game, players are required to show one another their programs after a game and, if necessary, explain any procedures used in order to verify that they keep to the rules. (9) To play a game, each player submits K(N) initial organisms written in an agreed language, together with a specification of the size, start location, and protected locations of his species. (9.1) K(N) = integral part of (size of arena)/(2*(number of players)*S(N)). (9.2) The organisms are loaded at pseudo-randomly chosen locations in the arena. (9.3) Control is initially given to some organism, chosen in an implementation-dependent way. (10) The game ends when only one species remains, or at the end of a fixed time, whichever occurs first. (10.1) The winner is the player whose species has most organisms left. ===================================================================== 68000 implementation -------------------- The Umpire I have written runs on a Macintosh. But the organisms use pure 68000 assembly language, so programmers of different 68000 machines can compete with each other. (Umpires for other machines, however, will have to be written by owners of those machines.) This also means that the Darwin species for 68000 may not use any of the standard Macintosh assumptions, such as where A6 points. The species are to be written in Motorola-compatible 68000 assembly language. Any special features of your assembler that you use, may make your program unusable by others! The arena is presently 32 K bytes in size. The present maximum size S of an organism is 256 bytes. The number of protected cells is R = integer part of (S(N)/4), where S(N) is the actual size of species number N. Each species loaded at the beginning of the game will consist of K(N) identical copies, but new organisms of the species created later need not be the same as the originals. The original copies loaded will be at even-numbered addresses, but any organism you add later must be placed by you. Initial control is assigned randomly. A few other details also need to be specified. When control is passed to your program, it will be at the entry point. The register A6 will point to the bottom of the arena. Register A7 will contain the Umpire's stack pointer. Since it points outside the arena, you are not allowed to use it as a stack pointer. (If you wish, you may change it to point to a legal space for your use. But it should be restored to its original value for any Umpire call.) The three umpire calls will be made using small negative offsets from A6. The offset amounts (called probe, kill, claim) will be added to your assembly-language program to fit the particular Umpire. A PROBE call is done using: jsr probe(A6) On calling PROBE, register D0.B must contain N, the number of the species; register A0 must contain the address LOC; and register A7 must contain the original Umpire stack pointer. On return from a PROBE, register D0.B contains HISNO (between 0 and 255; 0 means unoccupied); register A1 contains BOT; register A2 contains TOP. All registers except D0,A1,A2 are preserved. A KILL call is done using: jsr kill(A6) On calling KILL, register D0.B must contain N; register A0 must contain LOC, and register A7 must contain the original Umpire stack pointer. No information is returned by KILL. All registers except D0 are preserved. A CLAIM call is done using: jsr claim(A6) On calling CLAIM, register D0.B must contain N; register A0 must contain LOC, and register A7 must contain the original Umpire stack pointer. No information is returned by CLAIM. All registers except D0 are preserved. Each species to be loaded will be in the form of a binary "load module" of the following form. No header information or "resource fork" is allowed. (Two-byte integers are taken in BigEndian order.) N Species number 2 bytes S(N) Length 2 bytes G(N) Offset for start 2 bytes R No. of protected cells 2 bytes P(N,1) ... Offsets of protected ... cells (2 bytes each) 2R bytes P(N,R) T Length of identifying text 1 byte text Text to be displayed by the Umpire when this species is loaded T bytes prog The program itself S(N) bytes The assembly language source for one of the organisms would look something like the following. Spaces marked '****' are to be filled in by the author of the program. The five equates at the top will be added (automatically) to fit the particular Umpire to be used. ;myno equ 8 ; species number ;asize equ 32768 ; arena size ;probe equ -24 ; offsets from A6 ;kill equ -16 ; .. for the three ;claim equ -8 ; .. umpire calls length equ mytop-mybot ldmod: ; binary load module dc.w myno ; species number dc.w length ; length of program dc.w start-mybot ; offset for starting address dc.w (prote-prot)/2 ; number of protected cells prot: dc.w **** ; protected cells (offsets) dc.w **** prote: dc.b txte-txt ; length of text txt: dc.b "****" ; text displayed on loading txte: mybot: **** start: **** mytop: end Since copies of the program will be loaded here and there at random, the programs will either have to be relocatable or else make some adjustments on themselves when executed. ====================================================================== The Macintosh Umpire is a preliminary version. It works, but it has no resources, and no documentation. Perhaps there is a volunteer to write docs? Just follow the menus. (When you are finished loading, choose CANCEL.) ====================================================================== ; a sample DARWIN species for Macintosh (translated from the 8080) ; G. Edgar 19 April, 1987 ; five lines like the following will be added before assembly. ;myno equ 8 ; species number ;asize equ 32768 ; arena size ;probe equ -4 ;kill equ -8 ;claim equ -12 mysize equ mytop-mybot ldmod: ; binary load module dc.w myno ; species number dc.w mysize ; length of program dc.w start-mybot ; offset for starting address dc.w (prote-prot)/2 ; number of protected cells prot: dc.w 0,1,2,3,4 ; protected cells dc.w 20,21,22,23 dc.w 40,41,42,43 dc.w 60,61,62,63,64 dc.w 80,81,82,83 dc.w 100,101,102,103 prote: dc.b txte-txt ; length of text txt: dc.b " ** MOLE **" dc.b $0D,$0A dc.b " GAE; 22 April 1987" ds.w 0 ; assure even-numbered address ?? txte: ; Here is the actual code for this organism mybot: dc.l 0 ; storage location start: lea mybot,a5 ; for writing to this location move.l (a5),d0 andi.l #-2,d0 ; must be even move.l d0,a0 addq.l #2,a0 cmpa.l a6,a0 ; above the bottom of arena? bcc st1 move.l a6,a0 ; if not, use bottom st1: move.l #asize,a1 add.l a6,a1 ; top of arena cmpa.l a1,a0 ; below top of arena? bcs st2 move.l a6,a0 ; if not, use bottom st2: move.l a0,(a5) ; save for next time gprobe: move.b #myno,d0 jsr probe(a6) ; probe this location cmp.b #myno,d0 ; my own species? beq start ; if so, try again cmp.b #0,d0 ; empty? beq empty gkill: move.b #myno,d0 jsr kill(a6) ; if not, kill it empty: move.l a1,a0 ; bot sub.l a1,a2 ; space available cmpa.l #mysize,a2 ; enough for me? blt start ; if not, start again gclaim: move.b #myno,d0 jsr claim(a6) ; claim the space for me move.w #mysize-1,d1 move.l a5,a1 loop: move.b (a1)+,(a0)+ ; copy myself there dbf d1,loop bra start ; and start again mytop: end ====================================================================== May 2, 1987 G. Edgar CompuServe 70715,1324 1000 Urlin Ave gae@osupyr.UUCP Columbus, OH 43212 TS1871@OHSTVMA.bitnet