Path: news-rocq.inria.fr!France.EU.net!news.bull.fr!nntp.bull.com!cam-news-feed5.bbnplanet.com!cam-news-hub1.bbnplanet.com!news.gtei.net!chippy.visi.com!news-out.visi.com!news.idt.net!netnews.com!newspeer1.nac.net!news.new-york.net!news.stormking.com!grumpy@xanther.digitald.uk.com From: John Metcalf Newsgroups: rec.games.corewar Subject: Core Warrior 70 Date: 5 Feb 1999 18:29:34 -0500 Organization: Storm King Ind. Inc. Lines: 833 Sender: server@news.stormking.com Distribution: world Message-ID: Reply-To: grumpy@xanther.digitald.uk.com NNTP-Posting-Host: valhalla.stormking.com Mime-Version: 1.0 Originator: corewar-l@stormking.com .xX$$x. .x$$$$$$$x. d$$$$$$$$$$$ ,$$$$$$$P' `P' , . $$$$$$P' ' .d b $$$$$P b ,$$x ,$$x ,$$x ,$$b $$. Y$$$$' `$. $$$$$$. $$$$$$ $$P~d$. d$$$b d d$$$ `$$$$ ,$$ $$$$$$$b $$$P `$ $$$b.$$b `Y$$$d$d$$$' . . a . a a .aa . a `$$$ ,$$$,$$' `$$$ $$$' ' $$P$XX$' `$$$$$$$$$ .dP' `$'$ `$'$ , $''$ `$'$ `Y$b ,d$$$P `$b,d$P' `$$. `$$. , `$$P $$$' Y $. $ $ $ Y..P $ `$$$$$$$' $$$P' `$$b `$$$P `P `$' `Y'k. $. $. $. $$' $. 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, 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 , Anton Marsden , Christian Schmidt , Philip Kendall and John Metcalf