Enumerating Still Lifes (in C)

[Apple Bottom]

I noticed the new section about Fake still lifes on the wiki.
For the generalized still life searcher I need to find a clear definition of strict/pseudo still lifes versus fake still lifes for non-standard rules. I can think of a possible definition but I guess this must have been considered before in Catagolue for example?

Yes, I put that in earlier today after Saka asked about the difference on my user talk page. I'm not actually sure "fake still life" is a standard term of art, but it's what the venerable still life infobox template on the LifeWiki calls certain constellations.

The difference, in a nutshell and as best as I can tell, is that a pseudo still life is one object, while a fake still life is merely one pattern (consisting of multiple objects).

I'm playing around with some optimization ideas, and I'll be happy to help out with increasing the number of subsets, seaching some of them, etc. But I think I'll have to leave it to someone else to organize a search to 31-32 bits...

I discovered a small bug in the current version of the still life searcher that only affects searches where <max on cells> is in the range 9 to 12 bits. The division into subsets uses the first 9 on-cells to define which subset is being searched, and counting the subsets didn't work correctly when <max on cells> was too close to that. This is fixed now in an update.
This should not have affected a search such as "sc w 4 23", even though that range is included there, but I'll verify that the database is correct for those bit counts.

Right, thanks for the heads-up. I'll make sure to grab the new version. (Hmm, I wonder why Github didn't alert me to the activity in your repo even though I "Watched" it.)

Seems as if "fake still life" is a category that was invented for LifeWiki purposes, for things like the blockade that have names and are clearly stable (P1) but are not strict still lifes, pseudo still lifes, or eaters.

"Fake" doesn't seem like quite the right label -- at least, it implies to me that the object looks stable but actually isn't, or something weird like that. I think the usual label for a blockade would be a "still life constellation". Could "constellation" be used instead of "fake" in Template:Stilllife?

Certainly, that's an easy change, let me just go ahead and do that. (Unfortunately categories cannot be renamed in MediaWiki, so I'll have to delete and recreate those, but there's not too many of those to start with.)

EDIT: all done on the wiki.

[mniemiec]

I noticed the new section about Fake still lifes on the wiki.
For the generalized still life searcher I need to find a clear definition of strict/pseudo still lifes versus fake still lifes for non-standard rules.

It seems like the wiki's definition here is that any configuration with a period of 1 that isn't a still-life or a pseudo-still-life is a fake still-life. That should be a robust definition, as long as you already have robust definitions for still-life and pseudo-still-life. The original term used for disjoint collection of objects is "constellation". Personally, I use the term "Still constellation" for several disjoint still-lifes and/or pseudo-still-lifes (e.g. blockade).

Years ago, I coined the term "quasi-still-life" (and generalized "quasi-object"), for use by my still-life enumerator, to refer to objects that share dead cells (so the neighborhoods of those dead cells are changed), but otherwise do not have any effect (e.g. all cells that used to remain dead from under-population still do so). There are 6 8-bit ones:

Code: Select all

x = 81, y = 6, rule = B3/S23
bo3bo10bo13boo13boo14bo14bo$obobobo8bobobbo9boo13boo13bobo12bobo$bo3bo
10bobbobo27bo11bo3bo10bo$20bo12boo13bobo13bobo12bo$33boo14bo15bo12bobo
$79bo!

In case anyone cares, the following number of them exist for the first few sizes:
(EDIT: Adding simeks's rows for 21+22, and correction for 9):

Code: Select all

Size    Quasi-still-lifes
8       6
9       13
10      57
11      141
12      465
13      1224
14      3956
15      11599
16      36538
17      107415
18      327250
19      972040
20      2957488
21      8879327
22      26943317

Other than counting them, I don't consider them particularly interesting, as synthesizing them should be mostly trivial. But since the issue has come up, I will take a brief look at them to see if there are any I can find that don't have trivial syntheses. They should be considerably easier than pseudo-still-lifes. So far, the expert system has found syntheses for all up to 15 bits, except the one below. (EDIT: There are also 7 unknown 16s, 6 of which would need a missing "add tub to corner" recipe). I had to add five new trivial recipes to add nearby objects (since those were never needed there before), but all used known methods.

Code: Select all

x = 113, y = 8, rule = B3/S23
oobboobo8bo3bo10bo3bo9bo5bo8boo4bo11boo12bo13bo$o3boboo7bobobobo8bobob
obo8b3obbobo7bobobbobo9bobo11bobobbo8bobobbo$bo14bo3bo10bo3bo12bobbo
10bo3bo9bo15bobbobo8bobbobo$bbo44bo13bo13bo5boo13bo13bo$3bobo10bo3bo
11bo3bo10boobbo9boobbo9boo5bo8bo15bo$4boo9bobobobo9bobobobo12bobo11bob
o14bo8bobobbo10bobobbo$16bo3bo11bo3bo14bo13bo12bobo10bobbobo10bobbobo$
78boo15bo15bo!

The number of quasi-still-lifes seems be around O(3.04^n), so they increase much faster than still-lifes. Curiously, the number of still-lifes is around O(2.46^n) while the number of pseudo-still-lifes is around O(2.56^n), so the pseudos should eclipse the strict still-lifes at size 31 (around 2.27 billion still-lifes, and 2.34 billion pseudo-still-lifes).

[simeks]

For the generalized still life searcher I need to find a clear definition of strict/pseudo still lifes versus [constellations] for non-standard rules. I can think of a possible definition but I guess this must have been considered before in Catagolue for example?

I think I need to be clearer about what I mean, and coming to think of it, I don't think this question has been needed to consider in Catagolue.

Let's look at this simple pattern:

Code: Select all

x = 5, y = 2, rule = B3/S23
2ob2o$2ob2o!

Two off-cells have 4 on-cell neighbours each.
If the rule is standard life, B3/S23, those two cells are "overloaded" (birth is prevented because there are too many on-cell neighbours).
Because there are two islands, each of which is stable by itself, but they are connected by at least one overloaded cell, we consider it a pseudo still life.

Suppose instead the rule is B5/S23.
Now there are no overloaded cells, and the pattern should be considered a constellation, right?

What if the rule is B35/S23?
The two cells between the blocks are now "semi-overloaded"... Is it a pseudo still life or a constellation?

What is the general rule to decide if an off-cell connects two islands that are each stable by itself, into a pseudo still life?

[calcyman]

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

So, yes, it is a pseudo-still-life in B35/S23.

[Apple Bottom]

Let's look at this simple pattern:

Code: Select all

x = 5, y = 2, rule = B3/S23
2ob2o$2ob2o!

Two off-cells have 4 on-cell neighbours each.
If the rule is standard life, B3/S23, those two cells are "overloaded" (birth is prevented because there are too many on-cell neighbours).
Because there are two islands, each of which is stable by itself, but they are connected by at least one overloaded cell, we consider it a pseudo still life.

Suppose instead the rule is B5/S23.
Now there are no overloaded cells, and the pattern should be considered a constellation, right?

What if the rule is B35/S23?
The two cells between the blocks are now "semi-overloaded"... Is it a pseudo still life or a constellation?

What is the general rule to decide if an off-cell connects two islands that are each stable by itself, into a pseudo still life?

My personal gut feeling is that pseudo-objects and constellations are distinguished by what one might call the "zone of influence" of their constituent parts. Suppose you have an object that is made up of two stable minimal subpatterns (i.e. stable subpatterns that cannot be further divided into smaller stable subpatterns). Consider the Moore neighborhoods of those subpatterns. If those neighborhoods overlap, the pattern is a pseudo still life; otherwise it's a constellation.

This is the same irrespective of which rule you use, so long as the rule a) uses the Moore neighborhood (a similar definition can be given for the von Neumann neighborhood), and b) cells are only influenced, in each generation, by their *direct* neighbors (there's no "spooky action at a distance"). In particular, the definition is the same for all totalistic and semi-totalistic rules that Catagolue currently supports.

The definition can also be extended to patterns composed of more than two stable minimal subpatterns. For example, this:

Code: Select all

x = 9, y = 2, rule = B3478/S4
2ob2o2b2o$2ob2o2b2o!

is a constellation composed of one pseudo still life and one still life.

[simeks]

Years ago, I coined the term "quasi-still-life" (and generalized "quasi-object"), for use by my still-life enumerator, to refer to objects that share dead cells (so the neighborhoods of those dead cells are changed), but otherwise do not have any effect (e.g. all cells that used to remain dead from under-population still do so). There are 6 8-bit ones:
...
In case anyone cares, the following number of them exist for the first few sizes:

I was able to confirm those numbers with my search program (except for what is clearly a typo for 9 bits, where the count should be 13 instead of 9). I also computed two new values:

Code: Select all

Bits	Quasi still-lifes
21		 8879327
22		26943317

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

Yes, that is the definition I had in mind, nice to have that confirmed!

Consider the Moore neighborhoods of those subpatterns. If those neighborhoods overlap, the pattern is a pseudo still life; otherwise it's a constellation.

But wouldn't that make a pattern like:

Code: Select all

x = 11, y = 6, rule = LifeHistory
6.4B$.6B2A2B$2B2ABDA2BAB$BA2BADB2A2B$2B2A6B$.4B!

a pseudo still life? Their Moore neighbourhood clearly overlap. I think your definition matches Mark Niemiec's definition of a quasi still-life above.

[Apple Bottom]

Consider the Moore neighborhoods of those subpatterns. If those neighborhoods overlap, the pattern is a pseudo still life; otherwise it's a constellation.

But wouldn't that make a pattern like:

Code: Select all

x = 11, y = 6, rule = LifeHistory
6.4B$.6B2A2B$2B2ABDA2BAB$BA2BADB2A2B$2B2A6B$.4B!

a pseudo still life? Their Moore neighbourhood clearly overlap. I think your definition matches Mark Niemiec's definition of a quasi still-life above.

Hmm. Yes, it would, good point. So perhaps this is a sort of in-between category between pseudo still lifes and constellations.

I do like the term "quasi still life" for these. Something to add to the article, then? (Having a handy, agreed-upon name and definition would also allow submitting Mark's counts to the OEIS.)

[mniemiec]

What is the general rule to decide if an off-cell connects two islands that are each stable by itself, into a pseudo still life?

I don't think this has ever been formally defined, but pseudo-still-lifes weren't originally thought of either. I came up with the idea when I was developing my still-life searcher, and needed to specifically search for those, but also needed to separare them from strict still lifes.

The rule I use is this:

If any part of one island affects any part of another, there is at least a weak pseudo-object connection. For example, in the case of block-on-block, removing one adjacent live cell from one block enables a birth between them, which that cell suppresses. This would make it a pseudo-object in any rule that has B3 but not B4, including B35/S23.

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

Exactly!

This is the same irrespective of which rule you use, so long as the rule a) uses the Moore neighborhood (a similar definition can be given for the von Neumann neighborhood), and b) cells are only influenced, in each generation, by their *direct* neighbors (there's no "spooky action at a distance"). In particular, the definition is the same for all totalistic and semi-totalistic rules that Catagolue currently supports.

Right. There is no "action at a distance", although the connection rules apply inductively. An object connection is the strongest, and also implies a pseudo-object connection. A pseudo-object connection is weaker, and also applies a quasi-object connection. If a+b is an object, and b+c is a pseudo-object, a+b+c is a pseudo-object.

I was able to confirm those numbers with my search program (except for what is clearly a typo for 9 bits, where the count should be 13 instead of 9). I also computed two new values:

Oops! Yes, it's indeed 13; I just copied the wrong number to my status table. Thanks for the two new numbers. I ran the 21s yesterday, but ran out of disk space for the sorting pass, so I haven't gotten around to process the results yet.

I do like the term "quasi still life" for these. Something to add to the article, then? (Having a handy, agreed-upon name and definition would also allow submitting Mark's counts to the OEIS.)

(With simeks's correction and expansion, of course). Thanks. It's good to have a common term, to allow discussion.

[Apple Bottom]

This is the same irrespective of which rule you use, so long as the rule a) uses the Moore neighborhood (a similar definition can be given for the von Neumann neighborhood), and b) cells are only influenced, in each generation, by their *direct* neighbors (there's no "spooky action at a distance"). In particular, the definition is the same for all totalistic and semi-totalistic rules that Catagolue currently supports.

Right. There is no "action at a distance", although the connection rules apply inductively. An object connection is the strongest, and also implies a pseudo-object connection. A pseudo-object connection is weaker, and also applies a quasi-object connection. If a+b is an object, and b+c is a pseudo-object, a+b+c is a pseudo-object.

I was able to confirm those numbers with my search program (except for what is clearly a typo for 9 bits, where the count should be 13 instead of 9). I also computed two new values:

Oops! Yes, it's indeed 13; I just copied the wrong number to my status table. Thanks for the two new numbers. I ran the 21s yesterday, but ran out of disk space for the sorting pass, so I haven't gotten around to process the results yet.

I do like the term "quasi still life" for these. Something to add to the article, then? (Having a handy, agreed-upon name and definition would also allow submitting Mark's counts to the OEIS.)

(With simeks's correction and expansion, of course). Thanks. It's good to have a common term, to allow discussion.

Is is indeed!

Just to be clear again, though, what is the current agreed-on definition of "quasi still life", though? I was just going to add a section to the Wiki article, and realized that your definition and my above "gut feeling" aren't equivalent (as far as I can tell).

Specifically, with your definition, quasi still lifes are distinct from pseudo still lifes. The latter require at least one dead cell in the "zone of shared influence" that has >3 live neighbors in the unseparated pattern, but which has <3 live neighbors when each stable subpattern is considered individually. (Quoting the Wiki: "Furthermore, there must be at least one dead cell that has more than three alive neighbours in the overall pattern but has less than three alive neighbours in the subpatterns.")

Quasi still lifes meanwhile have the opposite requirement, if I understand correctly. Quoting what you wrote, above: "Years ago, I coined the term "quasi-still-life" (and generalized "quasi-object"), for use by my still-life enumerator, to refer to objects that share dead cells (so the neighborhoods of those dead cells are changed), but otherwise do not have any effect (e.g. all cells that used to remain dead from under-population still do so).".

So an object is either a pseudo still life or a quasi still life (or possibly neither) -- but never both. Right?

Finally, my own "gut feeling" from above makes no further statement about the dead cells in the "zone of shared influence", other than that there must be at least one (i.e. said zone is non-empty), so it seems to me that what I described is actually the union of pseudo and quasi still lifes. (Since these are in contrast to strict still lifes, perhaps they should simply be collectively called "non-strict still lifes".)

Drawing some ASCII art, I therefore think that right now, we have:

Code: Select all

                          Stable pattern
                                |
                      +---------+---------+
           One object |                   | Several objects
                      v                   v
                Stable object        Constellation
                      |
            +---------+---------+
Inseparable |                   | Separable
            v                   v
  Strict still life       Non-strict still life
                                |
                      +---------+---------+
             >3 -> <3 |                   | !(>3 -> <3)
                      v                   v
              Pseudo still life    Quasi still life

Or am I hopelessly confused now?

(The diagram could be continued, of course: strict still lifes could be distinguished into connected and non-connected, and constellations could consist of all manners of things.)

[calcyman]

Quasi-objects are considered to be constellations, I believe.

[mniemiec]

Just to be clear again, though, what is the current agreed-on definition of "quasi still life", though? I was just going to add a section to the Wiki article, and realized that your definition and my above "gut feeling" aren't equivalent (as far as I can tell).

If two or more objects or pseudo-objects are close enough that they share a dead cell, but not close enough that they would be considered the same object or pseudo-object, they form a quasi-object (e.g. two adjacent tubs). ("or more" may be superfluous, but it's probably safest to include it; it may only actually occur in cases of some uninteresting rules, e.g. four adjacent blocks in B5/S3.)

So an object is either a pseudo still life or a quasi still life (or possibly neither) -- but never both. Right?

Yes, and no. Strict still-lifes, pseudo-still-lifes, and quasi-still-lifes are mutually exclusive. However, pseudo-still-lifes and quasi-still-lifes are patterns, but neither is an object.

A pattern's connectivity (e.g. strict object, pseudo-object, quasi-object, or constellation) is independent of its periodicity (e.g. stable, oscillating, or unstable).

Stable patterns can be still-lifes (e.g. block), pseudo-still-lifes (e.g. two adjacent blocks), quasi-still-lifes (two adjacent tubs), or still constellations (e.g. blockade).
Stationary oscillating patterns can be oscillators (e.g. blinker), pseudo-oscillators (e.g. block on beacon), quasi-oscillators (e.g. traffic light), or oscillating constellations (bookend ash).
Moving patterns can be spaceships (e.g. LWSS), pseudo-spaceships (LWSS on LWSS), quasi-spaceships (two MWSS with belly sparks close to each other), or moving constellations (several spaceships moving in tandem).

Drawing some ASCII art, I therefore think that right now, we have: ...

This diagram is correct, but you should not use the term "object" here. Perhaps "stable cluster" would be better, where any two adjacent living cells or dead cells w/1+ living neighbors are part of the same cluster.
EDIT:

Quasi-objects are considered to be constellations, I believe.

Under existing definitions, that do not distinguish quasi-objects, this is true. (Originally, pseudo-objects were also considered constellations. In fact, apgsearch currently still treats them as such.)

[Apple Bottom]

Drawing some ASCII art, I therefore think that right now, we have: ...

This diagram is correct, but you should not use the term "object" here. Perhaps "stable cluster" would be better, where any two adjacent living cells or dead cells w/1+ living neighbors are part of the same cluster.

OK, great! Thanks for the explanations, I think I've understood it all now. (Famous last words again!)

"Cluster" is a good term, I like that.

[simeks]

I'll consider how to bundle them up into suitable files for the final database.

I created a set of files for the database using a script added to the repository to join the output files and then partition them into parts with at most 100 million still lifes. This is the file listing, the total size is about 13 GB:

Code: Select all

-rw-r--r-- 1 root root  20263016 Jan 19 16:41 04-23_bits.tar.xz
-rw-r--r-- 1 root root  13072952 Jan 19 16:37 24_bits_pseudo.txt.xz
-rw-r--r-- 1 root root  17674956 Jan 19 16:37 24_bits_strict.txt.xz
-rw-r--r-- 1 root root  33809368 Jan 19 16:37 25_bits_pseudo.txt.xz
-rw-r--r-- 1 root root  43557648 Jan 19 16:37 25_bits_strict.txt.xz
-rw-r--r-- 1 root root  88255880 Jan 19 16:37 26_bits_pseudo.txt.xz
-rw-r--r-- 1 root root 108271168 Jan 19 16:37 26_bits_strict.txt.xz
-rw-r--r-- 1 root root 230938520 Jan 19 16:37 27_bits_pseudo.txt.xz
-rw-r--r-- 1 root root 270110816 Jan 19 16:38 27_bits_strict.txt.xz
-rw-r--r-- 1 root root 444413800 Jan 19 16:38 28_bits_pseudo_part_0.txt.xz
-rw-r--r-- 1 root root 164480452 Jan 19 16:38 28_bits_pseudo_part_1.txt.xz
-rw-r--r-- 1 root root 449586056 Jan 19 16:38 28_bits_strict_part_0.txt.xz
-rw-r--r-- 1 root root 229347404 Jan 19 16:38 28_bits_strict_part_1.txt.xz
-rw-r--r-- 1 root root 451641404 Jan 19 16:38 29_bits_pseudo_part_0.txt.xz
-rw-r--r-- 1 root root 457330432 Jan 19 16:38 29_bits_pseudo_part_1.txt.xz
-rw-r--r-- 1 root root 454139096 Jan 19 16:38 29_bits_pseudo_part_2.txt.xz
-rw-r--r-- 1 root root 244299592 Jan 19 16:38 29_bits_pseudo_part_3.txt.xz
-rw-r--r-- 1 root root 458200364 Jan 19 16:39 29_bits_strict_part_0.txt.xz
-rw-r--r-- 1 root root 458681928 Jan 19 16:39 29_bits_strict_part_1.txt.xz
-rw-r--r-- 1 root root 459113644 Jan 19 16:39 29_bits_strict_part_2.txt.xz
-rw-r--r-- 1 root root 338520220 Jan 19 16:39 29_bits_strict_part_3.txt.xz
-rw-r--r-- 1 root root 457037332 Jan 19 16:39 30_bits_pseudo_part_0.txt.xz
-rw-r--r-- 1 root root 464966132 Jan 19 16:39 30_bits_pseudo_part_1.txt.xz
-rw-r--r-- 1 root root 469291308 Jan 19 16:39 30_bits_pseudo_part_2.txt.xz
-rw-r--r-- 1 root root 465246444 Jan 19 16:39 30_bits_pseudo_part_3.txt.xz
-rw-r--r-- 1 root root 466922868 Jan 19 16:40 30_bits_pseudo_part_4.txt.xz
-rw-r--r-- 1 root root 464051772 Jan 19 16:40 30_bits_pseudo_part_5.txt.xz
-rw-r--r-- 1 root root 465024024 Jan 19 16:40 30_bits_pseudo_part_6.txt.xz
-rw-r--r-- 1 root root 467451652 Jan 19 16:40 30_bits_pseudo_part_7.txt.xz
-rw-r--r-- 1 root root 470224912 Jan 19 16:40 30_bits_pseudo_part_8.txt.xz
-rw-r--r-- 1 root root  65388940 Jan 19 16:40 30_bits_pseudo_part_9.txt.xz
-rw-r--r-- 1 root root 464137960 Jan 19 16:40 30_bits_strict_part_0.txt.xz
-rw-r--r-- 1 root root 468938544 Jan 19 16:40 30_bits_strict_part_1.txt.xz
-rw-r--r-- 1 root root 474489964 Jan 19 16:41 30_bits_strict_part_2.txt.xz
-rw-r--r-- 1 root root 469025300 Jan 19 16:41 30_bits_strict_part_3.txt.xz
-rw-r--r-- 1 root root 468626152 Jan 19 16:41 30_bits_strict_part_4.txt.xz
-rw-r--r-- 1 root root 466547524 Jan 19 16:41 30_bits_strict_part_5.txt.xz
-rw-r--r-- 1 root root 467388752 Jan 19 16:41 30_bits_strict_part_6.txt.xz
-rw-r--r-- 1 root root 472553996 Jan 19 16:41 30_bits_strict_part_7.txt.xz
-rw-r--r-- 1 root root 474201596 Jan 19 16:41 30_bits_strict_part_8.txt.xz
-rw-r--r-- 1 root root 123179580 Jan 19 16:41 30_bits_strict_part_9.txt.xz

Now we just need somewhere to post them, like archive.org as suggested by Apple Bottom.
Any other ideas? Would someone be willing to help making the arrangements for this?

[Nathaniel]

I really wanted to know whether or not there was a 31-bit triple/quad pseudo still life, so I ran the search for 31-bit still lifes. Numbers:

31-bit strict still lifes: 2299616637
31-bit pseudo still lifes: 2364815358

And as a bit of a double-check I confirmed that the 30-bit numbers output by this search agreed with those posted earlier. I did not keep a database of all of the still lifes found, but can confirm that the script did not report any triple/quad pseudo still lifes. I'm now running the search for 32-bits to make sure that the 32-bit triple pseudo still life that we already know of is indeed found.

[Apple Bottom]

I really wanted to know whether or not there was a 31-bit triple/quad pseudo still life, so I ran the search for 31-bit still lifes. Numbers:

31-bit strict still lifes: 2299616637
31-bit pseudo still lifes: 2364815358

And as a bit of a double-check I confirmed that the 30-bit numbers output by this search agreed with those posted earlier. I did not keep a database of all of the still lifes found, but can confirm that the script did not report any triple/quad pseudo still lifes. I'm now running the search for 32-bits to make sure that the 32-bit triple pseudo still life that we already know of is indeed found.

Wow, excellent! I've updated the wiki in all the right places (I hope).

Someone just needs to submit an update for https://oeis.org/A019473 and https://oeis.org/A056613 on the OEIS now.

[Nathaniel]

As a follow-up to my previous post, I'm happy to report that Nivasch's 32-bit triple-pseudo-still-life was indeed found and detected by the script (in subset 21, if anyone is curious). Thus I can confirm that this is indeed the smallest >2 island pseudo still life that exists. I'll keep running the search to finish the 32-bit still life count and see if any others are found.

[mniemiec]

As a follow-up to my previous post, I'm happy to report that Nivasch's 32-bit triple-pseudo-still-life was indeed found and detected by the script (in subset 21, if anyone is curious). Thus I can confirm that this is indeed the smallest >2 island pseudo still life that exists. I'll keep running the search to finish the 32-bit still life count and see if any others are found.

This is great news (icing on top of the cake - the still-lifes up to 24 bits were counted in 1998, and then nothing for almost two decades - and suddenly this was increased to 31 (and soon 32) within a few short months).

I'm curious how difficult it would be to expand this search to include period 2 oscillators? My original search program searched for those by searching for still-lifes in a cylindrical 3D CA, where each cell's state is determined solely by the sate of the 9 neighboring cells on the previous layer. Unfortunately, the CPU time required increased substantially faster than the result objects, so it was not optimal - and by the time I searched for the 21-bit P2s in 2007, the search took several weeks - and the 22s wold have been impractical. However, I'm sure that with faster computers (and faster algorithms) a decade later, that limit cold probably also be expanded.

[Nathaniel]

32-bit still life counts:

Strict: 5716948683
Pseudo: 6123084116

And the already-known 32-bit triple-pseudo-still life is the unique pseudo still life of 32 or fewer bits requiring a decomposition into 3 or more pieces. The results for each of the 100 subsets of the search space for 24 to 32 bits are attached to this post.

The only remaining questions that I can think of are:

• Is there are 33-bit pseudo still life requiring a decomposition into 4 pieces? Currently the smallest known has 34 bits.
• Is the 34-bitter mentioned above unique?

I've started the 33-bit search, but I may or may not complete it.

[Apple Bottom]

Over in the apgsearch 3.1 thread, another used asked for a list of 14- and 15-bit still lifes not yet seen on Catagolue. In order to determine these, I converted the (smaller) still lifes enumerated generated by simeks's tool to their respective apgcodes.

I figure that these lists may be useful to others as well, so I uploaded them to my Github account. All lists are sorted lexicographically; get the files here:

• 4 bits
• 5 bits
• 6 bits
• 7 bits
• 8 bits
• 9 bits
• 10 bits
• 11 bits
• 12 bits
• 13 bits
• 14 bits
• 15 bits
• 16 bits
• 17 bits
• 18 bits
• 19 bits
• 20 bits
• 21 bits
• 22 bits

Conversion was done using a straightforward translation (to Perl) of the apgcode encoder logic from apgsearch. I haven't double-checked the lists to make sure they are correct, but didn't spot any errors in the 13-, 14- or 15-bitters.

[wwei23]

The following code computes the number of still lifes with a given number of cells in a given Life-like cellular automaton. All the still lifes found will be outputted to a user-defined text file. This script was used to get the still life counts on the 2x2 and maze pages of LifeWiki.

Some notes about the script:
- It does a brute force search, and thus finds all strict still lifes
- The way in which it filters out pseudo still lifes is based on the definition that if it can be split up into two stable subpatterns, then it is pseudo. I realize that there are pseudos that it may miss (see this page for some discussion), but I can't see that being an issue for still lifes that can realistically be computed using this script.
- It filters out different reflections/rotations of the same still lifes.
- Realistically, it's fast enough to enumerate still lifes up to 9 or maybe 10 cells.

Note: If you use Windows, there is a compiled (ie. executable) version of this program attached at the bottom of this post.

EnumStillLifes.c

Code: Select all

/*
 * EnumStillLifes.c
 * v1.03
 * Calculates the number of still lifes in a Life-like cellular automaton
 * given a rulestring and a number of cells
 * Does a brute-force search, so it is very slow for even moderately large n
 *
 * Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)
 * Created: March 19, 2009
 * Modified: March 28, 2009
 */

#include <math.h>
#include <stdio.h>
#include <string.h>

// If needed, change 10000 to a number larger than the number of still lifes that will be found
unsigned char foundSL[10000][16][16],islandCount=0,numIsl;
unsigned char group1[20][20],group2[20][20];
unsigned char birth23,n,u,uInc,curStep,islArr[16][20][20],been[20][20],tempB[20][20],tempC[20][20],xp[18],yp[18],minX,minY,maxX,maxY;
unsigned int i,j,survive=0,birth=0;
unsigned long int total=0;
char fName[50];
FILE *file;

int max(int mA, int mB)
{
    if(mA >= mB) return mA;
    return mB;
}

int min(int mA, int mB)
{
    if(mA <= mB) return mA;
    return mB;
}

unsigned char numNeighbours(unsigned char x, unsigned char y, unsigned char bArr[20][20]){
    char nI,nJ;
    unsigned char res=0;
    for(nI=x-1;nI<=x+1;++nI){
        for(nJ=y-1;nJ<=y+1;++nJ){
            res+=bArr[nI][nJ];
        }
    }
    return res;
}

void getMinMax()
{
    unsigned char mI;
    minX = u+2;
    minY = u+2;
    maxX = 2;
    maxY = 2;

    for (mI=1;mI<=n;mI++){
        minY=min(yp[mI],minY);
        minX=min(xp[mI],minX);
        maxY=max(yp[mI],maxY);
        maxX=max(xp[mI],maxX);
    }
}

void printSL(unsigned char pArr[20][20])
{
    unsigned char pI,pJ,pK;

    printf("Still lifes found so far: %d\n",total+1);
    file = fopen(fName,"a+");
    for(pI=2;pI<=maxY+1;++pI){
        for(pJ=2;pJ<=maxX;++pJ){
            if(pArr[pJ][pI]==1){
                fprintf(file,"*");
            }else{
                fprintf(file," ");
            }
        }
        fprintf(file,"\n");
    }
    fprintf(file,"\n");
    fclose(file);
}

unsigned char checkPreviousSL(unsigned char bArr[20][20])
{
    unsigned char cI,cJ;
    unsigned int cK;
    unsigned char match;
    for(cI=2;cI<=34;++cI){
        for(cJ=2;cJ<=34;++cJ){
            foundSL[total][cI-2][cJ-2] = bArr[cI][cJ];
        }
    }

    for(cK=0;cK<total;++cK){
        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][maxX-cI][maxY-cJ]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][cI-2][maxY-cJ]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][maxX-cI][cJ-2]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][maxY-cJ][maxX-cI]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][cJ-2][maxX-cI]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][maxY-cJ][cI-2]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}

        match=1;
        for(cI=2;cI<=maxX;++cI){
            for(cJ=2;cJ<=maxY;++cJ){
                if(foundSL[cK][cJ-2][cI-2]!=bArr[cI][cJ]){
                    cJ=maxY;
                    cI=maxX;
                    match=0;
                }
            }
        }
        if(match==1){return 0;}
    }

    return 1;
}

unsigned char isStillLife(unsigned char beenArr[20][20], unsigned char forceY)
{
    char sI,sJ,sRes;

    getMinMax();
    if(minY>forceY){
        return 0;
    }

    for(sI=1;sI<=u+2;sI++){
        for(sJ=1;sJ<=u+2;sJ++){
            if(beenArr[sI][sJ]==1){
                if((survive & (1 << (numNeighbours(sI,sJ,beenArr)-1))) == 0){
                    return 0;
                }
            }else if((birth & (1 << numNeighbours(sI,sJ,beenArr))) > 0){
                return 0;
            }
        }
    }

    if(forceY==2){
        sRes = checkPreviousSL(beenArr);
    }else{
        sRes = 1;
    }
    return sRes;
}

void fillOutIsland(unsigned char xC, unsigned char yC)
{
    unsigned char fI, fJ;
    for(fI=xC-1;fI<=xC+1;++fI){
        for(fJ=yC-1;fJ<=yC+1;++fJ){
            if((been[fI][fJ]==1)&(tempB[fI][fJ]==0)){
                tempB[fI][fJ]=1;
                tempC[fI][fJ]=1;
                islArr[numIsl][fI][fJ]=1;
                islandCount++;
                fillOutIsland(fI,fJ);
            }
        }
    }
}

void resetIslArr()
{
    unsigned char iaI;
    for(iaI=0;iaI<=15;++iaI){
        for(i=0;i<=19;i++){
            for(j=0;j<=19;j++){
                islArr[iaI][i][j]=0;
            }
        }
    }
}

void resetTempB()
{
    for(i=0;i<=19;i++){
        for(j=0;j<=19;j++){
            tempB[i][j]=0;
        }
    }
}

void resetTempC()
{
    for(i=0;i<=19;i++){
        for(j=0;j<=19;j++){
            tempC[i][j]=0;
        }
    }
}

void clearGroups()
{
    for(i=0;i<=19;i++){
        for(j=0;j<=19;j++){
            group1[i][j]=0;
            group2[i][j]=0;
        }
    }
}

unsigned char findIsland()
{
    unsigned char iI,start;
    for(iI=1;iI<=n;++iI){
        if(tempC[xp[iI]][yp[iI]] == 0){
            start=iI;
            break;
        }
    }
    resetTempB();
    tempB[xp[start]][yp[start]]=1;
    tempC[xp[start]][yp[start]]=1;
    islArr[numIsl][xp[start]][yp[start]]=1;
    islandCount++;

    fillOutIsland(xp[start],yp[start]);

    return (1-isStillLife(tempB,u+1));
}

unsigned char firstCellsCheck(unsigned char fPos){
    return (birth & (1 << (been[2][fPos]+been[2][fPos-1]+been[2][fPos-2])));
}

unsigned char firstRowCheck(){
    unsigned char fI;
    unsigned long int tNum=0,rNum=0;
    for(fI=0;fI<u;++fI){
        rNum += ((long)been[2][fI+2] << ((u-1)-fI));
        tNum += ((long)been[2][fI+2] << fI);
    }
    return (rNum >= tNum);
}

void combGroup(unsigned char groupArr[20][20], unsigned char islTArr[20][20]){
    for(i=0;i<=19;i++){
        for(j=0;j<=19;j++){
            groupArr[i][j]=max(groupArr[i][j],islTArr[i][j]);;
        }
    }
}

unsigned char checkPseudo(){
    unsigned int psI,psJ,psLim;
    psLim = (1 << numIsl);
    for(psI=psLim/2;psI<psLim-1;++psI){
        clearGroups();
            for(psJ=0;psJ<numIsl;++psJ){
                if(psI & (1 << psJ)){
                    combGroup(group1,islArr[psJ]);
                }else{
                    combGroup(group2,islArr[psJ]);
                }
            }
            if(isStillLife(group1,u+1)&&isStillLife(group2,u+1)){return 0;}
    }
    return 1;
}

void getNextStep(char curM)
{
    unsigned char m,cx,cy,isSL;
    unsigned char lim = min(u*u - (u-curStep), curM + 2*(u+2));
    if(curM==-1)lim=ceil(n/3.0001)-1;
    m=curM+1;

    if(!(birth23&&m<u&&firstCellsCheck(m))&&!(m==u&&(firstRowCheck()==0))){
        curStep++;
        while(m<=lim)
        {
            cx=floor(m/u)+2;
            cy=(m%u)+2;
            xp[curStep]=cx;
            yp[curStep]=cy;
            been[cx][cy]=1;
            if(curStep==n){
                islandCount=0;
                isSL = isStillLife(been,2);
                if(isSL==1){
                    numIsl=0;
                    isSL=0;
                    resetTempC();
                    resetIslArr();
                    while(islandCount<n){
                        isSL=max(findIsland(),isSL);
                        numIsl++;
                    }
                    if(numIsl==1){
                        isSL=1;
                    }else{
               if(isSL==1){
                   isSL=checkPseudo();
                }

                    }
                }
                if(isSL==1){
                    printSL(been);
                }
                total+=isSL;
            }else{
                getNextStep(m);
            }
            been[cx][cy]=0;
            if(m==curM+u+2){m+=uInc;}
            else{m++;}
        }
        curStep--;
    }
}

void setVariables()
{
    for(i=0;i<=19;i++){
        for(j=0;j<=19;j++){
            been[i][j]=0;
            tempC[i][j]=0;
        }
    }
    curStep=0;
    total=0;
}

int main()
{
    unsigned char foundSlash = 0;
    char rs[19];

    setVariables();

    printf("This tool will calculate the number of still lifes in a Life-like cellular automaton.\nPlease enter the rulestring in S/B format (eg. 23/3 for Conway's Game of Life): ");
    scanf("%s",&rs);
    for(i=0;i<strlen(rs);i++){
        if(foundSlash==0){
            if(rs[i]=='/'){
                foundSlash = 1;
            }else{
                survive += (1 << (rs[i]-16));
            }
        }else{
            birth += (1 << (rs[i]-16));
        }
    }

    if(birth & 1){
        printf("There are no still lifes in any rule with \"0\" in the birth list.");
    }else if(birth & 2){
        printf("There are no still lifes in any rule with \"1\" in the birth list.");
    }else if(!(survive & 1)&&!(survive & 2)&&!(survive & 4)&&!(survive & 8)&&!(survive & 16)){
        printf("There are no still lifes in this rule because all cells with 4 or fewer neighbours die.");
    }else{
        birth23=((birth & 4)||(birth & 8));
        printf("Enter the number of cells (1 <= n <= 16): ");
        scanf("%d",&n);

        u = n;
        if(!(survive & 2)){    // if "1" is not in the survival list
            u = min(max(n - 2, min(n, 4)), u);
        }
        uInc = max(u-4,1);

        printf("Please enter an output file name (eg. \"output.txt\"): ");
        scanf("%s",&fName);

        getNextStep(-1);

        file = fopen(fName,"a+");
        fprintf(file,"Number of %d-cell still lifes in \"%s\": %d\n",n,rs,total);
        fclose(file);
        printf("Total number of %d-cell still lifes in \"%s\": %d",n,rs,total);
    }
    return 0;
}

Unless you're doing B3/S2, in which case there are NO still lives from 9 to 19 cells.

[gameoflifemaniac]

Can someone upload all the still lifes up to 22 (or more) bits in RLE format, just like Apple Bottom did?

[mniemiec]

Can someone upload all the still lifes up to 22 (or more) bits in RLE format, just like Apple Bottom did?

Why do you need them in RLE format? apgcode (or similar encoding) is much more compact, and also easier to parse, for huge lists of patterns. On my web site I have lists up to 18 bits, in multiple pages, at 1000 still-lifes per page, in both PNG and RLE formats, but they're not terribly useful in that form.

[gameoflifemaniac]

Can someone upload all the still lifes up to 22 (or more) bits in RLE format, just like Apple Bottom did?

Why do you need them in RLE format? apgcode (or similar encoding) is much more compact, and also easier to parse, for huge lists of patterns. On my web site I have lists up to 18 bits, in multiple pages, at 1000 still-lifes per page, in both PNG and RLE formats, but they're not terribly useful in that form.

But it's not updated. Now there are 6 more 24-bit still lifes.
And I need the RLE, because I'm making a new folder in Golly called 'Still lifes by bits'.

[mniemiec]

But it's not updated. Now there are 6 more 24-bit still lifes.
And I need the RLE, because I'm making a new folder in Golly called 'Still lifes by bits'.

True, the number of 24-bit still-lifes was wrong, but that isn't relevant, as I didn't actually list the ones above 18 bits (because there were too many). To put it in perspective: my RLE files for the 18-bit still-lifes are around 1/2 MB, while my own internal list (similar in size to apgcode) is around 1/3 MB, so it's more compact than RLE. For 22 bits, it 15MB, and for 24 bits it's 104MB. The RLEs would be considerably larger.

I understand that you want to create Golly files for those lists, but why do you want to do so? RLE files so large that they can be seen from space may provide a brief "wow" moment, but aren't really practical. The files would be so huge that they would be impossible to meaningfully view by hand, and scanning them mechanically by any kind of program would likely be done much easier by looking at individual still-lifes from an apgcode list (or similar). Similarly, even a human lookup of a particular object (e.g. 24.123456) would be done much more easily by picking one line out of a text file and then displaying it, than by going into Golly and moving the cursor tens of thousands of cells to home in one particular still-life in a 2000x2000 table of them. Also, distributing such huge files with Golly would also be impractical.

[Apple Bottom]

Can someone upload all the still lifes up to 22 (or more) bits in RLE format, just like Apple Bottom did?

Writing a script to generate RLEs from the apgcode lists should be straightforward. Take a look at e.g. the inofficial Catagolue browser extension; the relevant code is in catagoluereloaded.js, function apgcodeToPattern for converting an apgcode to an internal representation, and function patternToRLE for encoding that in RLE form. If you're working in Python/Golly, you'll not even need the latter.

If you want to put all n strict still lifes of population c into one big file, simply create an empty universe of size (ceil(sqrt(n)) * (c + 2))^2 or so, and put each individual still life into a (c + 2)^2 square before encoding the whole shebang. As Mark Niemiec remarked, you'll end up with a huge RLE file that way, but if that's what you want, go for it.