PREFACE

This part of introduction describes what and how the scanner warriors work. The scope in this document covers only classical scanners. Classical scanners are scanners that are designed to specifically catch paper style warriors by throwing self-splitting instructions. This includes two scanner prototypes: B-scanner and CMP-scanner. They are detailed in two separate parts. Comparison between scanners can be found afterward. Further details on other types of scanners can be obtained from various collection of articles in ftp.CSUA.berkeley.edu under directory pub/corewar/redcode.


Scanner prototypes

Scanner warriors are those that are configured to detect the presence of opponent before laying down their bombs on any suspicious locations. Aside from scanning, it is also important that the scanners are able to avoid messing up their own code.

There are two distinct prototypes for scanners. They are B-scanner and CMP-scanner. Their names were derived from their functions that do scanning. B-scanners detect their opponent by searching for any non-zero B-field in their code. CMP-scanners provide more rigid detection by comparing (CMP) for any non-identical instructions between two different locations. In the extent of their functional differences, both kinds of scanners avoid self-attack in interestingly different manner. (For further detail, see Comparison between B-scanners and CMP-scanners).

B-scanner

B-scanners assumes that at least one of their opponent code has non-zero value in their B-field.

One of B-scanners' duties might be as follow:

; ... B-scan ; ... throw self-splitting instructions ; ... redo before finish ; ... core-clear

B-scan

Its main instruction is: JMZ scan, ptr where scan refers to the scanning instructions and ptr refers to the current scanning location. The scanning instructions update the scanning pointer and test if it points to a non-zero B-field. The instructions might be: scan ADD #const, ptr JMZ scan, ptr During scanning phase, the scanner shouldn't be mistaken with any of its own codes. An easy way to do it is to add SLT after JMZ, e.g: scan ADD #const, ptr JMZ scan, ptr SLT #num, ptr ; num is number of codes... ; ...in-between ptr and last line

Throw self-splitting instructions

These are the two instructions: MOV jmp_i, @ptr MOV spl_i, <ptr spl_i refers to SPL 0 and jmp_i refers to JMP -1.

Redo before finish

Against replicator warriors or other warriors that execute more than one modules, it is neccessary to scan as many locations as possible before core-clearing. A simple test to see whether it has undergone a self-modification or not is sufficient. This test could be a single instruction: JMN scan, scan

Core-clear

This is to clear away all the opponent stunned processes and to convert tie into winning: SPL 0, 0 MOV dat_i, <-1 JMP -1, 0

Overall

Putting up together, here is the first version of B-scanner: This version uses SLT to avoid self-attack. ; name B-scanner 1 const EQU 3094 init EQU scan scan ADD #const, ptr ptr JMZ scan, ptr+init SLT #dat_i, ptr throw MOV jmp_i, @ptr MOV spl_i, <ptr ; pointer is decremented by 1 ADD #1, ptr ; needed to readjust the pointer redo JMN scan, scan spl_i SPL 0, 0 MOV dat_i, <-1 jmp_i JMP -1, 0 dat_i END scan Here is a much more elegant solution to B-scanner, blatantly taken from a successful classical B-scanner: B-scanner live in vain. ; name B-scanner 2 const EQU 2234 init EQU scan scan ADD #const, @2 JMZ scan, @ptr ; hit here throw MOV jmp_i, @ptr ptr MOV spl_i, <init+ptr redo JMN scan, scan spl_i SPL 0, 0 MOV dat_i, <-1 jmp_i JMP -1, 0 dat_i END scan The SLT instruction has been dropped off but this program performs much better. Note that the warrior scans in modulo 2 or one for every two instructions. Also note that the warrior structure is aligned such as the B-scanner will scan zero B-field in its own code. This is how it avoids winding up its own code. There is but one instruction: the second one that will be read as non-zero when it reads its own code. This instruction is the indicator for this warrior to begin its core-clear.

CMP-scanners

CMP-scanners detect the presence of opponent code by comparing (CMP) two instructions at different locations. One of '88 rules is that at loading time, all instructions other than those of two warriors are initialized with DAT $0, $0. When CMP-scanner finds two non-identical instructions, it knows that it is not comparing two DAT $0, $0. At least one of these two instructions is either an opponent code or a modified code. In both cases, CMP-scanner simply throws in self-splitting instructions at the concerned locations. The tricky part is to find out which one of the two potentially belongs to the opponent. Like B-scanner, it should also avoid any unintentional self-modification.

CMP-scanners might as well fall into two smaller divisions. Their difference is in the way they handle two non-identical instructions. Their choices are based on their scanning gap. The CMP-scanner with large/medium scanning gap assumes the following: "if it is not the first instruction, then the second one is part of opponent's". It then takes the next step (detailed below) to accomplish its duty. The other CMP-scanner (small scanning gap) assumes that they have touched the intersection of the opponent's code. It then throws in self-splitting instructions at all locations between the two locations it is comparing.

Most CMP-scanners have the following components:

; ... CMP-scan ; ... handle everything to do upon two non-identical instructions. ; ... redo before finish ; ... core-clear

CMP-scan

The standard instructions for this component: update ADD loc_mod, scan scan CMP loc, loc + gap avoid SLT #num, scan rescan JMP update, 0 The first instruction updates both A-field and B-field of scanning location. The second instruction does the scanning. The third instruction provides a mechanism to prevent damaging its own codes. The last instruction loops back to label update in the case of identical instructions. Most scanners use the form DJN update, <b-attack as their looping instruction.

Handle the next part after CMP-scan

One basic problem with CMP-scanners is that '88 doesn't have any A-field indirect references. Since CMP-scanners use both A-field and B-field as their scanning location, they should as well be able to inspect both pointed locations and to take the neccessary actions based on both fields. Not until then, their progress is incomplete.

Some solutions to the above problem are:
Bomb in-between the two locations.
MOV #gap, cnt ; the constant gap is known MOV spl_i, <scan cnt DJN -1, #cnt ADD #gap, scan ; re-adjust the B-field scan ptr
Bomb exactly at the two locations. (I)
MOV jmp_i, @scan ; on B-field MOV spl_i, <scan SUB #gap-1, scan ; now B-field scan has the same value... ; ... as A-field scan MOV jmp_i, @scan ; on A-field MOV spl_i, <scan ADD #gap+1, scan ;resume to B-field scan
Bomb at first location and re-enter the scanning phase with B-field now refers to A-field.
MOV jmp_i, @scan MOV spl_i, <scan ADD loc_mod2, scan
Due to the lengthy codes, the second method is rarely used. The first The first method is used by CMP-scanners based on Agony type warrior. The second method is rarely used due to its lengthy codes. The last method is used by Crimp type CMP-scanners.

The last method is intriguing to know. In normal scanning (instruction 1 - 4), both location pointers are updated as from E-F to C-D to A-B ... (below).

* * * * * * A B C D E F When it detects different instructions, e.g between E and F, it changes its scanning pointers as from E-F to D-E. The purpose is to provide way to access the A-Field.

Redo before finish

Like B-scanner, CMP-scanner intentionally bombs itself to indicate that it has finished its scanning phase. A single instruction does the trick: JMN update, update

Core-clear

A normal core-clear. The const value of MOV const, <const can be used as loc_mod constant.

Overall

Putting up together, here are the two versions of CMP-scanners: ; name CMP-scanner (small) ; name CMP-scanner (large) gap EQU 12 gap EQU 49 const EQU -28 const EQU -98 init EQU update+const init EQU update+const2 const2 EQU -49 update ADD loc_mod, scan update ADD loc_mod, scan scan CMP init-gap, init scan CMP init-gap, init SLT #last-update, scan SLT #last-update, scan rescan DJN update, <6000 rescan DJN update, <6000 MOV spl_i, <scan MOV jmp_i, @scan cnt DJN -1, #cnt MOV spl_i, <scan MOV #gap, cnt ADD mod_2, scan ADD #gap, scan redo JMN scan, scan redo JMN update, update spl_i SPL 0 spl_i SPL 0 mod_2 MOV const2, <const2+1 loc_mod MOV const, <const jmp_i JMP -1 last END scan loc_mod DAT #const, #const END scan

Comparison between B-scanners and CMP-scanners

Size
B-scanner is much smaller than CMP-scanner. The average B-scanner #lines of codes is 8. The average CMP-scanner #lines of codes is 12.
Scanning speed
CMP-scanner is generally faster than B-scanner. CMP-scanner scans two locations for every three instructions (67%) while B-scanner scans one location for every two instructions (50%).
Coverage
A success B-scan can cover exactly half size of the core before entering core-clear. A success CMP-scan can cover from half size to almost full size of the core depending on the spread of its opponents.
Additional offense and defense
B-scanner: B-protection. CMP-scanner: DJN stream plus B-protection.
Wasting on decoys
B-scanner wastes less cycles than CMP-scanner does on decoys spreaded by their opponents. Most CMP-scanners however avoid most decoys caused by opponent's DJN-stream.
Efficiency against stone
B-scanner performs better than CMP-scanner does.
Efficiency against paper
CMP-scanner performs better than B-scanner does.
Author: wangsawm@kira.csos.orst.edu