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 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-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
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
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.
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
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
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 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
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.
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.
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
A normal core-clear. The const value of MOV const, <const can
be used as loc_mod constant.
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
- 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