
SGB_13.net      CORE WARS

Steve's Guide for Beginners Iss 13 (v1)

Issue 10 analysed RAVE.red

Issue 11 looked at the MTS tournament utility
briefly.

Issue 12 investigated constants and tweaking of
warriors.

======

In issue 9, reference was made to replicators. I
have realised that I still don't have an
instinctive feel for it - despite the clear
explanation in Core Warrior.

To this end I intend here to investigate them -
with lots of core dumps to aid and abet.

======

Here is silk as presented in SGB_12.
;redcode-b
;name Silk
;author Lifted from Core Warrior # 1
;assert 1
OFFSET  equ     100
start   spl     1,      <1111
        mov     -1,     0
silk    spl.a   @0,     OFFSET
        mov.i   }silk,  >silk
        jmp.a   silk,   {silk
        end     start

The first task is to see what happens to the main
loop. To achieve that, I'll replace "silk spl.a"
by "silk nop.a" to only have the processes I want
to watch.

I'll also use cdb to generate core dumps:
"pm silk -e"            ;start pmars
write silk.log          ;open a logfile
edit 2                  ;change the spl.a ...
nop.a @0,$10            ;... to nop.a
@sk2~l pc~ec .~l 0,20   ;step 3, dump core
        ;repeat using ENTER several times

(CDB notes: "sk2" is step 3 because it skips 2
and then displays one - suppressed by the "@".
"l pc" lists the contents of the location pointed
to by the program counter. "ec ." echoes (prints)
a "." in the output log as a separator.)

I'm providing a core dump of locations 2..4 (the
core of SILK) after every three instructions
(because there are three processes running round
together). Whenever any other location in the
range 5..20 is altered I'll list 0..20. I'll mark
the location of the three processes with "<<<" and
any changed locations with "*".

After the first 3 cycles, we have three processes,
all about to execute NOP.A
00000   SPL.B  $     1, <  1111
00001   SPL.B  $     1, <  1111     * (was mov.i)
00002   NOP.A  @     0, $    10     <<<
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020

After three NOPs:
00002   NOP.A  @     0, $    10
00003   MOV.I  }    -1, >    -1     <<<
00004   JMP.A  $    -2, {    -2

After the three MOVs:
00000   SPL.B  $     1, <  1111
00001   SPL.B  $     1, <  1111
00002   NOP.A  @     3, $    13     *
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2     <<<
00005
00006
00007
00008
00009
00010
00011
00012   NOP.A  @     0, $    10     *
00013   MOV.I  }    -1, >    -1     *
00014   JMP.A  $    -2, {    -2     *
00015
00016
00017
00018
00019
00020

After JMP:
00002   NOP.A  @     0, $    13     <<<*
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2


After NOP (really the SPL):
00002   NOP.A  @     0, $    13
00003   MOV.I  }    -1, >    -1     <<<
00004   JMP.A  $    -2, {    -2

Another three MOVs:
00000   SPL.B  $     1, <  1111
00001   SPL.B  $     1, <  1111
00002   NOP.A  @     3, $    16     *
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2     <<<
00005
00006
00007
00008
00009
00010
00011
00012   NOP.A  @     0, $    10
00013   MOV.I  }    -1, >    -1
00014   JMP.A  $    -2, {    -2
00015   NOP.A  @     0, $    13     *
00016   MOV.I  }    -1, >    -1     *
00017   JMP.A  $    -2, {    -2     *
00018
00019
00020

Then:
00002   NOP.A  @     0, $    16     <<<*
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2

Then
00002   NOP.A  @     0, $    16
00003   MOV.I  }    -1, >    -1     <<<
00004   JMP.A  $    -2, {    -2

Then:
00000   SPL.B  $     1, <  1111
00001   SPL.B  $     1, <  1111
00002   NOP.A  @     3, $    19     *
00003   MOV.I  }    -1, >    -1
00004   JMP.A  $    -2, {    -2     <<<
00005
00006
00007
00008
00009
00010
00011
00012   NOP.A  @     0, $    10
00013   MOV.I  }    -1, >    -1
00014   JMP.A  $    -2, {    -2
00015   NOP.A  @     0, $    13
00016   MOV.I  }    -1, >    -1
00017   JMP.A  $    -2, {    -2
00018   NOP.A  @     0, $    16     *
00019   MOV.I  }    -1, >    -1     *
00020   JMP.A  $    -2, {    -2     *

And so on. You can see that each loop of the
original silk replicates silk in an adjacent area
of memory. This is ok because it is not
inefficiently copying it to the same location on
each loop; but bad beacuse they are all adjacent
and "overrunning core" would be better achieved by
spacing the copies out more.

======

Of course, while this is going on, the other half
of the processes generated by the SPL is
executing.

Some things to note.

Firstly each copy is created using a changing
offset. As each code segment runs it creates a
copy at an "offset" and that copy will run with
the same initial offset.

So there is a treelike structure for which
segment of code is generated by which other
segment: I'll draw part of the tree here,
identifying each segment of code by the location
of its SPL instruction and including in
parentheses beside it, the offset that it was
created with (that it used on its first
iteration).:

2 (10)
|---12 (10)
|   |---22 (10)
|   |   |---32 (10) etc
|   |   |---35 (13) etc
|   |   |---38 (16) ...
|   |   ----41 (19) ...
|   |---25 (13)
|   |   |---38 (13)
|   |   |---41 (16)
|   |   ----44 (19)
|   ----28 (16)
|       |---44 (16)
|       ----47 (19)
|---10 (13)
|   |---28 (13)
|   ----31 (16)
----18 (16) etc etc etc

With the basic silk, the segements are heavily
overlapping!

A particular segement of code starts at location:
2 + a*OFFSET + b*(OFFSET+STEP) + c*(OFFSET+2*STEP)
+ d*(OFFSET+3*STEP) + ...
where each of a,b,c,d... are integers ranging from
0 upwards.

Secondly, as the replications grow, the processes
interleave in a very complex fashion, they don't
queue up in neat bunches of three. As time passes,
the number of cycles between each process of a
triplet of processes will grow steadily further
apart.

To illustrate this, the spl instruction in the
main loop (location 2) and the first daughter
process (at location 12) is executed as cycle
numbers:
Location 2      Location 12
4,5,6           8,10,12
22,26,30        36,42,48
79,92,105       124,143,162
256,291,326     376,425,475
679,764,845     etc

Thirdly, SILK isn't really very good at killing
enemies. Yes it overruns them rapidly, but as it
stands there are no killing commands and the enemy
will just run SILK's code. Now since it is likely
that the enemy will be running it with the wrong
number of processes (not 3), it will run
malfunctioned.

This explains why one needs to add bombs and such
to SILK.

======

Back to Core Warrior #1. I quote "Simple
improvements are adding an add line so as copies
are not packed one near the other, and adding some
bombing to make it a bit nastier."

I reckon that's enough for one lot of reading. I
intend to look more at replicators in the next
issue. Probably at Paperone.

Comments - praise, criticism - welcome.

=== Steve Bailey 101374.624@compuserve.com
sgb@zed-inst.demon.co.uk
http://ourworld.compuserve.com/homepages/SGBailey
Work: Electronics Play: Go 2kyu.



