Nick Gotts wrote:From: Nick Gotts
Date: Mon, 03 Nov 1997 13:01:42 +0000
Subject: Small pattern survey
The 8-cell survey is finished.
Unless I have made an error at some point, there are no infinite growth patterns with 8 or fewer cells. Discovering whether this was so (because of its implication for the long-term behavior of very sparse random fields, to which I'll return in a later message) was the main point of the survey: everything else reported here is incidental to that, and because of the way I processed most of the patterns, some of the information given may be subject to revision even if I haven't made any errors. Furthermore, some parts of the survey are less well documented than others. This does not affect the main conclusion, but does mean that some information that potentially could be available, is not. I hope to fill these gaps in documentation in the near future. I'll try to indicate clearly what information falls into which category.
I've tried to make this message fairly self-contained, so people don't have to go back to my earlier ones to understand it. This being so, some of what is here repeats parts of earlier messages. I've described my procedures in a reasonable amount of detail so that anyone who wishes can check for logical flaws. I'll gladly answer questions, and will provide code and data files if anyone really wants them.
In retrospect, it was an error to program in Pop-11 (which I know well) rather than C, which I don't. I thought that this would save my time, but the difference in efficiency turns out to be much greater than I expected, and I had to spend a lot of time writing relatively complex programs in order to minimise the computer time required. In C, I could have made much more use of BFI methods. I did, however, do some thinking -- e.g. about ways of combining clusters of cells (see below) in two-cluster patterns -- and gain some information -- about how quickly a large number of starting patterns converges onto a smaller number of successors -- that I wouldn't otherwise have done.
The saving in computer time referred to was achieved mainly by avoiding following the same pattern twice. Because of the way this was done (explained below), results such as "longest death agony", or "longest to quiescence" are not automatically available from the survey.
I checked all patterns with n cells before proceeding to those with n+1, any n-cell pattern which had a successor (immediate or not) with less than n cells did not need to be followed any further. Furthermore, patterns having a successor with their original number of cells did not need to be followed further, as this successor would itself get checked. Finally, patterns which had already been found as successors to some other pattern did not need to be followed. I included checks for all these possibilities in those parts of the search where they seemed likely to save significant time. The effect of this, however, is that for those parts of the search, I can't readily identify the longest-lasting pattern with certainty, or tell how many initial patterns led to some result; and I could have missed some new oscillators. With one exception, which I intend to remedy, I believe that all the information to answer these questions is somewhere in my files - but digging it out would be non-trivial.
Breakdown of the patterns checked
=================================
For each number n from 3 to 8, the procedure followed can be divided into two: cataloging all the n-cell patterns that need to be investigated, and following these patterns. For n from 6 to 8, we also need to distinguish "single-cluster" from "multi-cluster" patterns (see below).
Clearly, there is a sense in which there are an infinite number of GoL starting patterns for any number of cells greater than 1 (2 cells can be any distance apart). Equally clearly, we can ignore any patterns in which single cells, or pairs of cells, are isolated from the rest of the pattern. (Note that this would not be so for Game of Life variants in which birth requires less than 3 cells, or survival less than 2 apart from the cell itself.) Such cells will die on the first tick, and contribute nothing to the successor pattern -- so if a pattern containing isolated cells grows for ever, there will be a smaller pattern without them that also does so. The actual criterion used in my cataloging algorithm is that every on-cell in a starting pattern should fall within a 3*3 square containing at least two others (Note that any cell falls within 9 overlapping 3*3 squares. Note also that any pattern violating this criterion must include "useless cells", that can be removed without affecting the subsequent history, but that meeting the criterion does not guarantee there are no such cells.)
This criterion reduces the survey problem to finite size for any number of cells up to 5. For 6 or more cells, we could have two clusters of 3 or more cells each (three clusters if we start with 9 or more cells, up to n clusters if we start with at least 3n cells). For 6 or more cells, I therefore divide the problem into two: single-cluster and multi-cluster starting patterns. The definition of "single-cluster pattern" I have used is that for such a pattern, there must be a path along Moore-neighbourhood links (i.e. between immediate orthogonal or diagonal neighbours in the grid) from any on-cell to any other, which does not go through two consecutive off-cells. (I call such a pattern a "1-cluster", as opposed to a "0-cluster", or "plet", in which all cells are "kingwise connected". We can similarly define 2-clusters, 3-clusters...) Separate 1-clusters cannot interact on the first tick, so we can compute the successor of a pattern by considering its 1-clusters separately and summing the results. (Note that a 1-cluster may consist of 2 or more parts which do not interact -- again, I am using a sufficient but not necessary condition for non-interaction.) In what follows, "cluster" means 1-cluster.
As I've said, in order to show that there are no patterns of x cells that expand forever it is enough (provided that surveys for all lower numbers have already been done) to check on those patterns which show an increase in cell-number on the first tick. This does *not* mean that any pattern which grows for ever must increase cell number on the first tick, but if it doesn't, one of its successors, with the same or fewer cells, must do so. This applies both to single-1-cluster and multi-1-cluster patterns but for the latter, it is only the total number of cells that must increase on the first tick.
Cataloging Single-1-Cluster Patterns
====================================
My basic 1-cluster catalogs include (I hope and believe) all x-cell patterns consisting of a single 1-cluster, and in which every on-cell falls in a 3*3 square including at least 2 others. These are now complete up to 8 cells, the numbers of distinct patterns (rotations and reflections not being counted as different) being as follows:
1 cell: 0
2 cells: 0
3 cells: 10 (including 5 triplets)
4 cells: 66 (including 22 tetraplets)
5 cells: 551 (including 94 pentaplets)
6 cells: 8203 (including 524 hexaplets)
7 cells: 102845 (including 3031 heptaplets)
8 cells: 1334484
These catalogs would be suitable for investigating small patterns in any variant on Life where the minimum number of cells for birth or survival (including the cell itself) is 3. It would be straightforward to generate catalogs for variants where this minimum is 4 or more. If the minimum is less than 3, a catalog of all single 1-cluster patterns would be wanted. It would also be possible to compute clustering and isolation using the von Neumann rather than the Moore neighbourhood (but of course Xlife assumes a Moore neighbourhood).
Paul Callahan has now confirmed these numbers (and taken the single cluster enumeration on to 9 cells), using a very different algorithm. Mine involved first calculating the possible minimum bounding rectangles for single cluster patterns for each number of cells, and for each such m.b.r., the possible distributions of on-cells among rows. For each such distribution, possible patterns were then built up row-by-row, avoiding the generation of vertical and horizontal reflections, 180 degree rotations, and patterns with isolated cells altogether, and eliminating 90 degree rotations, diagonal reflections, and multi-cluster patterns when adding the final row. Paul's algorithm built up patterns one cell at a time in a single depth-first search, checking each generated pattern to eliminate rotations, reflections, etc. after generation. So we can be pretty confident of these numbers.
Cataloging Multi-1-Cluster Patterns
===================================
For 6 cells, we need to consider just patterns with two clusters of 3 cells each, and these must be very close together. To show an immediate increase in cell count, such a pattern must consist of one pre-block, and either a second pre-block or a blinker. Clearly, if these do not form a single 1-cluster after the first tick, they never will. There turn out to be just three such patterns that show real interaction, of which one becomes a honeyfarm, and two die:
For 7 cells, we need to consider patterns with two clusters of 4 and 3 cells. Since there is a 4-cell cluster that immediately increases to 7 cells, any 3-cell cluster that leaves any cells behind (i.e. any that meet the non-isolation criterion) can combine with this 4-cell cluster to produce >7 cells on the first tick. However, for 5 of the 10 3-cell clusters, it can be shown that they will disappear before interacting with any other 1-cluster (of any size or shape), and more detailed examination shows that there are only two patterns consisting of a 3-cell 1-cluster other than the blinker or pre-block with a 4-cell 1-cluster that need to be followed. What is more, we can in fact substitute the block for a preblock, meaning that we do not need to consider different orientations of the preblock separately. This is because, in any two-cluster pattern involving a preblock, we could always substitute any other preblock that would produce the same block at tick 1, or that block itself, without making any difference to the tick 1 pattern. Try drawing a preblock, and putting the tightest possible boundary round it such that anything inside the boundary would form part of the same cluster. This boundary surrounds a 6*6 square with a single cell missing at one corner. If the block were completed, an on-cell at that point would form part of the same cluster as the block, but could not interact with it without another on-cell being inside the boundary.
We need to consider combining the block and the blinker with all 4-cell clusters that produce at least 5 cells on the first tick. It might be thought that we also need to consider combining the (pre) block with any 4-cell cluster that gives rise to exactly 4 cells on the first tick, but such a two cluster pattern will always give the same result on the second tick as some 7-cell (one or two cluster) pattern on the first tick. (This is a bit tricky to explain, but try it out - there will always be a way of removing one cell from the block created from the pre-block at tick one, in such a way as to leave a 7-cell pattern that has the same successor as the 8-cell one including the block.)
In the 8-cell case, we need to consider both pairs of 4-cell 1-clusters, and combinations of 5-cell and 3-cell clusters, but can immediately eliminate those that fail to produce at least 9 cells on tick 1. In the 5-3 case, there are again only a very small number of cases where we need to follow a pattern where the 3-cell cluster is not a blinker or preblock. There are in fact just two (not counting rotations and reflections) where more than 8 cells result on tick 2:
and in fact each of these will give the same result at tick 2 as a single cluster pattern (substitute an appropriately placed
for the row of 5).
Also, we can again use the block instead of the variously oriented preblocks, so we only need to consider 5-cell patterns that give rise to more than 5 cells on tick 1, combined with the (pre) block, or the blinker (generally, we need to consider the two blinker orientations separately).
In the 4-4 case, we need to consider cases where one cluster gives rise to 7 cells on tick 1 and the other at least 2 (originally I intended to rule out the 7/2 case by general arguments, but these turned out to be rather complicated, so I left it in); where one gives rise to 6 and the other to at least 3; and where one gives rise to 5 and the other to at least 4. The symmetries of both must be taken into account if we want to cover all possible relative orientations, but avoid redundancy where possible. The procedures used for this are not described here. (I can go into this if anyone wants me to.)
Most of the 8-cell two cluster patterns that need looking at are in fact combinations of the r5 with a blonk; most of the rest are combinations of a pi-predecessor with a blonk. I note that there are in fact 8 5-cell predecessors of the r5, but none of these needed to be checked, as combining them with a blonk and moving forward 1 or 2 ticks would always lead to a pattern (single cluster or two cluster) equivalent to one that would be found either among the single cluster 8 cells, or among the r5-blonks. There are also two different 5-cell pi-predecessors (one of which is bilaterally symmetric, the other asymmetric), both of which grow to more than 5 cells on tick 1:
These remain distinct until tick 5 of the asymmetric one, which is the same as tick 4 of the symmetric. This case was dealt with by following all possibilities for the symmetric case, but only those which led to the possibility of interaction within ten ticks for the asymmetric.
In both 7-cell and 8-cell cases, a procedure was needed to find all possible relative positions of two initial clusters (given a specified relative orientation) that could result in an interaction at some stage. The approach taken was to calculate the "cumulative image" of each cluster -- that is, the set of cells occupied at some time during its evolution. In the case of the r5, a cut-off of 1103 ticks was used, after checking (using Xlife) that no r5-blonk interaction that occurred later than this could give rise to an infinite growth pattern. This check covers 216 different cases of a glider leaving the r5 and hitting a blonk, but in most of these the glider and blonk vanish or create a small still life; in only a few does a returning glider hit the r5 debris, and in all cases it is clear that moving the blonk further out would give the same final result, except for relative placings of the debris and spacing and timing of the fleeing gliders.
Given the cumulative image of a pair of initial single cluster patterns, another procedure was used to find all relative initial positions for which the initial patterns did not form a single cluster, but the cumulative images did. (In fact, the relationship of the cumulative images had to be slightly closer than this: if the two did not actually overlap, there had to be a cell in one that was at most a "knights move" from a cell in the other.) This test does not guarantee that the patterns would interact, but does catch all cases where they might do so.
Following Patterns
==================
For single cluster patterns, many n-cell patterns may have the same successor after 1 tick, many of these 1-tick successors may have the same 2-tick successor, and so on. Furthermore, a pattern may crop up both as a 1-tick and as a 2-tick successor, or more generally, may arise repeatedly after different numbers of ticks. Given the aim of the survey, it was not necessary to record all the possible ways such a pattern can be produced, and given the slowness of the GoL simulation part of the program, it was worth avoiding following such patterns repeatedly. The approach adopted was to run all n-cell single-1-cluster patterns in parallel one tick at a time in the initial stages ("phase 1"), discarding both those that declined to n or fewer cells and those that had been found on previous ticks, and noting which of the remaining patterns had the same successor on the current tick. At the end of phase 1 (when all patterns were quiescent in the 3 and 4 cell cases, after 16 ticks in the 5 cell case, 32 ticks in the 6 cell case, and 64 ticks in the 7 and 8 cell cases), the output was a list of "survivor" patterns that had not occurred on any earlier tick, and for which there was at least 1 path from a n-cell initial pattern which never subsequently dipped below n+1 cells. (One such initial pattern was retained for each of the survivors.) The survivor patterns were then followed using a different ("phase 2") GoL simulation program for up 1200 ticks (5 and 6 cell cases), 6000 ticks (7 cell case), and 4096 ticks (8 cell case). Up to 7 cells, these numbers were chosen in the (correct) expectation that no single-cluster patterns would avoid quiescence that long. The 4096-tick 8-cell survivors were checked individually using Xlife.
The phase 1 GoL simulation program uses a 2D binary array to represent a pattern. All patterns are advanced one tick in parallel. A successor is calculated for each pattern, then "normalised" (empty rows/columns trimmed, rotated 90 degrees if necessary to ensure there are no more rows than columns, 180 degree rotated or up-down or left-right reflected if necessary to ensure the row distribution was not bottom-heavy, and that the most "leftist" possible sequence of rows is achieved). The result is then matched against a list of all patterns already found on the current tick. Once all patterns had been moved on a tick, the new patterns are checked to ensure they contain enough cells, and have not been found on earlier ticks. (In fact, this description has been slightly adapted to make it more comprehensible, but the effect is as described here.)
It's worth noting that the phase 1 filtering procedure detects and removes not only static or oscillating patterns, but also single gliders or spaceships, or a salvo of gliders or spaceships, provided there is nothing else left in the pattern.
The phase 2 GoL simulation program represents a pattern as a list of lists of integers, each sublist representing a row. The first number in a sublist is the row number, the rest being the column numbers of the on-cells in that row. In this phase, each pattern is processed separately (Phase 2 actually restarts from an initial pattern, rather than from the pattern reached at the end of phase 1, for reasons of convenience.) After each tick, the pattern is compared with its predecessor. After every even-numbered tick, it is compared with the pattern from two ticks previously. In both cases an exact match is required. After every twelve ticks, a more complex matching process is applied (if the one-tick and two-tick matches fail):
(1) The number of on-cells is checked. If it is not the same, the match fails.
(2) The two patterns are matched, and the common on-cells and those cells in the old pattern but not the new are recorded.
(3) The "only in old" cells are checked to see if they consist solely of gliders (a glider will be recognised in any orientation and phase, but must have at least 3 empty cells separating it from anything else). (The case where there are no "only-in-old" cells is provided for.) If they do not, the match fails.
(4) It is checked:
(a) That all the gliders are outside a rectangle consisting of the minimum bounding rectangle of the "in both" cells, plus a border 4 cells wide (this ensures, given that the "in both" cells are identical 12 ticks on, that the gliders cannot be caught by anything from within the minimum bounding rectangle, provided they are moving away from it). (The case where there are no "in both" cells is provided for.)
(b) That all the NW-heading gliders are N and/or W of the rectangle, and similarly for the other 3 glider orientations.
(c) That all the NW gliders are W of all the NE gliders and N of all the SE gliders, and similarly for the other orientations.
If all these tests are passed, it is concluded that the pattern is "dead". Note that a "dead" pattern may pass all these tests, if it includes a spaceship, or a pair of very close gliders, or an oscillator of a period not a divisor of 12 (the only one that arose was a pentadecathlon).
For the 6 cell and 7 cell two cluster cases, and some of the 8 cell subcases (all but the r5/blonk and pre-pi/blonk subcases), the same procedure was followed as for the single-1-cluster patterns. For the remainder of the 8 cell subcases, phase 1 was omitted, as it was thought that few of these patterns would have common successors at any stage. Each was therefore followed individually for 4096 ticks using the "phase 2" program, then using Xlife if necessary.
Incidental 8-cell Results
=========================
Longest-to-quiescence pattern found, at 14,319 ticks:
Code: Select all
x = 34, y = 7
31b2o$32b2o$32bo4$3o!
Longest-to-quiescence single cluster pattern found, at 7468 ticks (I've already posted this, but a recent message asked the question again!):
Neither of these is guaranteed to be the true maximum (though I'd bet on the 14319, which -- excluding error, and patterns which last longer solely because of delays while gliders cross empty space -- is definitely maximal among the r5+blonks), because of the way I've followed the single cluster and some two cluster patterns. There could easily be a single cluster pattern that takes a few ticks longer than the 7468 to reach the same destination, and its *just* possible there is one that takes much longer. It's interesting to note that if we include *all* r5+blonk patterns, there is no limit to how long an 8 cell pattern can take to reach quiescence, although any particular pattern will do so in a finite number of ticks.
On the matter of longest death agonies, I've no new information (actually, I don't find this a particularly interesting question). I haven't done a systematic check through all my records, and the records for the single-cluster patterns are currently the scantiest (I only have the number of ticks to quiescence, not the final number of cells, for these patterns.) I'm currently rerunning the 1556 different patterns produced by my "phase 1" procedure to improve these records, and I'll report whether this turns up anything Paul didn't find. (Of course, a negative result won't be conclusive here, as explained above.) I have checked the records for patterns with two clusters of 4 cells, and the 5-3 records other than r5-blonk and pi-blonk. Nothing quite as long-lasting as Paul's pattern came up.
Paul has already posted one 8-cell pattern that produces a HWSS. Here is another:
Code: Select all
x = 45, y = 13
2o$o9$42b2o$43b2o$43bo!
This is an r5+preblock pattern, and we can of course rotate the preblock to produce three more 8-cell patterns giving the same result. Furthermore, from each of these four, and from the r5+blinker which Paul posted, we can produce another eight by substituting 5-cell predecessors of the "standard" r5 for that standard r5: so there are in fact 45 8-cell patterns that produce an HWSS, not counting rotations and reflections of the entire pattern. Using the same approach, I count at least 73 8-cell patterns that produce an MWSS and at least 725 that produce a single LWSS (the "at least" here is because there are single cluster patterns among those that produce an LWSS, and at least one that produces an MWSS, and as explained above, each of those I have recorded may represent more than one initial pattern).
There is also a set of 9 patterns that produce two LWSSs, going in opposite directions: these, unlike any other 8-cell patterns, expand their diameter at the speed of light - a maximum for finite patterns. Here is one of the 9 (to get the others, just substitute the 5-cell r5-precursors, switching the blinker orientation if necessary):
Since they also send out gliders in 4 directions, these patterns emit objects in 6 directions altogether.
One more pattern of some interest: in addition to the pairs of traffic-light predecessors that produce a lone pentadecathlon, there is a set of 12 closely related pi+preblock patterns that produce one as part of a cloud of debris. Here is one:
Nick