Macbi wrote:Could you explain a little bit about how search programs work that search up to a certain number of bits? I can't imagine at all how the search would be organised. It seems much harder than searching in a given bounding box.

Back in the 1990s, I wrote a search program to look for still-lifes. The idea was based on a similar program written by Peter Raynham in the 1970s. My program started with an arbitrarily large area (effectively unbounded, because I was searching by population, and the area boundaries were chosen so that the population constraints would be reached long before any boundary was).

Each cell in the area can have one of three states - definitely dead, definitely alive, or presumably dead (but which may be changed to alive). One seed cell in the center starts out as definitely alive. Everything above it, or directly left, is definitely dead. Everything below it, or directly right, starts as presumably dead. Every cell has certain derived properties, such as how many living neighbors it has, whether it is stable or not (e.g. living cells are stable if they have 2-3 neighbors, dead cells are stable if they have any number other than 3), and the degree of freedom (i.e. the number of presumably dead cells).

I would then do a tree search. At every level, I would find the most unstable presumably dead cell with the lowest degree of freedom, and then try two searches, assuming it is definitely dead, or definitely alive. In each case, forcing a cell's state would lower the degrees of freedom of neighboring cells, and if an unstable cell's degrees of freedom was lowered to 0, it could not be fixed, rendering this entire search branch non-viable. There were other similar optimizations (e.g. an unstable dead cell with n neighbors required exactly 3-n additional ones, so once its degree of freedom reached 3-n, all of its remaining neighbors had to be forced to be alive).

This method grows patterns like crystals outward from the seed. Given that the processor time required is around O(2.45^n) and the number of objects found is also around O(2.45^n), the algorithm is pretty much optimal. I used this to search for still-lifes up to 24 bits. Unfortunately, due to certain defects in the algorithm (notably in choices as to when it was reasonable to expand to disconnected islands), there were certain classes of objects that were not found; these had to be added manually, which was an error-prone process. There were relatively few at 22-24 bits, but at 25 there would have been over a hundred. (As it was, a subsequent search for still-lifes this year revealed that I had forgotten to count a few 24s from my manual list due to bookkeeping errors.)

I modified the same program to search for oscillators, by treating oscillators as still-lifes in a cylindrical 3D space. I used this to search for period 2 oscillators. Unfortunately, the time required expanded much faster than the result space, as searching for n-bit oscillators turned into a search for still-lifes of approximately 2n bits. I was only able to search for ones up to 21 bits. I tried using the same pattern to search for period 3 and 4 oscillators, but the compuational cost increased so prohibitively that I wasn't even able to search up to 12 bits, which is when the first results would have been found.

A few years ago, Nikolay Beluchenko searched for period 3 oscillators up to 20 bits by using WLS, using a rectangular area that would be large enough to contain them all, and a second search of a diagonal strip to catch the few that would have been larger. That search found 10 that had not been known previusly. A similar search was done this year for the 21-bit ones, and found 4 that were not previously known. As all the 20-bit ones that required the diagonal strip search were all variants of "two eaters", it is unlikely that there would be any new 21-bit ones that would have been missed by not doing a similar 21-bit diagonal strip search.

H. Koenig searched for period 4 oscillators up to 12 bits, but as far as I know, nobody has done any larger population-based searches for any periods higher than 3.