From: rjc@hal.gnu.ai.mit.edu (Ray)
Subject: Binary Subdivision bombing
Organization: /etc/organization
Date: Sun, 12 Apr 1992 23:37:51 GMT

   I have been experimenting lately with a bombing technique that I'd
call binary subdivision. It works like this.


                         -- program's location --
                        /                         \
                  bomb loc -2000              bomb loc +2000
	        /                \           /              \
            -1000             +1000       -1000           +1000
           /      \          /      \    /     \         /     \
        -500     +500      -500   +500 -500    +500    -500   +500
       /    \   /    \    /    \ /    \/   \  /    \  /    \ /    \
     -250   +250

  Well, you get the picture. On each iteration, a bomb is placed between
two previous bombs. On the 7th iteration, the core is bombed every 32
locations, hence a program of length greater than 32 will be hit.
On the next iteration, every 16th location is hit. And so on.

   The problem is with the implementation. Right now, I have implemented
a version which copies itself to each node on this tree, and splits
to each of the subnodes on its left and right.  This slows down the bombing
process but the program is more likely to survive non-spl bombers.
A hit only kills one of the branches of the tree.

  What I'd like to do is implement a faster version that uses iteration
rather than recursion (spawning copies). It's hard to do without a stack
of some sort though. With post increment on the Xhill it is easy to
implement a stack, however, the stack will grow exponentially large
as each iteration is evaluated. At the 7th iteration, the stack is 
about 256 locations large. That's much to big (as it can be bombed
easily)

 	What I need is a non-stack, non-spawning algorithm that can
bomb each node on that tree.

Here's a copy of my current program.

;redcode verbose
;name Binary Tree
;author Ray Cromwell
;strategy Spawn off two copies of itself at
;strategy dest+epsilon and dest-epsilon, then epsilon=epsilon/2
;strategy as a result, the distribution through the core is maximized.

dest1   dat #0,#0
dest2   dat #0,#0
size    dat #tbl-dest1,#tbl-dest1	;size of prog

start   mov #0,dest1			;zero dest1,dest2
        mov #0,dest2
        add @ptr,dest1			;dest1+offset
        sub @ptr,dest2			;dest2-offset
        djn 1,ptr			;decrement ptr to offset table
        mov size,dest1-1		;move copy size
        djn 1,size			;decrement size
        mov @dest1-1,<dest1		;copy program
        mov @dest1-1,<dest2		; to both branches on the tree
        djn -2,dest1-1			
        add #3,dest1			;
        add #3,dest2			; advance dest point to start of code
        spl @dest1			; exec code
        spl @dest2
					;die
ptr     dat #tbl,#tbl			;ptr into table		
        dat #0031,#0031			;subdivide table
        dat #0062,#0062		
        dat #0125,#0125
        dat #0250,#0250
        dat #0500,#0500
        dat #1000,#1000
tbl     dat #2000,#2000			

        end start
---------------------------------------------

  This program accomplishes its "bombing" by being lucky enought of
to overwrite a program with it's data table of dat's.


Comments ?