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>
|
