forked from conwaylife/ptbsearch
/
README
157 lines (116 loc) · 6.51 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
This directory includes most of C source code I use currently for
Life analysis (with the exception of the files containing main() in
the tools not included here). Very little of it is documented, but I
will describe the components I use to look for still-life perturbations.
Some data files and some perl scripts are also included.
------
The two executables needed for perturbation search are ptb2 and survive.
(Edit the Makefile if necessary and type make ptb2; make survive.)
ptb2:
ptb2 is invoked as:
ptb2 <test pattern> <list of perturbers> [maximum generation]
[#perturbers-1]
[minimum generation]
[#perturbers that can be destroyed
completely without halting search]
[max gen of first interaction]
For example:
ptb2 picol.life ptb.list 80 2 20 1 > ptbpicol.out
This will try to add three perturbers to the collision between a glider
and block that results in a Pi heptomino. The perturbation has to start
after generation 20 and both perturbers must be touched by step 80.
The last argument requires some explanation. The cells of the perturbers
are labeled '*' or 'z' depending on whether they can ever disappear. In
an eater, there are certain cells that persist in all known cases, so they
are not allowed to disappear (these are labeled) '*'. Once they are
destroyed, the perturbation is considered a failure. The others can
disappear, but in some cases such as the block, all cells can potentially
disappear, and the last argument above limits the number of such
perturbers, since their presence can greatly increase search time.
Note that in picol.life, the glider cells are labeled 'a' and the
block cells are labeled 'b' to distinguish between them. The
survive program uses this labeling.
The extra parameter [max gen of first interaction] ensures that the
first interaction between the pattern and the catalysts is before a
particular generation. If this parameter is omitted then we assume
that [max gen of first interaction] == [maximum generation]. This
parameter should be especially useful if the initial pattern is a
spaceship.
survive:
survive tests which stable cells continue to exist after the pattern
has stabilized. To use it, some cells in the initial pattern are
excluded from this test, while the others (assumed to be part of
a still life) are tested at each generation to see if they are
present. These cells may disappear for some time, but must be restored
before the end of the testing period (hard-coded to 500 generations in
the program). Since cells can be either *, a-z, or A-Z, the one argument
of survive specifies which cells to ignore.
For picol.life, 'survive a' only outputs patterns that restore the block,
while 'survive ab' will output any pattern such that the perturbers added
by ptb2 are not destroyed.
Pattern format:
Like xlife picture format, except ! acts as a linefeed.
Also, live cells can be represented by letters a-z A-Z
in order to distinguish between parts of the pattern that survive
If the filename of the test pattern ends in ".rle" then it is assumed
that the data is in RLE format. In plain RLE, live cells are translated
to '*'. In LifeHistory format state 1 translates to '*', state 3 to 'a'
and state 5 to 'b'. States 2 and 4 are ignored. No other states may be
present.
RLE can also be used in the list of perturbers. RLE is assumed to be in
use if there is at least one instance of the character '$' on the line.
State 1 corresponds to '*' while states 3 and 5 correspond to 'z'. All
RLE for a single catalyst must appear on one line. Lines that begin with
two hash signs '##' are used as descriptors for the following catalysts.
Lines that begin with a single hash sign '#' are ignored, as are lines
that are purely whitespace. At the start of the program's execution a
summary of the catalysts that are being used is printed to stderr.
Order of fields in output
from ptb2:
<pattern> <generation of first interaction>
from survive:
<input line> <max #generations fixed part is "damaged" and then restored> \
<#generations during last "damaged" period> \
<last generation fixed part was intact> \
<#cells - fixed part> \
<final pattern - fixed part>
makematrix is a perl script that converts this output to an xlife
picture format file.
Example:
To find the initial pertubation in the original stable reflector, use
the command
ptb2 picol.life ptb2.list 80 2 20 0 > ptbs.out
to generate a list of candidates, and
survive a < ptbs.out > restore.out
to find the two that restore the block.
Note that this is not the same arguments to ptb2 given earlier. In this
case, four different block patterns are used:
zz ** z* *z
** zz z* *z
These indicate the different ways a block can be involved in a fast
perturbation, where just two cells are destroyed. Then the last argument
is 0, because none of the perturbers have the potential to be destroyed
completely. This makes the enumeration much faster.
To get an xlife file containing the two patterns in viewable form, use
perl makematrix.pl < restore.out
----
ptb2 works in depth-first fashion without any capability of avoiding
recursion on effectively identical branches (e.g. the eater 2 has the
same effect as a fishhook eater). To carry out longer searches, I
found it useful to add just one perturber at a time using some additional
scripts:
ptblist.pl is a perl script that runs ptb2 on a list of patterns to
be perturbed. It uses the second column on each line as the first
step when the perturber can be added. User 'Scorbie' on conwaylife forums
is the best person to ask about ptblist.pl. See for example this post
http://conwaylife.com/forums/viewtopic.php?f=9&t=1536&start=75#p24025.
uniq.pl is a perl script that only prints one example of each final pattern
based on the last column of output from survive (but this could eliminate
results that are not really duplicates for reasons of spacing).
runall.sh is a shell script that adds one perturber at a time to
a list of patterns and outputs to ph1.out, ph2.out, ..., ph7.out
You can try 'runall.sh picol.life' for example. This requires a lot
of disk space.
Some new catalyst files spartan.list, spartanlite.list and exotic.list were
added by Scorbie. Also see the following link for a detailed walkthrough:
http://conwaylife.com/forums/viewtopic.php?f=2&t=1808&start=25#p23900