Here's Dean's README.txt file:
Code: Select all
Description of Snakes rule (by Dean Hickerson, 4/20/2012)
----------------------------------------------------------
This file describes the Snakes and Snakes-history rules, and the
accompanying files.
The objects of interest in these rules are called "snakes". The shape of a
snake is a simply-connected polyomino in which every cell has exactly two
orthogonal neighbors in the snake, except for the two end cells, which
have only one neighbor each.
A snake grows at one end and shrinks at the other; if it can't grow (and
even sometimes if it could), it reverses direction. The growth at the
front is exactly matched by shrinkage at the back, so the 'size' of a
snake, defined later, never changes. (Because of a time delay between
growing and shrinking, the population can vary, but not by much.)
At each step, the direction of growth of a snake is determined by some
bits within the snake which evolve pseudorandomly, so the path that it
follows looks like a random walk. But since a snake is connected and its
population is bounded, it must eventually repeat, becoming either an
oscillator or a spaceship.
The rule
--------
There are two versions of the snakes rule, called "Snakes" and
"Snakes-history". These differ only in the handling of dead cells. In
"Snakes-history", dead cells that were once alive have a different
state (Z) from cells that were never alive (0). This makes it easy to
see where a snake has been, and to see if it's become periodic. You can
switch back and forth between the two rules at any time, without affecting
the behavior of the live cells. There's a script, snakes.switch.py, which
changes from one rule to the other; I recommend assigning it to a key for
ease of use. The rest of this description concerns the "Snakes" version.
There are 13 types of cells in the rule, but 5 of them also have a bit
value that's either 0 or 1, giving a total of 18 states. When a snake has
been growing at one end for a while, roughly half of its cells are in a
Background state (B0 or B1). The other half are involved in 'shrink
signals': Whenever the front end grows by one cell, it sends a shrink
signal toward the back, causing the back end to shrink by one cell. A
shrink signal consists of a Shrink Head (SH0 or SH1), followed by a Tail
cell (T0 or T1).
Another type of signal is used to make the snake reverse direction. A
reverse signal consists of a Reverse Head (RH0 or RH1) followed by a Tail
cell.
These four types of cells (8 states) are the only ones that can occur in
a snake, except at its front end. Six other states (N=New, L=Left,
F=Forward, R=Right, C0 and C1 = Check) can occur in the front two cells,
and 2 other non-dead states (A=Available and V=Venom) can occur outside of
the snake, orthogonally adjacent to the front cell. These are used to
control the growth or reversal of the snake.
The bit values associated with cells of type B, T, SH, RH, and C obey an
XOR rule. Mostly they evolve independently of the types of the cells: If
a bit x has 2 bits, y and z, as orthogonal neighbors, then its new bit will
be x XOR y XOR z, unless the cell is at a bend in the snake and the
diagonally adjacent cell outside the bend is a Venom cell. In that case,
the new bit will be the complement of x XOR y XOR z.
Sometimes a cell that isn't part of a group of 3 cells with bit values will
have a bit value in the next generation. In such cases, exactly one of its
neighbors currently has a bit value; the cell itself may or may not have
one. In this case the new bit value of the cell will be the complement of
its neighboring bit, unless the cell is currently a Background cell and is
going to be a Background cell in the next generation. (I experimented with
many alternatives before settling on this choice.)
Growth at the front of the snake is a 3-step process: At certain times
the snake will have a New cell at the front, with either a Background or
a Check cell behind it, and Background, Tail, and Shrink Head cells
everywhere else; call this generation 0.
In gen 1, each of the 3 empty cells orthogonally adjacent to the New cell
determines whether the snake can grow into it while remaining simply
connected; if so, then the cell becomes an Available cell. If the cell
directly in front of the N is not available, it may become a Venom cell,
depending on what's in the 3 cells in front of it. Meanwhile, the New cell
becomes a T0 or T1 cell, depending on the bit behind the New cell. In the
front position, a T cell is not a Tail cell, but rather a Tentative Turn
direction: T0 means that the snake may try to turn left, T1 that it may
try to turn right.
In gen 2, the T cell at the front looks at its bit value, at the bit values
of one or two cells behind it, and at the pattern of Available cells around
it, and makes a firm decision about whether and in what direction to try to
grow. It becomes either a directional cell (Left, Forward, or Right), or a
Check cell if it decides to reverse.
In gen 3, the Available cell in the direction just chosen tries to become a
New cell. It may not be able to: Although it was available for growth in
gen 0, it's possible that by gen 2 another snake has grown too close to it.
Meanwhile, the former directional cell becomes a Check cell.
A Check cell checks to see if it has a New cell next to it. If so it
becomes a Shrink Head; otherwise it becomes a Reverse Head. So if the
snake succeeded in growing, then it sends a shrink signal toward the back;
otherwise it sends a reverse signal.
The size of a snake
-------------------
The size of a snake is defined as the number of Background cells in it,
plus the number of Tail cells in it. (A T cell at the front is not
included in this count, unless it's touching a Reverse Head.) It turns
out that the size of a snake never changes. For a snake of size s, the
population of the snake, including any Available and Venom cells adjacent
to its front end, can vary from s+1 to floor(4s/3)+5. The lower limit
occurs just after a reversal, when there are no remaining shrink or
reverse signals in the snake. The upper limit occurs when the snake has
been growing at the front for a while, and is half full of shrink signals.
Small snakes don't reverse very often, and their populations tend to stay
near the upper limit. Larger snakes often run into themselves and reverse,
causing the population to drop to s+1 frequently; it may never approach
the upper bound.
Symmetry
--------
The rule has 90 degree rotational symmetry. It also has mirror symmetry,
provided that you complement all of the bits and swap states L and R.
There's a script, snakes.flip.py, which reflects a pattern horizontally
and changes states as needed.
Suppose an oscillator or spaceship has period P. Then it first reappears,
perhaps in a different orientation, in generation P or P/2 or P/4. There
are 8 possible orientations that this reappearance can have relative to
the original:
same: The pattern is probably a knightship. It can also be an
oscillator or orthogonal or diagonal spaceship, if it reappears
in the same position or shifted orthogonally or diagonally. For
example, in the file size_15.rle, 5 of the orthogonal spaceships
and all 4 of the diagonal spaceships are of this type. I
haven't seen any 'natural' oscillators like this, but the
second p738 snake of size 178 in bsp_9.rle is an artificial one.
rotated 180 degrees: The pattern is an oscillator.
rotated 90 degrees (clockwise or counterclockwise): The pattern is
an oscillator.
reflected horizontally or vertically: The pattern is probably a
glide-reflecting orthogonal spaceship. It could also be an
oscillator; I haven't seen that happen.
reflected across either diagonal: The pattern is probably a
glide-reflecting diagonal spaceship. It can also be an
oscillator; the first p360 oscillator in size-14.rle is the
only example that I've seen.
The 8 orientations should be equally likely, so I expect that a random
snake will become an oscillator with probability 3/8, an orthogonal
spaceship with probability 1/4, a diagonal spaceship with probability
1/4, and a knightship with probability 1/8.
Non-snake patterns
------------------
Originally the rule was designed only for patterns consisting of snakes,
but then I added some transitions that handle other sorts of patterns.
First, objects consisting only of Background cells are permanent; their
bits may change, but they keep the same shape, even if snakes bump into
them. Such objects can be used as walls and as labels.
Next, to deal with random starting patterns, cells whose neighborhoods
can't occur in snakes or in Background objects die. Within a few
generations, we're left with 3 types of objects: snakes, permanent
Background objects, and 2-headed snakes. A 2-headed snake grows at both
ends for a while; its shrink signals cancel each other in the middle.
Usually, one end will eventually reverse; the reverse signal will be
cancelled in the middle by a shrink signal from the other end and the
snake will become a normal 1-headed snake.
So random patterns, say 100x100 with density 50%, quickly break up into a
bunch of small snakes moving among some small Background objects, along
with a few larger snakes formed from 2-headed snakes.
Small snakes
------------
For brevity, I'll refer to a snake of size s as an s-snake. For values
of s up to 5, there are only one or two different forms for an s-snake
that's not interacting with anything else. For larger values, there may
be many different forms. Here are the ones I know of up to s=7; it's
possible that I've missed some less common forms:
s Forms of an s-snake
--- --------------------
1 c/6 diagonal spaceship
2 p24 oscillator (frequency ~ 20%)
p72 oscillator (frequency ~ 80%)
3 p36 oscillator
4 p30 oscillator (frequency ~ 10%)
(2,5)/21 knightship (frequency ~ 90%)
5 p48 oscillator (frequency ~ 30%)
p72 oscillator (frequency ~ 70%)
6 6 oscillators, with periods 42, 48, 48, 84, 84, and 336
c/3 orthogonal spaceship
2c/12 diagonal spaceship
3 knightships, with speeds (1,9)/42, (2,18)/84, and (2,14)/84
7 9 oscillators, with periods 48, 48, 120, 144, 240, 240, 240,
360, and 720
2 orthogonal spaceships, with speeds 4c/12 and 6c/36
2c/12 diagonal spaceship
4 knightships, with speeds (3,9)/60, (9,11)/60, (17,23)/180,
and (1,27)/180
It's amusing to put a bunch of small snakes in a rectangular box formed
from Background cells. If we just use snakes of sizes 2, 3, 4, and 5,
they'll usually just form independent oscillators before very long. But
if we add some 1-snakes, they'll fly around, reflecting off the walls
and pushing the other snakes around. Such a pattern must eventually
become periodic, but it can take a long time. (Usually the final result
isn't very interesting, consisting of independent oscillators, and
1-snakes shuttling between some of them.) An example is in the file
no_loitering.rle, which takes more than 3 billion gens to become periodic.
Combinations of snakes
----------------------
If a snake is all alone in the plane, then, since it's connected and has
bounded population, it must eventually repeat, becoming either a spaceship
or an oscillator. The pattern files contain many examples of both. It can
take a long time for repetition to happen; before then the snake behaves
like a particle doing a random walk. Even after it becomes periodic, the
motion may appear random unless you watch it for a long time.
If there are two snakes in the plane, they'll either interact infinitely
often or they won't. In the first case they'll jointly form a spaceship
or oscillator; several examples are in the file tandems.rle. In the second
case both snakes eventually become spaceships or oscillators, which evolve
independently. In either case, every cell in the plane eventually becomes
periodic.
For three snakes, things can be slightly more complicated; the pattern
collection contains several shuttles, in which one spaceship bounces
back and forth between two oscillators or spaceships. (In each of these,
the 'mirrors' are unaffected by the collision. There could also be a
shuttle in which a spaceship bounces between two oscillators, pushing
them farther apart each time, but I haven't found one.)
Conceivably one could build a universal computer with enough snakes, but
I've made no attempt to prove that.
Stuckness
---------
Much of the complexity of the rule was added to prevent snakes from getting
stuck. In early versions of the rule, a snake would always grow at the
front if it could possibly do so, even if there was only one direction
available. But that led to a problem: Large snakes would usually get
stuck after a few hundred million generations. This would happen when
both ends of the snake grew into an indentation in the snake; from then
on they'd alternately grow and shrink, but never enough to escape from
the indentation. So I modified the rule; now if a snake has only one
direction that it can grow, it may instead reverse direction, depending on
the bits near the front. A snake may still become stuck for a while, but
it will usually get unstuck eventually. (Of course, it's possible to
create a snake that's permanently stuck, but I haven't seen any cases where
a lone snake that's initially unstuck becomes stuck forever.)
An example of this sort of stuckness is shown in the files
stuck_until_22230.rle and stuck_forever.rle. These contain the same
starting pattern, but the second one uses a modified rule in which a
snake always grows if it can.
Unfortunately, fixing that stuckness problem caused another one. For the
snakes in a box patterns mentioned earlier, a snake would sometimes get
stuck in a corner or against a wall; although it always had a direction
that it could grow, it would choose not to. Other snakes might bump into
it, but they couldn't affect its growth enough to let it escape. So I
added the Venom state to the rule: If a snake can't grow forward because
of a cell that's a knight's move ahead of it, it will spit a drop of
venom, which may affect the bit value of the cell ahead of it. So a
spaceship running into a snake that's stuck on a wall can modify it so it
will escape.
Parity
------
If a lone snake reappears after P gens, shifted by the vector (X,Y),
then it turns out that P+X+Y must be even. In particular, there are no
oscillators with odd periods consisting of a single snake.
I have found some examples of odd-period oscillators, but they're all
rather dull. One is made up of 2 snakes that are stuck against each
other, and never grow or shrink at either end. There are some examples
with 2 snakes in a box. A closed loop made of Background cells can have
any period at all. And if the path of a single-snake oscillator is a
nonintersecting loop, it may be possible to put multiple snakes equally
spaced around it; although each snake takes an even number of gens to make
the loop, the merged pattern may have an odd period. The file
odd_period_oscillators.rle contains some examples of these types of
oscillators.
It's conceivable that an unboxed pair of snakes could interact with an odd
period, but I haven't seen it happen.
Here's why P+X+Y must be even: Each generation of a snake has one of
5 types:
Type N: There's an N cell at the front.
Type T: There's a T cell at the front.
Type LRF: There's an L, R, or F cell at the front.
Type C: There's a C cell at the front.
Type RH: There's an RH cell somewhere in the snake.
The possible transitions between these types are:
N -> T (The T cell is in the same place as the N.)
T -> LRF or C (The L, R, F, or C cell is in the same place as the N.)
LRF -> N (The N is adjacent to the L, R, or F.)
LRF -> C (The C is in the same place as the L, R, or F.)
C -> RH (The RH is in the same place as the C.)
RH -> RH (The new RH is adjacent to the old one.)
RH -> N (The N is in the same place as the RH.)
Define the 'color' of a snake to be (x+y+t) mod 2, where x and y are the
coordinates of the front cell if its type is N, T, L, R, F, or C, or of the
RH cell wherever it is, and where t=0 if the type is N, LRF, or C, t=1 if
it's T or RH. Checking the possible transitions, we see that the color
changes parity each generation, unless an LRF -> C transition occurs. But
this transition only happens when the heads of 2 snakes collide: the L, R,
or F was created because the snake thought it could grow, but when it tries
to it can't because the front of another snake is too close.
So for a lone snake, the color alternates between 0 and 1. If the snake
reappears in gen P shifted by (X,Y), then the color has changed by
(X+Y) mod 2, which must be 0 if P is even and 1 if P is odd.
Nonreversing snakes
-------------------
If you run a bunch of 12-snakes to completion, they'll almost all turn
into diagonal spaceships with speed 86c/2408. But if you do the same for
13-snakes, you'll get a large variety of oscillators and spaceships, all
with periods which are divisors of 1260. This dependence on the size is
partly explained by looking at snakes that never reverse and never
envenomate themselves. For such a snake, the evolution of its sequence of
bit values can be computed without knowing anything about how the snake
moves. For example, in a 4-snake, in one generation out of three, the
cells will look like this, from front to back:
N Ca Bb Tc SHd Be Bf
where a, b, ..., f are either 0 or 1. Three gens later this becomes:
N C(1+c) B(a+b+d) T(1+b+d+e) SH(1+c+e+f) B(a+b+d) B(1+b+c+f)
where the addition is done mod 2. Iterating, we find that gens 6 and 27
are identical:
N C(b+d+e) B(a+b+d+e+f) T(c+e+f) SH(1+a+b+c+e+f) B(a+b+d+e+f) B(1+a+b+c+e+f)
(Gens 3 and 24 may not be identical: Information is lost from gen 0 to
gen 3 and from gen 3 to gen 6.)
So, from gen 6 on, the period of the bit sequence is a divisor of 21. It's
also a multiple of 3, so it's either 3 or 21.
The actual period of a nonreversing snake must be a multiple of its bit
sequence period (b.s.p.). It can be an arbitrarily large multiple; the
file bsp_3.rle contains an extensible sequence of oscillators with
b.s.p. 3 and increasing periods. However, such examples are rare; usually
the actual period is either 1, 2, or 4 times the b.s.p.
The table below shows the maximum b.s.p. for snakes of size up to 22.
There's probably a clever way to compute this based on polynomials over
GF(2), but I haven't figured it out, so these were found by iteration:
s 1 2 3 4 5 6 7 8 9 10 11 12 13 14
p 6 9 6 21 36 84 180 3066 630 6141 16002 6132 1260 360
s 15 16 17 18 19 20 21 22
p 360 786429 8190 41943 1747620 19975068 190092 402407448
When the maximum b.s.p. is small, e.g. for s = 13, 14, or 15, a random
snake may turn into any of a large number of small period things.
When the b.s.p. is large, most snakes will crash into themselves and
reverse; in these cases the number of likely outcomes tends to be small.
There may also be some nonreversing snakes with small periods, but they'll
be very rare.
The files bsp_3.rle, bsp_6.rle, bsp_9.rle, and bsp_12-48.rle contain
examples of oscillators and spaceships with small b.s.p.s. The
oscillators are mostly shaped like long, narrow rectangles, around which
a snake chases its tail, but some of them can be bent into other shapes.
The spaceships mostly travel in almost straight lines, with fairly high
speeds.
Questions
---------
Is there an efficient way to compute the maximum bit sequence period for
an n-snake?
Is there a 'natural' oscillator, consisting of a single snake, which
doesn't reappear in reflected form after half of its period? (The second
p738 178-snake in bsp_9.rle is an artificial example.)
Is there an oscillator, consisting of a single snake, which reflects across
a horizontal line in half of its period? (The first p360 oscillator in
size-14.rle reflects across a diagonal line.)
Is there an odd-period oscillator consisting of two or more snakes which
aren't stuck against each other?
Is there a shuttle in which a spaceship bounces between two oscillators,
pushing them farther apart each time?
Is there a shuttle in which the bouncing snake has different speeds in
the two directions that it goes? (The ones in the pattern collection all
involve reflections in which the snake doesn't reverse. So its bit sequence
doesn't change, and it has the same speed, in the opposite direction, after
the reflection.)
Files
-----
These files are included in this distribution:
README.txt
This description.
Rules and associated files:
Snakes.table
The main rule, discussed above.
Snakes-history.table
A variant in which dead cells that used to be alive have a
different state. It's often easier to see what a snake is doing
by switching to this rule; in particular it can make it visually
obvious when a snake has become an oscillator or spaceship.
Snakes-aggressive.table
Aggressive variant of the rule, in which a snake always grows if
it can. This is included to demonstrate the stuckness problem
mentioned earlier.
Snakes.colors
Snakes.icons
Color and icon files for all 3 rules.
Scripts:
snakes.random.py
Generates random snakes. Enter a single number S to get a random
S-snake, or two numbers S,N to get N S-snakes, or three numbers
S,M,N to get an MxN array of S-snakes. (Not all snakes can be
produced by this script, only ones which, when traversed from
front to back, only involve moves to the north, south, and east.)
snakes.flip.py
Reflects the selected rectangle across a vertical axis,
complementing bits and swapping states L and R.
snakes.switch.py
Switches between rules 'Snakes' and 'Snakes-history'. Assigning
a key to this script makes it easy to switch between the rules.
snakes.randombits.py
Randomizes the bits in the selected region, without affecting the
types of cells.
Patterns:
size_1-6.rle
size_7-9.rle
size_10-12.rle
size_16-18.rle
size_19-20.rle
All known snakes with sizes 1-12 and 16-20.
size_13.rle
size_14.rle
size_15.rle
A selection of snakes with sizes 13-15. There are many others.
size_21-46.rle
An assortment of larger oscillators and spaceships, with sizes 21
to 46. (These are packed too close together; to view one of them
you'll need to copy and paste it into an empty universe.)
odd_period_oscillators.rle
Oscillators with odd periods (not very interesting).
bsp_3.rle
bsp_6.rle
bsp_9.rle
bsp_12-48.rle
Snakes with bit sequence periods from 3 to 48.
tandems.rle
Combinations of 2 or more snakes working together.
shuttle_ef_2_#1.rle
shuttle_ef_2_#2.rle
shuttle_ef_5.rle
shuttle_ef_7.rle
shuttle_ef_103.rle
shuttle_ef_2_diagonal.rle
Shuttles, in which a spaceship bounces back and forth between two
other spaceships or between a spaceship and an oscillator. In each
case, all of the activity is confined to a strip of finite width
around an horizontal or diagonal line. ("ef" means expansion
factor, the limit of the ratio between the times of successive
bounces at one end.)
shuttle_2D_ef_2.rle
In this shuttle, an orthogonal spaceship alternately travels
east and south, bouncing off of a knightship and a diagonal
spaceship.
spiral.rle
A knightship spirals outward, repeatedly bouncing off of four
orthogonal spaceships heading east, south, west, and north.
no_loitering.rle
There are 12 snakes in a box. Most of them spend most of their
time as oscillators, but 3 of them (1-snakes) fly around, bouncing
off the walls and pushing the oscillators around.
Maxwells_demon.rle
A box is divided in two by a porous wall, which allows a 1-snake
to pass from left to right, but not so easily from right to left.
Starting with 1-snakes on the left and 3-snakes on the right, they
eventually trade places, and mostly stay that way.
bull_in_a_china_shop.rle
A 19-snake starts in the middle of an orderly collection of
3-snakes. It pushes them around and finally escapes from them,
but goes back in 3 times before becoming a spaceship.
flyby.rle
A dense collection of snakes is imprisoned by some 5-snakes, until
a passing 1-snake releases them.
trap.rle
A snake wanders around for a while, but then enters a box and locks
the door behind itself.
you_shall_not_pass.rle
A flotilla of snakes is stopped by a single snake.
stuck_until_22230.rle
A snake becomes stuck for 22230 generations.
stuck_forever.rle
The same pattern, in a more aggressive rule where snakes always
grow if they can, becomes stuck forever.
4-cell_unknown.rle
A 4-cell 2-headed snake becomes a 212-snake. It must eventually
become an oscillator or spaceship, but I doubt that we'll ever
know which.
END OF FILE
