;; File: corewar.lisp ;; Roger Bellin, Spring 1998 ;; ;; An attempt to build a basic Core War/Redcode interpreter in Common Lisp, for use ;; in evolutionary programming. ;; ;; The Redcode specification used was taken from "Core War Encore" in Dewdney's book ;; _The Armchair Universe: An Exploration of Computer Worlds_ (W.H. Freeman & Co., 1988). ;; It differs only slightly (which argument is used for what function in some instructions, and ;; the JMG and SPL instructions) from the article _A Guide to Redcode_, available on the Internet. ;; Note that this is not a full implementation of the ICWS '94 or (I think) '88 specifications. ;; ;; For Hampshire College CCS 263, Artificial Intelligence. ;; Things that still need to be done: ;; Make a CoreWar pretty-printer. ;; Make a single function to initialize and run a battle, returning useful information. ;; Combine with MidGP and evolve programs! (defstruct instruction "A single Redcode instruction, with an opcode and two arguments (argument-a and argument-b). Defaults to DAT 0 0." (opcode 'dat) (argument-a 0) (argument-b 0)) (defstruct (immediate (:constructor make-immediate (value))) "An immediate value for use in arguments to Redcode instructions. Replaces '#'." value) (defstruct (indirect (:constructor make-indirect (value))) "An indirect value for use in arguments to Redcode instructions. Replaces '@'." value) (defstruct program "An entire program in Redcode - a list of instructions, and the relative address of the first one to execute." (start 0) (instruction-list nil)) (defconstant *core-size* 800 ;; typically 8000 or some larger number divisible by 4 "The number of virtual memory cells in the core battleground.") (defparameter *core* (make-array *core-size* :initial-element (make-instruction) :element-type 'instruction) "The actual core in which the programs will do battle. Initialized to empty data statements, with the programs loaded later.") (defun init-core () (setq *core* (make-array *core-size* :initial-element (make-instruction))) 'core-initialized) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Queue functions for the instruction queues, from Graham's _ANSI Common Lisp_. ;; A queue object here has its car pointing to the head of the queue and its cdr ;; pointing to the tail of the queue. enqueue and dequeue behave like push and pop. (defun make-queue () "Makes a new empty queue." (cons nil nil)) (defun enqueue (obj q) "Inserts obj at the tail of q, returning a list of the queue's contents (the car of the actual queue object)." (if (null (car q)) (setf (cdr q) (setf (car q) (list obj))) (setf (cdr (cdr q)) (list obj) (cdr q) (cdr (cdr q)))) (car q)) (defun dequeue (q) "Removes an object from q, returning it." (pop (car q))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defparameter *instruction-queue-1* (make-queue) "Program 1's instruction queue.") (defparameter *instruction-queue-2* (make-queue) "Program 2's instruction queue.") (defun init-queues () (setq *instruction-queue-1* (make-queue)) (setq *instruction-queue-2* (make-queue)) 'instruction-queues-initialized) (defmacro core+ (&rest numbers) "Adds numbers (presumably addresses or offsets) modulo *core-size*." `(mod (+ ,@numbers) ,*core-size*)) (defmacro core- (number &rest more-numbers) "Subtracts one or more numbers (presumably addresses/offsets) modulo *core-size*." `(mod (- ,number ,@more-numbers) ,*core-size*)) (defun load-program (pgm addr instr-queue) "Loads a program into *core* at a given address, enqueueing the address of its first instruction in the given queue." (do* ((i 0 (+ i 1)) (instr (car (program-instruction-list pgm)) (nth i (program-instruction-list pgm)))) ((null instr)) (setf (svref *core* (core+ addr i)) (copy-instruction instr))) (enqueue (core+ addr (program-start pgm)) instr-queue)) (defun setup-battle (pgm1 pgm2) "Loads two programs into the core at random, non-conflicting addresses, enqueueing the addresses of their first instructions. Assumes that the core and the two instruction queues are initialized." (let ((address1 (random *core-size*)) (address2 (random *core-size*))) (if (or (< address1 address2 (+ address1 (length (program-instruction-list pgm1)))) (< address2 address1 (+ address2 (length (program-instruction-list pgm2))))) (setup-battle pgm1 pgm2) ;; Try new random numbers via a recursive call. (progn (load-program pgm1 address1 *instruction-queue-1*) (load-program pgm2 address2 *instruction-queue-2*) 'programs-loaded)))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun valid-instruction-p (instr) "Predicate function which checks the validity of a Redcode instruction's opcode." (member (instruction-opcode instr) '(mov add sub jmp jmz jmg djz cmp spl dat))) (defun resolve-address (arg absolute-addr) "Takes a relative or an indirect address along with the absolute address of the instruction from which the argument was taken; returns the absolute address referred to. (If given an immediate address, simply returns the corresponding absolute address.)" (declare (absolute-addr fixnum)) (cond ;; Unlimited indirection is allowed, for now: An indirect address can refer to another indirect address, ;; and so forth indefinitely. ((indirect-p arg) (resolve-address (instruction-argument-b (svref *core* (core+ (indirect-value arg) absolute-addr))) (core+ (indirect-value arg) absolute-addr))) ((immediate-p arg) (immediate-value arg)) ((numberp arg) (core+ arg absolute-addr)))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; The main battle loop function, with other useful top-level stuff. (defconstant *max-iterations-per-battle* 80000) (defun run-corewar (&optional noisy) "Run a Core War battle by executing instructions in the core, pointed to by the two instruction queues. Assumes that the core and the two queues have been initialized, and the competing programs loaded into the core, with their first addresses to execute enqueued in each queue." (let ((address-1 (dequeue *instruction-queue-1*)) (address-2 (dequeue *instruction-queue-2*))) (do ((iterations 0 (+ iterations 1))) ((or (null address-1) (null address-2) (= iterations *max-iterations-per-battle*)) (cond ((null address-1) (if noisy (format t "Program 2 wins!~%")) (list 'program-2-wins iterations)) ((null address-2) (if noisy (format t "Program 1 wins!~%")) (list 'program-1-wins iterations)) (t (if noisy (format t "Time has run out. It's a tie.")) (list 'tie iterations)))) (if noisy ;; Print the instructions being executed currently. (let ((instr-1 (svref *core* address-1)) (instr-2 (svref *core* address-2))) (format t "~A: ~A ~A ~A ~20T ~A: ~A ~A ~A~%" address-1 (instruction-opcode instr-1) (instruction-argument-a instr-1) (instruction-argument-b instr-1) address-2 (instruction-opcode instr-2) (instruction-argument-a instr-2) (instruction-argument-b instr-2)))) (eval-redcode address-1 *instruction-queue-1*) (eval-redcode address-2 *instruction-queue-2*) (setq address-1 (dequeue *instruction-queue-1*)) (setq address-2 (dequeue *instruction-queue-2*))))) (defun init-corewar (pgm1 pgm2) "Initializes the core and the instruction queues, and loads the programs into the core." (init-core) (init-queues) (setup-battle pgm1 pgm2)) (defun run-battle (pgm1 pgm2) "Initialize and run a battle between two programs, returning the information returned by run-corewar." (init-corewar pgm1 pgm2) (run-corewar)) (defun arg-type-char (arg) "Returns the character denoting its argument's addressing mode in traditional CoreWar notation (a space if it's an ordinary argument)." (cond ((immediate-p arg) #\#) ((indirect-p arg) #\@) (t #\Space))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A single-instruction evaluator. (defun eval-redcode (address instr-queue) "Evaluates the instruction at a given address by calling an instruction-specific evaluator." (declare (number fixnum)) (let ((instr (svref *core* address))) (cond ((not (valid-instruction-p instr)) nil) ((equal (instruction-opcode instr) 'mov) (eval-mov instr address instr-queue)) ((equal (instruction-opcode instr) 'add) (eval-add instr address instr-queue)) ((equal (instruction-opcode instr) 'sub) (eval-sub instr address instr-queue)) ((equal (instruction-opcode instr) 'jmp) (eval-jmp instr address instr-queue)) ((equal (instruction-opcode instr) 'jmz) (eval-jmz instr address instr-queue)) ((equal (instruction-opcode instr) 'jmg) (eval-jmg instr address instr-queue)) ((equal (instruction-opcode instr) 'djz) (eval-djz instr address instr-queue)) ((equal (instruction-opcode instr) 'cmp) (eval-cmp instr address instr-queue)) ((equal (instruction-opcode instr) 'spl) (eval-spl instr address instr-queue)) ((equal (instruction-opcode instr) 'dat) nil)))) ;; Instruction-specific evaluators. Note that ill-formed instructions (or execution of a DAT) ;; do not cause errors, but simply die, effectively killing the process that executed them, so ;; a program's other threads keep going after an error. (defun eval-mov (instr address instr-queue) "Evaluates a MOV instruction, enqueueing the next address." (declare (instr instruction) (address fixnum)) (let ((a (instruction-argument-a instr)) (b (instruction-argument-b instr))) (if (immediate-p b) nil ;; Die on an ill-formed instructions. (let ((destination-address (resolve-address b address))) (if (immediate-p a) (setf (svref *core* destination-address) (make-instruction :argument-b (immediate-value a))) (setf (svref *core* destination-address) (copy-instruction (svref *core* (resolve-address a address))))) (enqueue (core+ address 1) instr-queue))))) (defun eval-add (instr address instr-queue) "Evaluates an ADD instruction, enqueueing the next address." (declare (instr instruction) (address fixnum)) (let ((a (instruction-argument-a instr)) (b (instruction-argument-b instr))) (if (immediate-p b) nil ;; Die on ill-formed instructions. (let ((destination-address (resolve-address b address))) (cond ((and (immediate-p a) (numberp (instruction-argument-b (svref *core* destination-address)))) (setf (instruction-argument-b (svref *core* destination-address)) (core+ (instruction-argument-b (svref *core* destination-address)) (immediate-value a))) (enqueue (core+ address 1) instr-queue)) ((and (numberp (instruction-argument-b (svref *core* destination-address))) (numberp (instruction-argument-b (svref *core* (resolve-address a address))))) (setf (instruction-argument-b (svref *core* destination-address)) (core+ (instruction-argument-b (svref *core* destination-address)) (instruction-argument-b (svref *core* (resolve-address a address))))) (enqueue (core+ address 1) instr-queue)) (t nil)))))) ;; Die when adding to immediate/indirect values. (defun eval-sub (instr address instr-queue) "Evaluates a SUB instruction, enqueueing the next address." (declare (instr instruction) (address fixnum)) (let ((a (instruction-argument-a instr)) (b (instruction-argument-b instr))) (if (immediate-p b) nil ;; Die on ill-formed instructions. (let ((destination-address (resolve-address b address))) (cond ((and (immediate-p a) (numberp (instruction-argument-b (svref *core* destination-address)))) (setf (instruction-argument-b (svref *core* destination-address)) (core- (instruction-argument-b (svref *core* destination-address)) (immediate-value a))) (enqueue (core+ address 1) instr-queue)) ((and (numberp (instruction-argument-b (svref *core* destination-address))) (numberp (instruction-argument-b (svref *core* (resolve-address a address))))) (setf (instruction-argument-b (svref *core* destination-address)) (core- (instruction-argument-b (svref *core* destination-address)) (instruction-argument-b (svref *core* (resolve-address a address))))) (enqueue (core+ address 1) instr-queue)) (t nil)))))) ;; Die when subtracting from immediate/indirect values. ;; I have permitted immediate values to be used by all control-transfer instructions as ;; absolute addresses. (This isn't very useful for coding.) Also, the instructions that ;; involve comparison may use immediate values for comparison. (defun eval-jmp (instr address instr-queue) "Evaluates a JMP instruction." (declare (instr instruction) (address fixnum)) (let ((a (instruction-argument-a instr))) (if (immediate-p a) (enqueue (immediate-value a) instr-queue) (enqueue (resolve-address a address) instr-queue)))) (defun eval-jmz (instr address instr-queue) "Evaluates a JMZ (jump if zero) instruction." (declare (instr instruction) (address fixnum)) (let* ((b (instruction-argument-b instr)) (b-value (if (immediate-p b) (immediate-value b) (instruction-argument-b (svref *core* (resolve-address b address)))))) (if (not (numberp b-value)) nil (if (= b-value 0) (eval-jmp instr address instr-queue) (enqueue (core+ address 1) instr-queue))))) (defun eval-jmg (instr address instr-queue) "Evaluates a JMG (jump if greater than 0) instruction." (declare (instr instruction) (address fixnum)) (let* ((b (instruction-argument-b instr)) (b-value (if (immediate-p b) (immediate-value b) (instruction-argument-b (svref *core* (resolve-address b address)))))) (if (not (numberp b-value)) nil (if (> b-value 0) (eval-jmp instr address instr-queue) (enqueue (core+ address 1) instr-queue))))) (defun eval-djz (instr address instr-queue) "Evaluates a DJZ (decrement, then jump if zero) instruction." (declare (instr instruction) (address fixnum)) (let* ((b (instruction-argument-b instr)) (b-value (if (immediate-p b) (immediate-value b) (instruction-argument-b (svref *core* (resolve-address b address)))))) (if (numberp b-value) ;; Die on ill-formed instructions - can't decrement a non-numeric value. (progn (if (immediate-p b) (setf (immediate-value b) (core- b-value 1)) (setf (instruction-argument-b (svref *core* (resolve-address b address))) (core- b-value 1))) (if (= b-value 1) (eval-jmp instr address instr-queue) (enqueue (core+ address 1) instr-queue))) nil))) (defun eval-cmp (instr address instr-queue) "Evaluates a CMP (compare, skip next if not equal) instruction." (declare (instr instruction) (address fixnum)) (let* ((a (instruction-argument-a instr)) (b (instruction-argument-b instr)) (a-value (if (immediate-p a) (immediate-value a) (instruction-argument-b (svref *core* (resolve-address a address))))) (b-value (if (immediate-p b) (immediate-value b) (instruction-argument-b (svref *core* (resolve-address b address)))))) (if (and (numberp a-value) (numberp b-value)) (if (= a-value b-value) (enqueue (core+ address 1) instr-queue) (enqueue (core+ address 2) instr-queue)) nil))) (defun eval-spl (instr address instr-queue) "Evaluates a SPL (split execution to next address and address A) instruction." (declare (instr instruction) (address fixnum)) (let ((a (instruction-argument-a instr))) (enqueue (core+ address 1) instr-queue) (if (immediate-p a) (enqueue (immediate-value a) instr-queue) (enqueue (resolve-address a address) instr-queue)))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Sample programs from A.K. Dewdney's original _Scientific American_ article on Core War. (setq imp (make-program :instruction-list (list (make-instruction :opcode 'mov :argument-b 1)))) (setq dwarf (make-program :start 1 :instruction-list (list (make-instruction :argument-b -1) (make-instruction :opcode 'add :argument-a (make-immediate 5) :argument-b -1) (make-instruction :opcode 'mov :argument-a (make-immediate 0) :argument-b (make-indirect -2)) (make-instruction :opcode 'jmp :argument-a -2)))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; I wasn't sure how to further optimize the code, so I just added the line below. ;;(proclaim '(optimize (speed 3) (safety 0))) :corewar-loaded ;; Evaluate this to set up for a battle between the Dwarf and the Imp. ;; Then evaluate this to run a battle between them and see each instruction. ;; (init-corewar imp dwarf) ;; (run-corewar t) ;; Or evaluate this for a quick battle. ;; (run-battle imp dwarf)