pipsqueek wrote: November 28th, 2022, 6:05 pmHow do spaceship search programs work? I read David Eppstein's "Searching for Spaceships" paper, he mentions algorithms like breadth first search. and doesn't explain how the search program works very well. in general, what kind algorithm do most search programs use?
I'm not sure exactly what algorithm that modern search programs use, but this is what I used in my old search program that I originally used to find all the still-lifes up to 23 bits (and most of the 24s):
I start with a grid with a single live seed cell fixed in the center. All cells on above rows, and on the same row as the seed left of it, are fixed at 0. All cells below and to the right are set as flexible - i.e. "provisionally 0, but may also become 1". Each cell as associated with it a neigbhorhood count (from 0-8), and a degree of freedom (from 0-8) that indicates the number of adjacent flexible cells. A cell is also noted as stable (alive with 2-3 neighbors or dead with 3) or unstable otherwise.
Searching is recursive. A cell is chosen to explore; it is then explored as if it was fixed at 0, and then again as if it was fixed at 1. Fixing a cell to 0 decrements the degree of freedom of all adjacent cells. Fixing a cell to 1 does the same, and also increases their neighborhoods by 1. The key to fast searching is picking the best candidate to search first. Peter Raynham wrote a similar program in the 1970s whose running time was O(4^n). After much fine tuning, mine runs at around O(2.54^n), and since the total number of still-lifes and pseudo-still-lifes is also around O(2.54^n), this indicates that the search methodology is close to optimal, with almost no waste.
I keep a list of cells sorted first by viability, and then by degree of freedom. Non-viable cells are explored first, because if they can't be made viable, there's no point in searching further. Living cells with too many neighbors are automatically disqualified. Living cells with 1 neighbor require at least one more; if they have exactly 1 degree of freedom, the one adjacent flexible neighbor is forced on; if they have none, this cell is disqualified. Living cells with 0 neighbors similarly require at least two more; if they have exactly 2 degrees of freedom, both adjacent flexible neighbors are forced on; if they have 0 or 1, this cell is disqualified. It's similar with unstable dead cells; they must add at least one additional live neighbor to become stable.
If none of the above mandates need to be enforced, the cell is explored both as forced to 0 and forced to 1. Doing this to cells with the lowest degree of freedom first ensures that non-viable situations are found quickly and discarded. This tends to create patterns with dense clusters of fixed cells, with flexible cells around the edges. Whenever a pattern is found that has zero non-viable cells, it is output (assuming that it matches configured search criteria, e.g. searching only for 14-bit still-lifes will ignore anything smaller). Attempting to place a cell that causes the population to exceed the configured maximum will immediately fail. Attempting to force a cell that is already fixed in one state to a different state also immediately fails.
Once everything has been searched, the output consists of all possible still-lifes that match the search criteria - possibly with many rotations and reflections (that can be removed by a post-processing filter). Also, separating pseudo-still-lifes from true still-lifes is more easily done in post-processing.
It's possible to search for specialized types of still-lifes by pre-initializing the search space with fixed live and dead cells. E.g. to find all still-lifes that could potentially support a mold rotor, you could start with a living loaf, leave all cells near the diagonal edge (where the mold rotor would go) fixed to 0, and leave the rest flexible.
Searching for oscillators can be done by extending the search space to 3 dimensions, with the third dimension being time, and that wraps around in a torus. The search is now for 3-dimensional still-lifes, with each cell deriving neighbors degrees of freedom from the layer below, and contributing neighbors to the layer above. Sadly, the run time escalates much more quickly this way, so I was only able to search period 2 oscillators up to 21 bits (which took several weeks of steady grinding), and for higher periods, it became impractical, as I wasn't even able to find the 12-bit period-3 and period-4 oscillators within a reasonable time frame. (That was done in the 1990s, so it's likely that much fasters computers these days might be able to do so).
Searching for spaceships could be done similarly - by twisting the torus so the cells on the top layer are adjacent to ones on the bottom layer, offset by a fixed value of your choice.
One could similarly search for oscillators of 2x or 4x the search period, or spaceships for 2x that period, by applying glide symmetry to the translation from the top to the bottom layer. Most spaceship search programs that find higher-period spaceships do this. (E.g. a period-3 search with glide symmetry can yield period-6 glide-reflected spaceships).
Most modern oscillator and spaceship search programs seem to constrain their searches to fixed narrow rectangular strips, rather than by population. This is similar to how my program works if given only a small area of flexible cells.