Philosophy of the Scanner:
by John Metcalf

In Corewar, a battle program will execute either one, or multiple copies of itself. A program which is running just one copy will often lose the round after a single successful attack against it. A program which has multiple copies will not be beaten until each of these copies has been successfully dealt with.

A battle program which is continually creating new copies of itself is described as a replicator. No program can hope to attack copies of a replicating program sufficiently fast enough to keep up with the new copies which are constantly being spawned.

The only practical solution is to use a two stage attack. First, slow the rate at which the replicator is producing new copies. Next, destroy all copies of the opponent program while they are incapacitated.

The manner in which a replicator can be slowed is by making it split off useless processes. We achive this by overwriting it with, or otherwise forcing it to execute, SPL instructions.

Modern replicators spend approaching 50% of their time splitting off new processes, so we will need several consecutive SPL instructions to have any chance of being effective. The number of cycles to place these is considerable - compared, for example, to the time taken to drop single bombs.

Before spending a substantial number of cycles, it would make sense to check the area we are about to wipe contains an opponent, rather than empty core. This is precisely what a scanner is designed to do:

1) look for an area of core which potentially contains an opponent,

2) attack the selected area with a stun attack to slow the opponent,

3) repeat from step 1, until an implementation determined point,

4) the end-game - change the means of attack from stun to destroy.

Let us take a closer look at each of these stages:

Typical Scan Loops:

First, our scanner will look through core for a location which differs from empty core. If we are lucky, this will contain an active copy of the opponent. Alternatively, it may have been bombed by the opponent.

Scan loops come in a variety of speeds. The ratio of scanner size to scan speed can make a big difference to the effectiveness of a warrior. A small/fast scanner will find and attack a bigger/slower opponent more frequently than that opponent finds and attacks it. It is therefore desirable to have the lowest possible value of size/speed.

The example code in this section is labelled in a manner consistent with a great deal of published code. Conventions used are:

 * scan  - the top of the scan loop, and the entry point for our examples.
           Would ptr be a better entry point to the scan loops below?  Why?

 * ptr   - the instruction holding either one or two pointers to the
           location(s) to be scanned.

 * inc   - an instruction holding the constant 'step' in both fields, so a
           single ADD instruction can update two pointers.

 * step  - the distance between two scanned locations.  Some important
           literature on 'good' scan steps is listed below in Suggested Reading.

 * hop   - certain scanners look at two locations which are close to each
           other.  When something is found, they use an attack which covers both
           locations.  Hop is the distance between such a pair of locations.

 * start - the first location to be scanned.  Often chosen to maximise the
           length of time before the scanner detects itself.

Some examples of the most common forms of scan loop follow:

The .5c Scan Loop:

The simplest, with a comparatively poor size/speed ratio. Upgrade from a .5c loop to .66c for a guaranteed improvement. Instructions with zero a & b fields such as SPL #0,0 are invisible to the f-scan used here.

scanA   ADD     #step,          ptrA
ptrA    JMZ.F   scanA,          start  ; scan 1 location every 2 cycles

The .66c Scan Loop:

For scanners up to length 8, .66c provides the optimal ratio. The data at incB will usually be combined with another instruction. For example, in Blur 2 the data is held in the SPL above the clear.

Having two scan pointers is one disadvantage of this loop. When the scan triggers it is neccessary to either determine which pointer holds the location to be attacked, or else attack both.

An effective variation is to change the JMP instruction to DJN, to colour core against other scanners. Use something similar to DJN.F scanB,<-500 to create a sequential decoy, or alternatively decrement through your scan pointer with DJN.F scanB,@ptrB.

scanB   ADD     incB,           ptrB
ptrB    SNE     start+hop,      start  ; scan 2 locations every 3 cycles
        JMP     scanB
      ; ...
incB    DAT     step,           step

The .75c Scan Loop:

It gives the optimal size/speed ratio for scanners between 9 and 15 instructions. The location at which something has been found is held in the b-field of ptrC. As with the .5c scan, instructions with zero a & b fields are invisible. If we re-enter the scan loop, the pointers need to be reset; MOV.BA ptrC,ptrC should do the trick.

It appears at first glace, if the SNE detects something through it's a-field, the scan loop will not drop through into the attack phase. Stepping through the code however, reveals how some simple arithmetic 'copies' the value from the a-field of ptrC to the b-field. The scan loop can then drop through with the b-field of ptrC pointing to whatever has been found.

scanC   ADD     incC,           ptrC
ptrC    SNE.X   start,          start  ; scan 3 locations every 4 cycles
        ADD.X   incC,           ptrC
        JMZ.F   scanC,          @ptrC
      ; ...
incC    DAT     2*step,         step

The .8c Scan Loop:

Ideal for scanners of more than 16 instructions, this extension to the basic .66c loop has the same disadvantage of two scan pointers. As with it's slower relative, changing the JMP to a DJN proves effective against other scanners.

scanD   ADD     incD,           ptrD
ptrD    SNE     start+hop,      start  ; scan 4 locations every 5 cycles
        ADD     incD,           ptrD
        SNE     *ptrD,          @ptrD
        JMP     scanD
      ; ...
incD    DAT     step,           step

Common Forms of Offense:

Once the scanner has found something, what comes next? We hit it. We hit it hard with a stun attack intended to bring the enemy's processes to a virtual stand-still. There are four main types of offense to consider:

 * Permanent - a.k.a.  one-shots.  Switch to a core-clear with one or more
   SPL passes though core, beginning with the location found by the scan.
   After this, the clear wipes with DAT.  Simple and effective.  
   See Scanny Boy for an example.

 * Fixed Length - switch to a fixed length attack.  Afterwards, switch back
   to scanning.  The two most common types of fixed length attacks are SPL
   carpets and special bombs (stun and incendiary for example).  Take a look
   at Rave and The Marsupial Lion, which use these techniques.

 * Variable Length - switch to a linear SPL wipe beginning at the location
   where the scan detected something, continuing until it reaches empty core.
   After this, switch back to scanning.  This technique proves the most
   effective against paper/imps.  Check He Scans Alone for a good example.

 * Ongoing - a linear SPL wipe runs parallel to the scan.  When something is
   found by the scan, the pointer for the SPL wipe is adjusted to point to
   the scanned location.  However, the most common implementation of this
   technique introduces an extra instruction to the scan loop, reducing the
   speed.  Blur 2 is a clear example of an ongoing attack.

The scanner needs somehow to ensure it doesn't attack itself. One way to achieve this is to check the scan pointer isn't within a range which points to our scanner before attacking. Other alternatives are to use a scan pattern which avoids detecting the scanner, or using some means of hiding the scanner from itself (reflections).

The Switch:

Perhaps the trickiest requirement is the need to implement a switch from the attack to the end-game. The one-shot avoids this altogether by entering the end-game as soon as something is found. In a traditional scanner however, we have a choice to make:

 * When our scanner detects itself either once, or a number of times, enter
   the end-game.  For example Mini HSA switches after 16 self-scans.

 * After a number of iterations of the scan loop, drop through to the end
   game.  In Blur 2, there is a counter which is decremented by the scan
   loop.  When this reaches zero, control will pass into the end-game.
   
 * After a number of iterations of the attack, drop through to the end game.
   In Dandelion III, there is a counter which is decremented if the scanner
   attacks something.  When this reaches zero, control will pass into the 
   end-game.

 * Switch when a pre-determined location is altered by the attack.  See
   myZizzor for an example, which has a small decoy the scanner detects and
   attacks, thus altering the checked location.

The End-Game:

After our scanner has completed it's main attack phase, what next? It needs to dispose of the enemy processes we've worked so hard to stun. The two most effective methods are:

 * Clear - switch to a core-clear, which wipes core with DAT.  Optionally,
   the clear may wipe with SPL prior to the DAT wipe.  The most often seen
   type clear is the d-clear, with spiral clears also being a popular choice.
   Scanners containing a spiral clear include Eggbeater, Memories, SETI and
   Win!

 * DAT Switch - the scan continues, bombing with DAT instead of it's previous
   attack.  Many of the HSA-style warriors work in this way, including Mini
   HSA.  Another example is the scanner from Enough is Enough!

Suggested Reading:

A selection of material discussing step sizes can be found in Push Off 07 September 1993, Core Warrior #11, and Mathematical Models for Step Sizes (Morrell 1996). Stefan Strack provides a useful tool for finding good step sizes, mOpt v1.2, for which there is a tutorial in Core Warrior #32.

Below are some references to a few instructive examples of scanners. These illustrate the methods discussed above. Generally, those which function in a similar manner are grouped together, with the most readable example in the group listed first:

Blur 2 by Anton Marsden (CW36) - implements an ongoing attack from the scan loop, followed up by a d-clear end-game. After reading Blur 2, continue with Hazy Lazy, Silver Talon, Stalker, Eggbeater (CW46) and the scanner from Enough is Enough! (CW79).

HAL 9000 by Justin Kao (CW50) - an alternative means of implementing an ongoing attack, or scan directed clear.

Mini HSA from Electric Head by Anton Marsden (CW59) - provides an excellent introduction to the workings of HSA. Scanning continues into the end-game, with the SPL wipe becoming a DAT wipe. Also, check He Scans Alone, Mischief (CW80) and Razor.

Beholder's Eye v1.7 by W. Mintardjo - an easy to read spl/jmp bomber. Continue reading with Iron Gate (CW19), Harmony II and Memories (CW19).

myZizzor by Magnus Paulsson - performs a variable length attack, followed by a SPL / DAT clear.

Origin of Storms by John Metcalf (CW86) - a variable length attack realized in the scan loop, followed by the ever-present d-clear.

Rave 4.1 by Stefan Strack - a good example of a .66c scan with a fixed length SPL carpet. Also, you should take a look at SETI. Next study Win! and Recon 2, two warriors based on the same concept, employing an abundance of effective techniques.

Scanny Boy by David van Dam (CW29) - drops straight through from the scan loop into the end-game's SPL / DAT clear and provides a good example of a one-shot. See also Tiny BiShot 2.0, The Bloodhound, G2 and Phantasm 50.