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