Sections
Home
Hills
Infinite Hills
Tournaments
Software
Evolving
Optimizer
Community
Newsletter
Discussion
History
Sections
 
For Beginners
First Steps
FAQ
Guides
Lexicon
Benchmarks
For Beginners
> Home > The Corewar Newsletters > Core Warrior > Issue #1

Issue 70                                                       4 February, 1999
_______________________________________________________________________________
Core Warrior is a newsletter promoting the game of corewar. Emphasis is placed
on the most active hills - currently the '94 draft hill, the beginner hill and
the '94 no-pspace hill. Coverage will follow where ever the action is. If you
haven't a clue what I'm talking about then check out these five-star internet
locals for more information:

FAQs are available from:
  ftp://rtfm.mit.edu/pub/usenet/news.answers/games/corewar-faq.Z
  http://www.koth.org/corewar-faq.html

The ftp site and mirrors are at:
  ftp://ftp.csua.berkeley.edu/pub/corewar
  ftp://ftp.inria.fr/INRIA/Projects/para/doligez/cw/mirror
  ftp://www.koth.org/corewar

pMARS itself is also available from:
  http://www.koth.org/pmars.html             ;Stormking
  http://www.ncs.infi.net/~wtnewton/corewar  ;Terry's web page
  ftp://members.aol.com/ofechner/corewar     ;Fechner ftp site

Web pages are at:
  http://www.koth.org/                       ;Stormking
  http://www.ecst.csuchico.edu/~pizza/koth   ;Pizza
  http://para.inria.fr/~doligez/corewar      ;Planar

Newbies should check the Stormking page for the FAQ, language specification,
guides, and tutorials. Post questions to rec.games.corewar. All new players
are infinitely welcome!

A collection of Bezzi's hints in the first issues is available at:
  ftp://ftp.volftp.vol.it/pub/pc/msdos/games/solutions/bbhints.zip
_______________________________________________________________________________
Welcome...

Apologies for the many weeks which have passed since last issue. Fortunately
though, they have not been entirely uneventful. Ian Oversby's Autumn/Winter
tournament has begun, Macrae has successfully destroyed the deadlock on the
multi-warrior hill, and a selection of quality redcode has been published.

This issue - David Moore introduces the P^3 switcher and the code of Zooom,
the current '94nop king is revealed.

-- John Metcalf
_______________________________________________________________________________
Current Status of the Internet Pizza Server ICWS '94 Draft Hill:

Hill Specs:
         coresize: 8000
   max. processes: 8000
         duration: after 80,000 cycles, a tie is declared.
max. entry length: 100
 minimum distance: 100
    rounds fought: 200
  instruction set: ICWS '94 Draft

 #   %W /  %L /  %T                       Name               Author Score  Age
 1  45.5/ 34.2/ 20.2    Diamonds and more Rust    Christian Schmidt 156.8    3
 2  39.1/ 25.5/ 35.4                  Recovery          Ian Oversby 152.6   22
 3  43.5/ 36.8/ 19.6             Recycled Bits          David Moore 150.3   40
 4  45.7/ 42.4/ 11.9                      Win!          David Moore 148.9   16
 5  35.1/ 26.8/ 38.0          The Stormbringer    Christian Schmidt 143.4   32
 6  34.5/ 26.8/ 38.6                 Brigadeer     M Joonas Pihlaja 142.2   21
 7  35.9/ 30.6/ 33.6                      Vain          Ian Oversby 141.1  126
 8  34.6/ 28.4/ 37.0   Three Queens and a King    Christian Schmidt 140.7    1
 9  32.5/ 24.3/ 43.2                 Fragility         John Metcalf 140.7    5
10  27.8/ 15.7/ 56.5                  Fugitive          David Moore 140.0   80
11  34.7/ 30.0/ 35.3                     Vigor         Ken Espiritu 139.4  114
12  37.6/ 36.3/ 26.1                  Defender          Ian Oversby 138.8   34
13  40.6/ 42.4/ 17.0                  Zooom...         John Metcalf 138.8   18
14  38.5/ 38.3/ 23.1               myVamp v3.7             Paulsson 138.7   27
15  38.0/ 37.5/ 24.5                   Trefoil        Steve Gunnell 138.5    1
16  32.6/ 27.2/ 40.2                      Newt          Ian Oversby 138.1  204
17  34.3/ 30.8/ 35.0                     Fixed         Ken Espiritu 137.7  110
18  33.0/ 28.2/ 38.8                    Shadow    Christian Schmidt 137.7   31
19  28.9/ 20.1/ 51.0       Three Men in a Boat     M Joonas Pihlaja 137.7   33
20  33.1/ 29.6/ 37.4         Benj's Revene 1.0        Robert Macrae 136.6   28
21  39.7/ 43.1/ 17.2                 Blurstone        M. J. Pihlaja 136.2   50
22  32.3/ 29.5/ 38.2         Tuesday Afternoon             John K W 135.1   54
23  41.8/ 49.5/  8.7             He Scans Anew              P.Kline 134.1    4
24  37.7/ 42.0/ 20.3                    Bee/7i         John Metcalf 133.3    2
25  33.1/ 33.7/ 33.2              Fire and Ice          David Moore 132.6   99

Age since last issue: 33 ( 13 last issue, 7 the issue before )
New warriors: 14  Turnover/age rate 42%
Average age: 46 ( 36 last issue, 34 the issue before )
Average score: 140 ( 138 last issue, 134 the issue before )
The top 25 warriors are represented by just 11 independent authors: Schmidt,
Oversby and Moore with 4, Pihlaja and Metcalf with 3, Espiritu with two and
the rest with one each.

Christian Schmidt claims first place with his Diamonds and more Rust, which
is achieving 60%+ wins against stone/imps Newt, Vain and Brigadeer.
_______________________________________________________________________________
94 - What's New (Sorted by rank and score)

 #   %W /  %L /  %T                       Name               Author Score  Age
 1  44.4/ 38.0/ 17.6          Silver Talon 1.2                Edgar 150.7    0
 2  44.7/ 33.2/ 22.1    Diamonds and more Rust    Christian Schmidt 156.1    0
 2  34.7/ 24.5/ 40.8          The Stormbringer    Christian Schmidt 144.9    0
 2  33.2/ 22.8/ 44.0                 Brigadeer     M Joonas Pihlaja 143.5    0
 3  34.1/ 26.4/ 39.5                  Recovery          Ian Oversby 141.8    1
 3  38.4/ 36.6/ 25.0            Digital Dragon    Christian Schmidt 140.2    0
 5  40.0/ 40.5/ 19.6                  Zooom...         John Metcalf 139.5    1
 6  41.2/ 44.3/ 14.5                      Win!          David Moore 138.2    0
 6  40.5/ 43.4/ 16.1              Have No Pity         John Metcalf 137.6    1
 9  41.6/ 49.5/  8.8             He Scans Anew              P.Kline 133.8    1
 9  28.0/ 22.7/ 49.3                 Fragility         John Metcalf 133.3    1
 9  31.3/ 29.8/ 38.9   Three Queens and a King    Christian Schmidt 132.8    0
10  36.4/ 39.8/ 23.8               myVamp v3.7             Paulsson 133.0    0
11  31.2/ 28.4/ 40.4        Benj's Revenge 1.0        Robert Macrae 133.9    1
11  35.3/ 38.5/ 26.1                   Trefoil        Steve Gunnell 132.1    1
12  37.7/ 42.5/ 19.8                     Erase         Ken Espiritu 132.8    1
15  24.4/ 18.0/ 57.6       Three Men in a Boat     M Joonas Pihlaja 130.8    1
??  ??.?/ ??.?/ ??.?                   Khayman          Ian Oversby ???.?    1
17  30.0/ 32.1/ 37.9               Liquid Fire    Christian Schmidt 127.8    1
19  35.6/ 42.5/ 21.9                    Bee/7i         John Metcalf 128.7    1
20  35.6/ 43.2/ 21.2           Recycled Bits--          David Moore 128.0    1
21  34.8/ 41.7/ 23.5               BiShot v1.0    Christian Schmidt 127.9    1
21  22.0/ 17.9/ 60.1                Redemption         John Metcalf 126.2    1
22  34.7/ 42.5/ 22.9                    Z-Shot         John Metcalf 126.8    1
22  30.4/ 34.4/ 35.1                    bomber                   dm 126.4    1
22  20.8/ 16.7/ 62.5                      Glok             Ben Ford 124.9    0
23  26.1/ 27.2/ 46.7              The Yokozuna    Christian Schmidt 125.1    1
24  32.6/ 42.3/ 25.0                 Z-Shot II         John Metcalf 123.0    1
25  32.8/ 42.6/ 24.6              Sand-Crawler         John Metcalf 122.9    1

Several strong new entries ensured warriors surviving from last issue have
had a struggle to retain their rank. A few beginners have joined the elite.
_______________________________________________________________________________
94 - What's No More (Sorted by age)

 #   %W /  %L /  %T                       Name               Author Score  Age
26  27.4/ 30.1/ 42.5             Ultraviolet-B         Ken Espiritu 124.7  120
26  31.6/ 39.4/ 29.0               Digitalis 4    Christian Schmidt 123.8   73
26  22.1/ 20.5/ 57.4 Return Of Return Of The J             John K W 123.6   63
26  30.7/ 38.5/ 30.8                     Shape    Christian Schmidt 123.0   39
26  33.9/ 44.3/ 21.8           Electric Head 2        Anton Marsden 123.4   34
26  32.7/ 40.9/ 26.4            The Body Guard          Ian Oversby 124.5   27
26   ?.?/  ?.?/  ?.?                     Alien    Christian Schmidt   ?.?   26
26  ??.?/ ??.?/ ??.?                    Eraser         Ken Espiritu ???.?   23
26  34.6/ 44.6/ 20.8      Diamonds and Rust v2    Christian Schmidt 124.5   23
26  29.6/ 40.3/ 30.1            Digital Dragon    Christian Schmidt 118.9   18
26  35.7/ 47.5/ 16.7              Have No Pity         John Metcalf 123.9   16
26  ??.?/ ??.?/ ??.?            Nine Seven Six           M R bremer ???.?   14
26  23.5/ 21.3/ 55.3                Redemption         John Metcalf 125.7   14
26  33.2/ 41.4/ 25.4               BiShot v1.0    Christian Schmidt 125.0   13
26   ?.?/  ?.?/  ?.?              Silver Talon                Edgar   ?.?   12
26  20.0/ 19.9/ 60.1                      Glok             Ben Ford 120.2   11
26  34.3/ 47.4/ 18.3                     Erase         Ken Espiritu 121.1    9
26  28.5/ 36.8/ 34.7                     C I A         Anders Ivner 120.3    8
26  26.6/ 29.6/ 43.8                    Gigolo   Core Warrior staff 123.6    7
26  29.9/ 36.1/ 34.0                   Khayman          Ian Oversby 123.6    5
26  33.4/ 43.7/ 22.9           Recycled Bits--          David Moore 123.2    5
26   1.6/  0.7/  1.7               Liquid Fire    Christian Schmidt   6.5    5
26  30.7/ 45.8/ 23.5                    Z-Shot         John Metcalf 115.7    4
26  29.7/ 43.5/ 26.8                 Z-Shot II         John Metcalf 115.8    4
26  ??.?/ ??.?/ ??.?                 Tornado 4          Beppe Bezzi ???.?    3
26  ??.?/ ??.?/ ??.?               Falcon v0.5          Ian Oversby ???.?    2
26  25.4/ 28.0/ 46.6              The Yokozuna    Christian Schmidt 122.9    2
26  29.5/ 35.8/ 34.7                    bomber                   dm 123.2    2
26  30.6/ 44.8/ 24.5              Sand-Crawler         John Metcalf 116.4    2

Ultraviolet is lost shortly after entering the New HoF. Old adversaries
Digitalis and the Jedimp are also pushed off.
_______________________________________________________________________________
94 - What's Old

 #   %W /  %L /  %T                       Name               Author Score  Age
16  32.6/ 27.2/ 40.2                      Newt          Ian Oversby 138.1  204
 7  35.9/ 30.6/ 33.6                      Vain          Ian Oversby 141.1  126
11  34.7/ 30.0/ 35.3                     Vigor         Ken Espiritu 139.4  114
17  34.3/ 30.8/ 35.0                     Fixed         Ken Espiritu 137.7  110
25  33.1/ 33.7/ 33.2              Fire and Ice          David Moore 132.6   99
10  27.8/ 15.7/ 56.5                  Fugitive          David Moore 140.0   80

Newt keeps on going, though is suffering heavy losses against a couple of
new warriors. Ultraviolet is no more and Vain becomes the second oldest
warrior. Fire and Ices holds a dangerously low rank and may not be around
for the next Core Warrior.
_______________________________________________________________________________
OLD HALL OF FAME
* means the warrior is still active.

Pos    Name                  Author          Age     Strategy
 1  Thermite II            Robert Macrae     2262    Qscan -> Bomber
 2  Impfinity v4g1         Planar            1993    Stone/imp
 3  Jack in the box        Beppe Bezzi       1620    P-warrior
 4  Tornado 3.0            Beppe Bezzi       1567    Bomber
 5  Torch t18              P.Kline           1539    Bomber
 6  Chameleon              Myer R Bremer     1437    P-warrior
 7  Frontwards v2          Steven Morrell    1420    Oneshot
 8  Evol Cap 6.6           John Wilkinson    1299    Stone/imp
 9  quiz                   Schitzo           1262    Scanner/bomber
10  T.N.T.                 Maurizio Vittuari 1204    Bomber
11  Grilled Octopus v0.5   David Boeren      1154    P-warrior
12  Hazy Shade II          John Wilkinson    1102    P-warrior
13  Stepping Stone         Kurt Franke       1049    Qscan -> Vampire
14  Rosebud                Beppe Bezzi        993    Stone/imp
15  Iron Gate 1.5          Wayne Sheppard     926    Scanner
16  T.N.T. pro             Maurizio Vittuari  925    Bomber
17  Agony II               Stefan Strack      912    Scanner
18  Barrage                Anton Marsden      876    Qscan -> Paper
19  Blue Funk              Steven Morrell     869    Stone/imp
20  Flurry                 Anton Marsden      835    Qscan -> P-warrior
21  Thermite 1.0           Robert Macrae      802    Qscan -> Bomber
22  Blue Funk 3            Steven Morrell     766    Stone/imp
23  Night Train            Karl Lewin         755    Paper
24  Mirage 1.5             Anton Marsden      736    Scanner/bomber
25  Blizzard               Anton Marsden      713    Qscan -> Paper
_______________________________________________________________________________
NEW HALL OF FAME
* means the warrior is still active.

Pos    Name                  Author          Age     Strategy
 1  Probe                  Anton Marsden      403    Q^2 -> Bomber
 2  Blur 2                 Anton Marsden      396    Scanner
 3  Damage Incorporated    Anton Marsden      373    Q^2 -> Bomber
 4  Return Of The Jedimp   John K W           357    Q^2 -> Stone/imp
 5  unrequited love        kafka              346    Q^2 -> Paper
 6  Impish v0.2            Ian Oversby        345    Stone/imp
 7  Gigolo                 Core Warrior staff 332    Q^2 -> Stone/imp
 8  Falcon v0.3            Ian Oversby        275    P-warrior
 9  Nine Seven Six         M R Bremer         232    Q^2 -> Stone/imp
10  Rosebud                Beppe              218    Stone/imp
11  Q^2 Miro               Anders Ivner       214    Q^2 -> Scanner/bomber
12  Instant Wolf 3.4       Edgar              205    P-warrior
13  Newt                   Ian Oversby        204 *  Q^2 -> Stone/imp
14  Goldfinch              P.Kline            201    P-warrior
15  Simple v0.4b           Ian Oversby        197    QScan -> Stone/imp
16  Trident^2              John K W           195    Q^2 -> Stone/imp
17  ompega                 Steven Morrell     189    Stone/imp
18  Frogz                  Franz              172    Q^2 -> Paper
19  The Machine            Anton Marsden      164    Scanner
20  Memories               Beppe              152    Scanner
21  Head or Tail           Christian Schmidt  142    Q^2 -> Paper
22  Electric Head          Anton Marsden      140    P-warrior
23  Tiberius 3.1           Franz              130    Q^2 -> Paper
24  Vain                   Ian Oversby        126 *  Q^2 -> Stone/imp
25  Ultraviolet-B          Ken Espiritu       120    Q^2 -> Paper

Ultraviolet enters the Hall and stops at 24th while Newt gains another five
places to 13th. New entry Vain returns Oversby to 5 warriors in the New HoF.
_______________________________________________________________________________
Current Status of the Internet Pizza Server Beginner Hill:

Hill Specs:
         coresize: 8000
   max. processes: 8000
         duration: after 80,000 cycles, a tie is declared.
max. entry length: 100
 minimum distance: 100
      maximum age: At age 100, warriors are retired.
    rounds fought: 200
  instruction set: ICWS '94 Draft

 #   %W /  %L /  %T                       Name               Author Score  Age
 1  46.0/ 34.3/ 19.7           Spat the dummy. Steve Gunnell (oh ye 157.8   50
 2  43.2/ 34.1/ 22.8                 Arsonic C             P._V._K. 152.2   67
 3  43.7/ 39.7/ 16.6                   Fat Man         A. S. Mehlos 147.8   64
 4  41.2/ 35.3/ 23.4          No Time To Think         A. S. Mehlos 147.1   51
 5  43.2/ 39.3/ 17.6       Reconnaissance v0.1             Ben Ford 147.0   15
 6  40.7/ 34.4/ 24.8           Ice Pick Willie             Ben Ford 147.0   33
 7  34.5/ 23.4/ 42.1                   iWeasel      WFB/Ian Oversby 145.5   90
 8  42.2/ 39.7/ 18.2 Death kiss with a dash of      Anders Rosendal 144.6   10
 9  41.6/ 38.7/ 19.7            Security Purge             Ben Ford 144.5    4
10  42.6/ 41.9/ 15.5                Scanzonato       Franco Solerio 143.3   85
11  35.5/ 28.2/ 36.3          A man with a Gun             Ben Ford 142.8   35
12  32.4/ 25.1/ 42.5           Frusteration II         A. S. Mehlos 139.7   54
13  26.3/ 14.7/ 59.0                Redemption         John Metcalf 138.0   26
14  28.2/ 19.1/ 52.7                      Glok             Ben Ford 137.3   34
15  40.3/ 44.2/ 15.5                    Hunter             Ben Ford 136.4   38
16  29.8/ 23.7/ 46.5       ModerationRevisited         A. S. Mehlos 136.0   70
17  39.8/ 44.0/ 16.2 Sticky taped together 1.2        Steve Gunnell 135.6   61
18  38.1/ 41.4/ 20.5            Reconnaissance             Ben Ford 134.8    1
19  40.7/ 47.7/ 11.5              v15variation        Steve Gunnell 133.8   16
20  25.9/ 18.3/ 55.8                 H-Bomb 9k          Josh Yeager 133.4   47
21  25.6/ 18.3/ 56.2                  H-Bomb 9          Josh Yeager 132.9   48
22  30.5/ 29.1/ 40.5    Rocking-Chair 94 v0.25    Leonardo Humberto 131.9   45
23  24.3/ 19.6/ 56.1                15,18 v1.1          Joshua Houk 129.1   44
24  27.6/ 27.3/ 45.1       Two kinds of chairs    Leonardo Humberto 127.9    3
25  28.7/ 31.2/ 40.1                    Kindly    Leonardo Humberto 126.2    2

The '94b hill has aged 103 since last issue, with several new players making
an appearance. Camarena's SpiImp expired of old age, as did Stajp's StiY v1.0
and StiZ v1.0, Arsonic B by PVK, Cut n Paste by Howard, Weasel by WFB and
Coleman's warriors Jam Major Zick 3, Hostile Takeover and Multiply or Drop??.
_______________________________________________________________________________
Current Status of the KOTH.ORG '94 No Pspace Hill:

Hill Specs:
         coresize: 8000
   max. processes: 8000
         duration: after 80,000 cycles, a tie is declared.
max. entry length: 100
 minimum distance: 100
    rounds fought: 250
  instruction set: ICWS '94 Draft, excluding ldp and stp

 #  %W/ %L/ %T                      Name               Author   Score     Age
 1  45/ 38/ 17                  Zooom...         John Metcalf     152      53
 2  44/ 38/ 18 Boys are Back in Town 1.1       Philip Kendall     151      78
 3  47/ 45/  8             He Scans Anew              P.Kline     149       4
 4  38/ 28/ 34                  Recovery          Ian Oversby     147      76
 5  45/ 45/ 10                      Win!          David Moore     145      51
 6  38/ 30/ 32                     Fixed         Ken Espiritu     145     136
 7  28/ 12/ 59              The Fugitive          David Moore     144     155
 8  28/ 13/ 58         _romanian_killah_  Costin Bontas rulez     144      45
 9  36/ 30/ 34                   Blacken          Ian Oversby     143      63
10  35/ 28/ 36                      Vain          Ian Oversby     143     153
11  40/ 38/ 22              Floody River              P.Kline     142     102
12  36/ 30/ 33          The Stormbringer    Christian Schmidt     142      87
13  36/ 31/ 33             Baseline Plus         Ken Espiritu     141     134
14  43/ 45/ 12                Red Carpet          David Moore     140      94
15  33/ 25/ 42                 Brigadeer     M Joonas Pihlaja     140      72
16  33/ 27/ 40              Gemini Dream     John K Wilkinson     139     159
17  39/ 42/ 19               The Machine        Anton Marsden     137     142
18  36/ 37/ 27               Liquid Fire    Christian Schmidt     135      49
19  34/ 33/ 33              Head or Tail    Christian Schmidt     134     124
20  37/ 41/ 22                 Sharkrage    Christian Schmidt     132       1

Now is the time of the scanners, which take four of the top five ranks.
_______________________________________________________________________________
Current Standings of the Oversby Autumn Corewar Tournament:

          :     '94     Tiny     Grey    Build    Multi  :   Total
 Macrae   :   87.63    69.55    74.28   100.00    74.87  :  406.33
 Pihlaja  :   98.66   100.00   100.00        x    84.82  :  383.48
 Schmidt  :   99.46    70.55    75.41    77.34    50.26  :  373.02
.WFB      :   91.10    22.42    49.35    56.28   100.00  :  319.15
.Khuong   :   75.82    60.37    65.86    63.96        x  :  266.01
.Mehlos   :   71.22    29.45    76.11    76.23        x  :  253.01
 Hale     :   99.12    66.52    18.68    60.92        x  :  245.24
 Moore    :  100.00    63.67    62.29        x        x  :  225.96
.Gunnell  :   72.82    46.50    19.46        x    47.12  :  185.90
.Yeager   :       x    24.93    44.22    60.03    34.55  :  163.73
 Kendall  :   90.04    35.48     3.21        x        x  :  128.73
.Duff     :   23.05    30.67    10.51        x        x  :   64.23

First place in the opening round was taken by Moore with his Recycled Bits,
after which Pihlaja dominated. His Genetic Beef easily took top spot in the
modified tiny round, and Quick Cooking further increased his lead when it
performed best against the grey warrior. Assugg won the build a warrior
round for Macrae, and finally, in the multi warrior round WFB's group of
warriors triumphed.

With three more round to play, there is still time to enter. Remember,
only the best 6 results count for veterans, or the best 7 for beginners.
Check the tournament's home page for details:

  http://www.geocities.com/TimesSquare/Realm/2443/
_______________________________________________________________________________
The Hint - The P^3 Switcher by David Moore

Redcoders often design their pspace-based switching routines in the form of
a state-transition diagram:

       .->------.                   L = loss
       |        |                   W = win
   W,T |      __V______             T = tie
  (w0) |     |         |<---.
       `--<--| State 0 |     \      w0 = strategy A (e.g. scissors)
             `---------'      `.    w1 = strategy B (e.g. paper)
                  | L (w1)     |
                  |            |
              ____V____        |
       .---->|         |       |
       |     | State 1 |---->--'
   W,T |     `---------'
  (w1) |       |         L (w0)
       `--<----'

Each round gives the program a new chance to change its mode of operation,
depending on the previous state and the result of the previous battle. In
addition, there is some action (or strategy) associated with each transition
between states:

   State  Input  Next  Action

   0      L      1     w1
   0      W      0     w0
   0      T      0     w0
   1      L      0     w0
   1      W      1     w1
   1      T      1     w1

Note that this pspacer would run w0 upon all transitions to state 0, and
that it would run w1 upon all transitions to state 1. Most interesting P^2
switchers execute the same program upon all transitions to the same state.
Can you see why?

If we assume that all transitions to a particular state run the same
warrior, then we no longer need to specify an action for each transition;
we simply specify an action for each state. That leads to a more compact
representation of the table:

   State  Action  L  W  T

   0      w0      1  0  0
   1      w1      0  1  1

The corresponding diagram becomes:

       .->------.                   L = loss
       |        |                   W = win
   W,T |      __V______             T = tie
       |     |         |
       |     | State 0 |<---.
       `--<--|   (w0)  |     \      w0 = strategy A (e.g. scissors)
             `---------'      `.    w1 = strategy B (e.g. paper)
                  | L          |
                  |            |
              ____V____        |
       .---->|         |       |
       |     | State 1 |       |
       |     |   (w1)  |---->--'
   W,T |     `---------'
       |       |         L
       `--<----'

The switcher for Electric Head has that property. Specifically, Electric
Head implemented the following state-transition table:

   State  Action  L  W  T

   0      w0      1  0  1    <---- initial state
   1      w0      2  0  2
   2      w0      3  0  3
   3      w1      4  3  3
   4      w1      5  3  4
   5      w1      6  4  5
   6      w2      7  6  0
   7      w3      8  7  7
   8      w3      9  7  8
   9      w3      3  8  9

A P^3 switcher can implement the same table in less time and in less space
than Electric Head's original code:

think ldp.a      #0, in
      ldp.a #PSTATE, table
      mod.ba   *in, table
      stp.b  *table, #PSTATE

table jmp }0, 441 ; = (44*10) + 1 = (49*9) + 0 = (40*11) + 1 ;initial state
      dat w0, 882 ; = (88*10) + 2 = (98*9) + 0 = (80*11) + 2
      dat w0, 333 ; = (33*10) + 3 = (37*9) + 0 = (30*11) + 3
      dat w1, 894 ; = (89*10) + 4 = (99*9) + 3 = (81*11) + 3
      dat w1, 345 ; = (34*10) + 5 = (38*9) + 3 = (31*11) + 4
      dat w1, 346 ; = (34*10) + 6 = (38*9) + 4 = (31*11) + 5
      dat w2, 627 ; = (62*10) + 7 = (69*9) + 6 = (57*11) + 0
      dat w3, 898 ; = (89*10) + 8 = (99*9) + 7 = (81*11) + 7
      dat w3, 349 ; = (34*10) + 9 = (38*9) + 7 = (31*11) + 8
      dat w3,  53 ; = ( 5*10) + 3 = ( 5*9) + 8 = ( 4*11) + 9

      dat w3, 349 ; = (34*10) + 9 = (38*9) + 7 = (31*11) + 8 ;unreachable

in    dat 0, 10  ; must have non-zero b-field in the previous cell
      spl 1,  9
      spl 1, 11

For example, after a transition to state 4, the pspacer will remember
the code 345. In the case of a loss, the next state will be decoded by
345 mod 10; after a win, the next state would be 345 mod 9; after a tie,
the next state would be 345 mod 11. Each of these decodings gives the
proper transition from one state (4) to the next (5, 3, or 4).

Note that we cannot specify different warriors for two different transitions
to the same state. However, as we have seen before, that is a very soft
restriction. Another restriction is that the 0th state must use the same
warrior as the 1st state.

Now we show how to construct the codes that are used in the table. This
requires some abstract algebra, but the results will be summarized below.

First, we must introduce some notation.

Operators listed from highest to lowest priority:

   gcd(a,b)   the greatest common divisor of a and b
   a =< b     a is less than or equal to b
   a >= b     a is greater than or equal to b
   a and b    logical and
   a -> b     a implies b (if a is true, then b is true)

"mod" will no longer refer to the MOD operation from redcode. Instead:

   a mod n            a modulo n
   a *' b (mod n)     the product of a and b modulo n
   a +' b (mod n)     the sum of a and b modulo n
   a == b (mod n)     a is congruent to b modulo n (also: n divides a-b)

I will borrow the % operation from the C language, which is similar to the
MOD from redcode:

   a % b      the unique c such that 0 =< c < b  and  c == a (mod b)

One of the theoretical results requires some more notation:

   Z          the set of all integers
   Z mod n    the set of all congruence classes modulo n
   G x H      the group formed by the Cartesian product of groups G and H

Modular arithmetic should look familiar to Redcoders, since all arithmetic
on the standard hills is done in Z mod 8000.

Examples:

   1 == 4 (mod 3)  ->  3*k = 1-4 for some integer k

   2 *' 3 == 1 (mod 5)

   (2 * 3) % 5 = 1

   gcd(3,3) = 3
   gcd(2,3) = 1
   gcd(2,4) = 2

We begin with a semi-formal description of the switcher:

   .------------------------------------------------------.
   |  P^3 switcher                                        |
   |------------------------------------------------------|
   |  r,s,t are positive integers                         |
   |                                                      |
   |  For each state in the table, there are non-negative |
   |  integers p,a,b,c such that p < CoreSize and         |
   |                                                      |
   |  a < r  and  p == a (mod r)  and                     |
   |  b < s  and  p == b (mod s)  and                     |
   |  c < t  and  p == c (mod t)                          |
   `------------------------------------------------------'

There will be different p,a,b,c for each state. However, since each state
may be considered independently, we won't bother to put subscripts on those
variables.

In the example above, r = 10, s = 9, and t = 11. Depending on the state,
p could be 441, 882, 333, ..., or 53. In the 0th state, a = 1, b = 0,
and c = 1.

To guarantee that we can compute any transition table, we need to choose
r,s,t such that for all possible a,b,c, there is a value for p such that
the above properties hold. In that case, there are r*s*t possible triplets
(a,b,c). It would be nice if every p between 0 and r*s*t-1 resulted in a
different triplet (p mod r, p mod s, p mod t). Then every possible triplet
(a,b,c) could be computed by choosing one of the first r*s*t non-negative
integers for p. That would guarantee that we can compute any transition
table if r*s*t does not exceed CoreSize.

Using some results from group theory, we can make those guarantees true
if gcd(r,s)=1 and gcd(r,t)=1 and gcd(s,t)=1. For ambitious mathematicians
who want to prove that statement, two of the relevant theorems are:

   Z mod m x Z mod n is cyclic if and only if gcd(m,n)=1.

   Every finite cyclic group of order n is isomorphic to Z mod n.

To express any possible transition table with n states, we must be able
to compute all triples (a,b,c) such that a<n, b<n, and c<n. Therefore, we
should choose r,s,t such that r >= n, s >= n, and t >= n. If we do that,
then we can assume that either r>n, s>n, or t>n (otherwise, either n=1,
gcd(r,s)>1, gcd(r,t)>1, or gcd(s,t)>1).

The result is that we will have some extra states which are not reachable
from the transitions specified by our n-state table. We should specify the
transitions for those unreachable states just in case a lucky opponent
brainwashes the switcher. That is why we added an extra table entry in the
example from Electric Head. We chose the same transitions as state 8 since
we hypothesized that Carbonite was the most brainwash-resistant component.

Since the size of the table will be the maximum value of r,s,t, we should
choose r,s,t to minimize max{r,s,t}. Since r,s,t are at least as large as n,
we can't achieve any result that is better than s=n, r=n+1, and t=n+2. In
fact, if n is odd, then that particular assignment does satisfy all of the
constraints. If n is even, then gcd(r,t) = gcd(n,n+2) = 2, so we are forced
to look for larger r,s, or t. In that case, we can simply add one state to
the table (to make n odd) to achieve the next best possible result.

That gives us the following rule for selecting r,s,t for an n-state table:

   If n is odd, then m = n+1.
   If n is even, then m = n+2.

   r = m, s = m-1, t = m+1.

Now that we have fixed r,s,t, we can compute the value p for each state
given a,b,c. We use the following result:

 .-----------.
 |  Theorem  |
 `-----------'

Given a,b,c,m,n,i,j,p such that

   m = n+1 if n is odd
   m = n+2 if n is even

   0 =< a < m    and
   0 =< b < m-1  and
   0 =< c < m+1

   i = b+c-2*a

   j = (i+1+m)/2 if i is odd
   j = i/2       if i is even

   p = (j*(m-1)+b-a)*m+a

Then

   p == a (mod m)
   p == b (mod m-1)
   p == c (mod m+1)

 .-----------.
 |   Proof   |
 `-----------'

Suppose that i is odd.

   j = (i+1+m)/2
   ->    j = (i+1)/2 + m/2        (since m is even and i is odd)
   ->  2*j = (i+1) + m
   ->  2*j == i+1+m (mod m+1)
   ->  2*j == i +' m+1 (mod m+1)
   ->  2*j == i +' 0 (mod m+1)
   ->  2*j == i (mod m+1)

Suppose that i is even.

   j = i/2  ->  2*j = i  ->  2*j == i (mod m+1)

In either case, 2*j == i (mod m+1).

   2*j == i (mod m+1)
   ->          2*j == b+c-2*a (mod m+1)
   ->       j *' 2 == b+c-2*a (mod m+1)
   ->    j *' (-2) == 2*a-c-b (mod m+1)
   -> j *' (m+1-2) == 2*a-c-b (mod m+1)
   ->   j *' (m-1) == 2*a-c-b (mod m+1)
   ->      j*(m-1) == 2*a-c-b (mod m+1)
   ->  j*(m-1)+b-a == a-c (mod m+1)

Substitute k for j*(m-1)+b-a.

   k == a-c (mod m+1)
   ->            k*(-1) == c-a (mod m+1)
   ->         k *' (-1) == c-a (mod m+1)
   ->      k *' (m+1-1) == c-a (mod m+1)
   ->            k *' m == c-a (mod m+1)
   ->               k*m == c-a (mod m+1)
   ->             k*m+a == c (mod m+1)
   -> (j*(m-1)+b-a)*m+a == c (mod m+1)
   ->                 p == c (mod m+1)

This proves 1/3 of the theorem. Furthermore,

   k = j*(m-1)+b-a  ->  j*(m-1) = k-(b-a)
   ->                 k == b-a (mod m-1)
   ->               k*1 == b-a (mod m-1)
   ->            k *' 1 == b-a (mod m-1)
   ->      k *' (m-1+1) == b-a (mod m-1)
   ->            k *' m == b-a (mod m-1)
   ->               k*m == b-a (mod m-1)
   ->             k*m+a == b (mod m-1)
   -> (j*(m-1)+b-a)*m+a == b (mod m-1)
   ->                 p == b (mod m-1)

For the last part, we simply observe:

   p = k*m+a  ->  k*m = p-a  ->  p == a (mod m)

Thus concluding the proof of this theorem.

 .-----------.
 |  Summary  |
 `-----------'

In summary, to construct a table of n states:

   m = n+1 if n is odd
   m = n+2 if n is even

   For each state, choose integers a,b,c such that
      0 =< a < m    and
      0 =< b < m-1  and
      0 =< c < m+1

   i = b+c-2*a

   j = (i+1+m)/2  if i is even
   j = i/2        if i is odd

   p = (j*(m-1)+b-a)*m+a % m*(m-1)*(m+1)

   p % m   = a
   p % m-1 = b
   p % m+1 = c

 .-----------.
 |  Example  |
 `-----------'

For Electric Head, the number of states is n = 10. Normally, m = 12 to
guarantee that all possible tables can be implemented. However, in this
case, m = 10 will work if we choose to decode with m on loss, m-1 on win,
and m+1 on tie. This implementation works because we know the particular
a,b,c values for each state and they are within the bounds:

   0 =< a < 10  (a is the transition on loss)
   0 =< b <  9  (b is the transition on win)
   0 =< c < 11  (c is the transition on tie)

Now we must determine the p value for each state. For state 0,

   a = 1
   b = 0
   c = 1

   i = 0+1-2*1 = -1

   j = (-1+1+10)/2 = 5  (since i was odd)

   p = (5*(10-1)+0-1)*10+1 % 10*(10-1)*(10+1)
     =        (5*9-1)*10+1 % 10*9*11
     =                 441 % 990

So p = 441 is the value that will actually appear in the redcode. We verify
that it is indeed correct:

   441 % 10 = 1
   441 %  9 = 0
   441 % 11 = 1

Note that m*(m-1)*(m+1) = 990 does not exceed CoreSize = 8000. Since
20*19*21 = 7980, any table with 19 states can be implemented in a CoreSize
of 8000. Of course, larger tables are possible with tricky coding.

Now the rest is up to you. Good luck and happy P-spacing!
_______________________________________________________________________________
Extra Extra -
Zooom... by John Metcalf

Following in the great Core Warrior tradition of publishing warriors
employing new techniques, here is Zooom...

Zooom is a scanner which uses the well known Mirage scan with a unique
twist - the clear instruction is not included in the main loop until
something is detected. This increases initial speed.

The constants have been chosen with care. The scan step is non-optimal,
since better find-x values would result in the scanner detecting itself
after fewer scans and switching to the dclear sooner.

The boot distance is optimal, ensuring Zooom doesn't detect it's boot
routine until after 923 scans. Perhaps reducing this to 920 scans, to
place Zooom closer to the decoy might improve it's performance against
oneshots slightly ;-)

Testing showed dclear to be the best end-game strategy rather than
switching to a dat bomb as Neverland did, or using a multi-pass clear.
Anyway, without further ado, here's the code:

;redcode-94
;name Zooom...
;author John Metcalf

;strategy .5 scan -> .33 scan/.33 clear -> dclear
;strategy  v0.1 self modifying scan loop
;strategy   v0.2 irregular scan pattern
;strategy    v0.3 boot and tailored decoy

;assert CORESIZE==8000

     org   boot

;    [ Decoy ]
q    for   22
     for   2+(q%5==0||q%5==2||q%6==2||q%16==3)
     spl   #m*3039,  {m*3359
     rof
     spl   #0,       0       ; scanned
     rof

;    [ Boot ]
boot:
q    for   10
     mov   sGat+q-1,  >sGat
     rof
     jmp   @0,        bDis+m-sGat

bDis equ   (boot+3+923*step) ; optimal distance
step equ   1671              ; non-optimal
numb equ   2230              ; number of scans
cGat equ   (sGat-2)

;    [ Scan ]
sGat:mov   }m,       *bDis   ; multi-function
     mov   sBmb,     >sGat
sLoo:sub   #step,    #step*numb
m:   jmz.f sLoo,     @sLoo   ; a-field mutates
     mov.b sLoo,     sGat
     jmn.a {m,       *sGat

;    [ Clear ]
sBmb:spl   0,        0
cLoo:mov   cBmb,     >cGat
     djn.f cLoo,     >cGat
cBmb:dat   <2667,    2-cGat
     end
_______________________________________________________________________________
Questions?  Concerns?  Comments?  Complaints?  Mail them to people who care.
Authors:  Beppe Bezzi <giuseppe.bezzi@galactica.it>, Anton Marsden
<amarsden@mcs.vuw.ac.nz>, Christian Schmidt <schmc003@goofy.zdv.Uni-Mainz.de>,
Philip Kendall <pak21@cam.ac.uk> and John Metcalf <grumpy@digitald.uk.com>
2002-2005 corewar.info. Logo C. Schmidt