_______ _______ // __ \ _____ __ ____ _____ // \ _____ ______ // / \\/ // \ // '___/ // __ \ // / / // \ // __/ // /____ // / / // / // ____/ // / / // / / _\\ \ \\______/ \\____/ //__/ \\____/ \\______/ // ,__/ //____/ ................................................ // / ................. Resonant Papers //__/ Issue 2 2020.01.27 Hello and welcome to CoreOps newsletter dedicated to CoreWar, the ulti- mate programming game. I'm inversed and it is my mission to bring you the latest news from the virtual frontline. Beginners and prospective redcoders are advised to read the tutorials at https://corewar.co.uk/guides.htm . This issue covers silk step interactions with a focus on the tiny set- ting. Warm up your emulator! _______ THEORY \________________________________________________________________ Barkley Vowk's new warriors 7b15f4b8-..., 4b0804b3-..., and 7fe57f81-... have set the new standard for tiny papers, taking the 1st, 2nd and 5th places at Koenigstuhl at the moment of publication. Yet at first glance they look completely unremarkable -- two-silk coreclear-type papers with plain MOV attacks. Let's dive into the mechanism behind their perfor- mance. 7b15f4b8-... 4b0804b3-... 7fe57f81-... 7 processes 7 processes 5 processes spl.i @ 0, > 236 spl.i @ 0, > 236 spl.i @ 0, { 66 mov } -1, > -1 mov } -1, > -1 mov } -1, > -1 spl.i @ 0, > 92 spl.f @ 0, < 83 mov } -2, > -2 mov } -1, > -1 mov } -1, > -1 spl.i @ 0, >-261 mov @ 4, { -21 mov } -53, { 115 mov } -1, > -1 mov }-121, {-392 mov < -30, {-341 mov > 25, {-164 jmp.ba -2, > 177 djn.x -1, < -41 djn.a -2, >-305 The first thing to note is that the papers do not boot, which in theory should leave them vulnerable to oneshots and table scans. However, exam- ination reveals that the original paper soon gets partially overwritten with another copy. This in turn happens to other copies and has two ef- fects. First, any processes caught in an SPL carpet are rescued and even put to useful work. Second, if the overwritten paper was not stunned, the processes from the two copies will be combined, resulting in either doubled attacks or increased process generation (more on that later). The exact sequence of steps leading to self-overwriting can be revealed by examining the table of the form i * X + j * Y, where X and Y are the inner and outer silk steps respectively. Denoting congruence modulo coresize by ~=, we have: 7b15f4b8-... 1 * X + 3 * Y ~= 0 When plotted on the (X, Y) plane, 4b0804b3-... 4 * X + 2 * Y ~= 4 such equalities look like lines 7fe57f81-... 1 * X + 4 * Y ~= 3 with rational slopes, wrapping around the edges. These lines are clearly visible on the score surface images [1]. By analogy with celes- tial mechanics I call such step interactions resonances. The larger a resonance's coefficients are, the less salient it is. The most notice- able lines correspond to detrimental resonances that prevent proper replications. The properties of paper steps mirror those of stone steps. The behaviour of the latter can in principle be understood by replacing the core with a unit interval and studying the sequence of bombed locations (fraction- al parts of step multiples). The worst possible step sizes in this model are the rational numbers p / q, covering only q distinct locations. Ir- rational numbers fare better, densely covering the "core", but not all of them are equally good. The worse the step can be approximated by ra- tional numbers, the more uniform the resulting sequence is. The least approximable number is the golden ratio. With paper steps we see a similar picture but in more dimensions. For a two silk paper with steps X, Y we have a 2D "sequence" of paper loca- tions within the unit square i * X + j * Y. If the steps are rationally dependent -- that is, p * X + q * Y is an integer for some integers p, q, then the sequence is periodic with period (p, q) and the ratio of unique locations goes to zero. So in terms of replication efficiency, resonances are the worst possible choices. But in a real, finite-sized core, this deficit can be easily outweighed by stun resistance. The best steps in this model are certain cubic irrationals analogous to the gold- en ratio. There is a lot of fascinating math behind this problem deserv- ing a separate exposition. ______________________ REPLICATION IN DETAIL \_________________________________________________ Now let's move on to the actual replicators, starting with a two silk coreclear-type paper: spl @ 0 , > Y This paper structure means that any replication path mov }-1 , >-1 consists of Y steps followed by X steps. The over- spl @ 0 , > X writing code initially lands over a paper containing mov }-1 , >-1 both silks and then spreads over its X step descen- ( p a y l o a d ) dants via natural replication. The inner silk has the time to fully execute the number of instruction equal to the sum of the resonance's step coefficients. Thus the minimal useful resonances have a coefficient sum of 3, paper-launched imps being an example. Payloads containing more than one instruction require higher values. In my experiments with a typical tiny paper (payload length 2), resonances with sums 4 and 5 worked best. It is assumed that both step coefficients are positive. Resonances with a single negative coefficient are technically possible, but are less practical as the initial paper and some early copies (the most vulnerable code) never get overwritten. Another important parameter is the remainder, or the offset between the overwriting copy and the original one, for it largely determines the ef- fect of the resonance. There are two particularly important cases. First, a zero remainder. Since the instructions effectively remain un- changed, the original processes continue the execution as if nothing happened. This means that now we have two sets of processes in the loop (assuming that the payload contains one). Not all attack types are com- patible with such resonance though, because all the fields will be reset to their original values. The original processes may also interfere with replication if they execute the silk's MOV at the wrong time. However, the fact that we now have two sets of processes within the same code opens up intriguing possibilities. It is tempting to exploit the process alternation to perform some kind of bombing. 7b15f4b8-... has zero re- mainder. Second, the silk's SPL can land right on top of an instruction that is about to be executed. This type of resonance leads to an extremely rapid, avalanche-like process generation. The overwriting copy will then have twice the normal process amount. The copy that overwrites it will double the process count again and so on. Under the tiny settings, the process count can be maxed out as early as 2.5 CORESIZE cycles. This serves as another type of stun resistance - the closer the paper to the process limit, the less effect an SPL carpet will have. This type of resonance is employed by 4b0804b3-... . In my experiments these two resonance types worked best. Other remain- ders are possible too, but they can lead to unexpected effects. For ex- ample, in 7fe57f81-... the overwriting silk's SPL and MOV instructions alternate, spilling processes to random locations. sX spl @ 0 , > X Timescape-style papers behave differently. mov } -1 , > -1 Unlike the coreclear papers, all 2^n replica- ( p a y l o a d ) tion paths of length n are valid. However, mov { sX , { sY every end silk replication increments the sY jmp Y+1 front silk step, so the different path permu- tations in general lead to different loca- tions. The set of paths with A and B steps of types X and Y respectively leads to locations ranging from: A * X + B * Y (path XXX ... YYY) to: A * X + B * Y + A * B * dX (path YYY ... XXX), where dX is the X step increment. All paths of length n lead to Sum (1 + i (n - i)) = (n + 1) (n^2 - n + 6) / 6 distinct locations (OEIS A000125 [2]). The papers come in clusters and the table i X + j Y gives their starting locations. In case of a reso- nance, any cluster is eventually overwritten. Since the overwriting cluster is larger by at least dX, the remainder can be in the [-dX .. L - 1] range, where L is the paper length. However, the head of the cluster gets written first, so it makes more sense to use the values from [0 .. L - 1] range to minimize the delay. The code must execute completely before being overwritten, otherwise there is no point in hav- ing an end silk. This means that the Y coefficient must be 1 or greater, or the X coefficient must be greater or equal to the number of exe- cutable instructions. The process stacking effect can be achieved without a resonance by using an end silk of the form jmp @0, resonant coreclear-type paper ;assert CORESIZE == 800 ; 3 * X + Y = 1 stepX equ 0 + (1 * time) stepY equ 1 - (3 * time) time equ 106 ma equ 523 djs equ 403 qx equ 150 qy equ 577 qa1 equ ((qx - 1) * qy + 1) * (((qx - 1) * qy) % 800) qb1 equ (qx - 1) * qy qa2 equ (qx * qy + 1) * ((qx * qy) % 800) qa3 equ ((qx + 1) * qy + 1) * (((qx + 1) * qy) % 800) qb3 equ (qx + 1) * qy org qscan qscan sne.f qf + qa1 , qf + qb1 seq.f qf + qa2 , } qf jmp @ qlo + 1 , { qf sne.f qf + qa3 , qf + qb3 jmz.f start , < qf qf mul.x # qx , # qy jmz.f @ qlo + 1 , > qf qlo mov } djs , > qf mov } qlo , { qf seq { qf , > qf djn.f qlo , > qf start spl 2 , {-djs spl 1 , {-djs - 2 spl 1 , {-djs - 4 silkY spl @ 0 , > stepY mov } silkY , > silkY silkX spl @ 0 , > stepX mov } silkX , > silkX mov > ma , { 0 djn.f -2 , < djs ;redcode-tiny ;author inversed ;name Chorus ;strategy Quickbomb -> Timescape-type paper with mirrored resonance ;assert CORESIZE == 800 stepX equ 67 ; 6 * 67 = 402 stepY equ 12 m1a equ 688 m1b equ 368 m2a equ 703 m2b equ 788 djs equ 45 bdist equ 400 qa equ 179 qb equ 411 qc equ 764 qd equ 388 x0 equ (-CURLINE) mirror equ silkX + bdist + 6 qalpha equ x0 + qa + i * qb qbeta equ x0 + qc + i * qd i for 9 mov { qalpha , qbeta rof start spl 2 , { x0 + qa + 10 * qb spl 1 , { x0 + qa + 11 * qb spl 1 , { x0 + qa + 12 * qb mov { silkX , { bp bp spl mirror , { x0 + qa + 13 * qb silkX spl @ 6 , > stepX mov } silkX , > silkX mov > m1a , { m1b mov > m2a , { m2b mov { silkX , { silkY silkY djn.f stepY + 1 , < djs _____________________ PERFORMANCE ANALYSIS \__________________________________________________ Let's take a look at the scores of various warriors against five reso- nant papers (bvowk's trio, Chorus and Consonance). Once dominant, oneshots are struggling against the new threat. The best result most ex- isting designs can hope to achieve is not losing horribly. Scanners don't fare any better. Only four scanning warriors score more than 135 points: +-----------------------------------------------------------+ |NAME AUTHOR TAKEN GIVEN | +-----------------------------------------------------------+ |Table Scan John Metcalf 147 125 | |SmarterLiner Christian Schmidt 146 138 | |s774++ Michal Janeczek 144 135 | |T-Scan John Metcalf 139 134 | +-----------------------------------------------------------+ Table scans can catch the unbooted paper quickly enough in order for the spl carpet to be effective. On the other hand, if the paper uses quickscanning instead of quickbombing, large scan table becomes a lia- bility. Smartliner uses bombing in combination with a scan step of 619, also allowing it to frequently find the original code quickly. s774++ uses a scan step of -26. Negative steps are rarely used by oneshots, since attacking the locations that were recently found to be empty is not very efficient. On the other hand, papers optimized against regular oneshots can be poorly adapted to such strategy. Oneshot authors hoping to score well against the replicating beasts should consider alternative attack methods such as multiple shots and extra spl stripes. Every strategy has a counterstrategy and the new papers are not an ex- ception to this fundamental rule, evolved papers being a hard counter: +-----------------------------------------------------------+ |NAME AUTHOR TAKEN GIVEN | +-----------------------------------------------------------+ |bestwar4.red Dave Hillis 191 96 | |[RS] Chaderia Nelitha inversed 187 100 | |[RS] Chaderia Hysura inversed 178 100 | |Evolving Threat Dave Hillis 174 115 | |Evolver 105814574x500 R.Daneel 165 108 | |redrace (3/05/01) v1 Dave Hillis 165 108 | +-----------------------------------------------------------+ Stone+imps tend to do rather well, oftentimes outperforming oneshots. Prolonged bombing and infinite imp spirals seem to be the key factors. +-----------------------------------------------------------+ |NAME AUTHOR TAKEN GIVEN | +-----------------------------------------------------------+ |Resin John Metcalf 148 107 | |Drypht inversed 135 126 | |backdraft Sascha Zapf 133 127 | |Windkeeper Christian Schmidt 133 124 | |Tiny Black Knight Christian Schmidt 130 130 | |Cristalline form v2 G.Labarga 129 126 | |Creeping Horror John Metcalf 128 115 | |Tiny Last Judgement Christian Schmidt 127 134 | +-----------------------------------------------------------+ The resonance technology turns the tiny hill balance upside down. The new equilibrium looks like this: resonant papers beat oneshots, oneshots beat evolved papers, evolved papers beat resonant papers. Stone+imps are no longer the only hard counter to scanners and should rely on balanced performance in order to adapt. A new tiny hill era requiring new strate- gies begins. ___________ REFERENCES \____________________________________________________________ [1] https://corewar.co.uk/gutzeit/score_surfaces/yap/index.htm [2] http://oeis.org/A000125 news:rec.games.corewar mailto:reoser@mail.ru Typeset in GNU Troff by Anton Shepelev (anton.txtgmail.com).