Enumerating Still Lifes (in C)

For scripts to aid with computation or simulation in cellular automata.
simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 3rd, 2017, 7:23 pm

chris_c wrote: My python script was too slow so I wrote something in C instead:
Thanks! I added a counter to verify that all patterns get tested, and I've tested that it reacts with Fail on a pattern such as:

Code: Select all

x = 12, y = 10, rule = LifeHistory
9.2A$2.2A.2A.A2.A$2.2A.A3.2A$5.A$2.3A$2.A$2A$A$2.A$.2A!
Apple Bottom wrote:Simeks, does your program's design allow for dividing up the task of enumerating still lives of a given population?
Yes, good idea, it should be pretty straight-forward to do this!

EDIT:
I wrote:The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3.
I was able to improve speed by a factor of 3.6, and on a slighly faster computer, with a 4.4 GHz Haswell core, the running time for the 24 bit still lifes is down to 52 minutes.

EDIT 2:
Result for 26 bit still lifes:
Strict still lifes: 24619307
Pseudo still lifes: 20463274

EDIT 3:
A note on the implementation of my still life searcher:

Reading Mark Niemiec's description of his search program in the Deficiencies section, it appears subtle bugs were starting to show up around 24 or 25 bits in his implementation. Appearently this is caused by restricting placement of new on-cells at a (2,0) or (2,1) distance from the closest previous on-cell to a few carefully selected special cases.

In my program I don't grow patterns from a corner, but instead from this start, where the white cell must be on and the red cells are open to define:

Code: Select all

x = 20, y = 40, rule = LifeHistory
D.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D$D.D.D.D.D.D.D.D.D.D$.D.D.D.D
.D.D.D.D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$
17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$C16D.D$.15D.D
.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.
16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$2.D.D.D.D.D.D.D.D.D$.D
.D.D.D.D.D.D.D.D.D$2.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D!
Any (finite, non-empty) pattern, if rotating/mirroring is not allowed, can be placed in exactly one way in that area, which should guarantee that any subpattern will be generated exactly once, for example like this:

Code: Select all

x = 244, y = 40, rule = LifeHistory
D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D
.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.
D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.
D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D
.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.
D.D$D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D
13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.
D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D13.D.D.
D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D
.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.
D.D.D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D
.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.
D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.
17D.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D
.D.D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D
13.17D.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.
16D.D.D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D
.D13.17D.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D
12.16D.D.D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.
17D.D13.17D.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D
.D12.16D.D.D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D
13.17D.D13.17D.D$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.
16D.D.D12.16D.D.D12.16D.D.D$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.
17D.D13.17D.D13.17D.D$16D.D.D12.2D2C12D.D.D12.16D.D.D12.3DC12D.D.D12.
2D2C12D.D.D12.16D.D.D12.2D2C12D.D.D12.16D.D.D$17D.D13.3DC13D.D13.17D.
D13.D3C13D.D13.2DC14D.D13.17D.D13.2DC14D.D13.17D.D$16D.D.D12.3C13D.D.
D12.2C14D.D.D12.C15D.D.D12.CDC13D.D.D12.C15D.D.D12.CDC13D.D.D12.2C14D
.D.D$2C15D.D13.C16D.D13.CDC14D.D13.2C15D.D13.2C15D.D13.3C14D.D13.2C
15D.D13.C16D.D$.C14D.D.D13.15D.D.D13.DC13D.D.D13.15D.D.D13.15D.D.D13.
2DC12D.D.D13.15D.D.D13.3C12D.D.D$.CDC13D.D14.16D.D14.D2C13D.D14.16D.D
14.16D.D14.D2C13D.D14.16D.D14.2DC13D.D$.D2C12D.D.D13.15D.D.D13.15D.D.
D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D$.16D.D14.16D.D14.
16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D$.15D.D.D13.15D.D.D13.
15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D$.16D.D14.
16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D$.15D.D.D13.15D.
D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D$.16D.
D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D$.15D.D.D13.
15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D$.
16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D$.15D.D.
D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D
.D$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D$.
15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D
13.15D.D.D$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.
16D.D$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.
15D.D.D13.15D.D.D$2.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D
.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D
15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D13.D.D.D
.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.
D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D
.D.D.D.D$2.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D
15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.
D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.
D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D
.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D!
As far as I can think of I don't make any dangerous assumptions about where new on-cells can be placed. For example the program will happily build and continue to search from an intermediate pattern like this:

Code: Select all

x = 20, y = 40, rule = LifeHistory
D.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D$D.D.D.D.D.D.D.D.D.D$.D.D.D.D
.D.D.D.D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$
D4.12D.D$5.11D.D.D$2.2C.12D.D$3.C.11D.D.D$3C2.12D.D$C4.11D.D.D$4.13D.
D$C4.11D.D.D$3C2.12D.D$3.C.11D.D.D$2.2C.12D.D$5.11D.D.D$5.12D.D$.15D.
D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.
16D.D$.15D.D.D$2.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D$2.D.D.D.D.D.D
.D.D.D$.D.D.D.D.D.D.D.D.D.D!
because it could possibly be completed to a still life for example like this:

Code: Select all

x = 20, y = 40, rule = LifeHistory
D.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D$D.D.D.D.D.D.D.D.D.D$.D.D.D.D
.D.D.D.D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$17D.D$16D.D.D$
D7.9D.D$9.7D.D.D$2.2C.2C3.7D.D$3.C.C5.5D.D.D$3C3.3C3.5D.D$C7.C4.3D.D.
D$8.C.C2.4D.D$C5.2C.2C2.3D.D.D$3C4.C5.4D.D$3.C.C.C4.4D.D.D$2.2C.2C3.
7D.D$9.7D.D.D$8.9D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$.16D.D$
.15D.D.D$.16D.D$.15D.D.D$.16D.D$.15D.D.D$2.D.D.D.D.D.D.D.D.D$.D.D.D.D
.D.D.D.D.D.D$2.D.D.D.D.D.D.D.D.D$.D.D.D.D.D.D.D.D.D.D!
Instead it seems I am able to reach about the same asymptotic speed of O(2.6^n) as Mark Niemiec by a careful selection of the search order.

EDIT 4:
Result for 27 bit still lifes:
Strict still lifes: 60823008
Pseudo still lifes: 52816265

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 7th, 2017, 4:18 pm

I've posted a test release of the still life searcher here

Note: I've also edited my previous post multiple times.

Should work well on Windows and Linux. Try the Windows version if you can, it has a nice visualization window!

Windows executables are included, run from a DOS window. Use sc256 if you have a Haswell or later CPU or sc128 if not.

For Linux, compile with "mknative".

Usage is:

> sc128 <command> <min on cells> <max on cells> [<selected subset>]
where <command> is "w" to write database files, or "c" to only count still lifes.

Pick a suitable <max on cells>. You can generate databases for lower bit counts in the same run in virtually no extra time, for example:

> sc128 w 4 22

will generate 38 different files in the current directory, one for each bit count, and one each for strict and pseudo still lifes.

The program will keep an eye open for any triple or quad pseudo still life, and report them to stdout (the console) if any are found. The smallest known of these types has 32 on-cells, but there could possibly be smaller ones.

To redirect stdout to a file, use for example:

> sc128 w 4 22 >out.txt

On the suggestion of Apple Bottom, I've implemented the possibility to search a subset of the search space.

There is currently a fixed set of 100 subsets that require about an equal amount of time to complete. They are numbered from 0 to 99, for example:

> sc128 w 31 32 91 >out.txt

will generate database files such as "32_bits_strict_subset_0091_of_0100.txt". The running time for searching one subset to 32 bits should be around a day. You can of course start one search for each CPU core of your computer in different subsets at the same time.

Note that it is normal for subset number 2 to contain no strict still lifes, only pseudo still lifes, so the corresponding database file will be empty.

If someone wants to set up a community search up to a larger bit count than 32 bits, I can post a version with a higher number of subsets.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 7th, 2017, 5:53 pm

simeks wrote:I've posted a test release of the still life searcher here.
Wonderful! I just gave it a test -- using one HT core on a Core i7-3770K (supporting AVX but not AVX2), it took roundabout 15 minutes to compute everything up to 22 bits. That's quite impressive. And I like the visualization window, that's a nice touch.

Output's a bit jumbled, for some reason:

Code: Select all

$ time ./sc128.exe w 4 22 |tee 4-22.txt

Cells open to define and the (4, 64) cell that should always be on:

x = 64, y = 128, rule = LifeHistory
4$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.
56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D
$4.subset = -1, min = 4
Not stable = 721221908, not canonical = 14977582, not connected = 193287

Number of on-cells:          4
Result for full search space:
Strict still lifes:          2
Pseudo still lifes:          0

Number of on-cells:  56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.
56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D
$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.56D$4.
56D$4.56D$4.56D$4.A55D$5.55D$5.55D$5.55D$5.        5
Result for full search space:
Strict still lifes:          1
Pseudo still lifes:          0

Number of on-cells:          6
Result for full search space:
Strict still lifes:          5
Pseudo still lifes:          0

Number of55D on-cells:          7
Result for full search space:
Strict still lifes:          4
Pseudo still lifes:          0

Number of on-cells:          8
Result for full search space:
Strict still lifes:          9
Pseudo still lifes:          1
$5.55D$5.55D$5.55D$5.55D
$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.
55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D
$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.
55D$5.55D$5.5
Number of on-cells:          9
Result for full search space:
Strict still lifes:         10
Pseudo still lifes:          1

Number of on-cells:         10
Result for full search space:
Strict still lifes:         25
Pseudo still lifes:  5D$5        7

Number of on-cells:    .55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D$5.55D
$5.55D$5.55D$5.55D$5.55D$5.55D!

0 strict and 0 pseudo 22 bit still lifes so far
8803 strict and 55225 pseudo 22 bit still lifes so far
26293 strict and 71539 pseudo 22 bit still lifes so far
58462 strict and 84332 pseudo 22 bit still lifes so far
83739 strict and 95972 pseudo 22 bit still lifes so far
99646 strict and 104337 pseudo 22 bit still lifes so far
141339 strict and 128106 pseudo 22 bit still lifes so far
178444 strict and 147869 pseudo 22 bit still lifes so far
205486 strict and 162157 pseudo 22 bit still lifes so far
228242 strict and 189946 pseudo 22 bit still lifes so far
258997 strict and 203380 pseudo 22 bit still lifes so far
284963 strict and 219239 pseudo 22 bit still lifes so far
314910 strict and 230573 pseudo 22 bit still lifes so far
359333 strict and 256623 pseudo 22 bit still lifes so far
391732 strict and 277920 pseudo 22 bit still lifes so far
403313 strict and 283035 pseudo 22 bit still lifes so far
433782 strict and 306333 pseudo 22 bit still lifes so far
456357 strict and 323082 pseudo 22 bit still lifes so far
472798 strict and 332153 pseudo 22 bit still lifes so far
497364 strict and 340995 pseudo 22 bit still lifes so far
526043 strict and 353865 pseudo 22 bit still lifes so far
559205 strict and 371219 pseudo 22 bit still lifes so far
576999 strict and 392941 pseudo 22 bit still lifes so far
591081 strict and 421296 pseudo 22 bit still lifes so far
615536 strict and 434655 pseudo 22 bit still lifes so far
636781 strict and 442280 pseudo 22 bit still lifes so far
657355 strict and 450477 pseudo 22 bit still lifes so far

Performence timer report:
Timer ticks/s: 3435937
Elapsed time:  933495.279 ms
     11
Result for full search space:
Strict still lifes:         46
Pseudo still lifes:         16

Number of on-cells:         12
Result for full search space:
Strict still lifes:        121
Pseudo still lifes:         55

Number of on-cells:         13
Result for full search space:
Strict still lifes:        240
Pseudo still lifes:        110

Number of on-cells:         14
Result for full search space:
Strict still lifes:        619
Pseudo still lifes:        279

Number of on-cells:         15
Result for full search space:
Strict still lifes:       1353
Pseudo still lifes:        620

Number of on-cells:         16
Result for full search space:
Strict still lifes:       3286
Pseudo still lifes:       1645

Number of on-cells:         17
Result for full search space:
Strict still lifes:       7773
Pseudo still lifes:       4067

Number of on-cells:         18
Result for full search space:
Strict still lifes:      19044
Pseudo still lifes:      10843

Number of on-cells:         19
Result for full search space:
Strict still lifes:      45759
Pseudo still lifes:      27250

Number of on-cells:         20
Result for full search space:
Strict still lifes:     112243
Pseudo still lifes:      70637

Number of on-cells:         21
Result for full search space:
Strict still lifes:     273188
Pseudo still lifes:     179011

Number of on-cells:         22
Result for full search space:
Strict still lifes:     672172
Pseudo still lifes:     462086

real    15m33.527s
user    0m0.000s
sys     0m0.046s
$ 
On the suggestion of Apple Bottom, I've implemented the possibility to search a subset of the search space.
That's very good as well! I see you've already computed the databases up to 27 bits -- I presume you're working on 28? Shall we divide up the work for the 29-bitters?

I'd propose that to do that we simply grab the next available subset(s), post a note in this thread saying what we've taken (to avoid duplicate work), and then start the computation. Post the results in this thread when the computation's done, and once the 29-bitters are done, we can move on to the 30-bitters, and so on.

I'll start by doing subset 0 of the 29-bitters!
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 7th, 2017, 6:27 pm

Apple Bottom wrote:That's quite impressive. And I like the visualization window, that's a nice touch.
Thanks! I actually wrote the visualization for debugging of another project I'm working on, so I just threw it in... ;)
Apple Bottom wrote:Output's a bit jumbled, for some reason:
I looks like output to stderr and output to stdout has somehow been intermixed. What if you only redirect stdout to a file (>out.txt) and let stderr go to the console?
Apple Bottom wrote:That's very good as well! I see you've already computed the databases up to 27 bits -- I presume you're working on 28? Shall we divide up the work for the 29-bitters?
Actually i started up an Amazon Ec2 server to generate the database for 25 to 30 bits. This was with an earlier version that had 16 subsets instead of 100. I'm running subset 0-3 of those 16 in parallel and they will complete soon. Luckily they correspond exactly to subset 0-24 of the new division.

I'm also running a count of the full 28 bits search that will complete soon, but without the database.
Would you like to start at subset 25 for bit count 25 to 30? Each one should take a bit over 5 hours at the speed you quoted.

In that case I'll continue at subset 50 when the current searches are done.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 7th, 2017, 6:36 pm

simeks wrote:I looks like output to stderr and output to stdout has somehow been intermixed. What if you only redirect stdout to a file (>out.txt) and let stderr go to the console?
tee(1) should only touch stdout, but sure, I'll try that and see if it makes any difference.
Apple Bottom wrote:Actually i started up an Amazon Ec2 server to generate the database for 25 to 30 bits. This was with an earlier version that had 16 subsets instead of 100. I'm running subset 0-3 of those 16 in parallel and they will complete soon. Luckily they correspond exactly to subset 0-24 of the new division.

I'm also running a count of the full 28 bits search that will complete soon, but without the database.
Would you like to start at subset 25 for bit count 25 to 30? Each one should take a bit over 5 hours at the speed you quoted.

In that case I'll continue at subset 50 when the current searches are done.
Sure, that works! Bit count 25 to 30, subset 25; I'll also run subset 26 right afterwards (otherwise the core this is running on will be partially idle overnight).
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 7th, 2017, 9:42 pm

New result:

Number of on-cells: 28
Strict still lifes: 150613157
Pseudo still lifes: 136655095

mniemiec
Posts: 1590
Joined: June 1st, 2013, 12:00 am

Re: Enumerating Still Lifes (in C)

Post by mniemiec » January 8th, 2017, 12:46 am

simeks wrote:So far I have confirmed the numbers reported by Mark Niemiec for bit counts from 4 to 23. However for 24 bits my program finds 6 more scrict still lifes and 1 more pseudo still life than previously reported. My numbers are 4051732 and 3069135 respectively.
I'm fairly confident of the counts up to 23 bits, but not so much about the 24 bit ones. My algorithm has known defects (i.e. there are certain classes of objects it won't find), and I had to add those manually. The lists of extra objects is very small at 23 bits, but larger at 24, and would be over a hundred at 25 (which is one reason I had never attempted those). A couple of years ago, I made a change to the algorithm to explicitly look for the specific class of objects that were missed, and it did indeed find them (and no others), but that change caused it to lose one pseudo-object that had been previously found (a pond surrounded by four blocks). This means there is still some subtle bug in the algorithm, and I wouldn't feel comfortable running any larger searches until I figure out why that is happening.
simeks wrote:There is no database of 24 bit still lifes from Mark Niemiec's search, or anyone who has access to the code used for it? It would be interesting to find out if the extra still lifes I've found have any special propertly...
Definitely! Do you have any way of uploading your results in any format? Years ago, I had a similar discrepancy with H. Koenig on his searches, and by comparing the lists, I was able to find out which objects I found that he didn't, and also a few extra ones that he found that I didn't - which all turned out to be pseudo-objects that were erroneously classified as objects.
[quote="simeks"Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?[/quote]
I have a tool that takes a pattern list, and splits it into four separate output buckets - objects, pseudo-objects, quasi-objects (i.e. two adjacent tubs), and non-objects (e.g. constellations). I use this to post-process my own searches, as those output objects and pseudo-objects together. Ideally, the last two categories are always empty, unless something is seriously wrong.
simeks wrote:I'm currently running the search for 25 bit still lifes, I will report the result soon. EDIT: The result I get is 9971377 strict still lifes and 7906676 pseudo still lifes.
Nice! As a sanity check, the number of 25-bit still-lifes are 2.46 times the number of 24s, which is exactly the ratio I would expect.
simeks wrote:The database will be two textfiles of this format: ...
This looks like RLE without the header, which should be very easy to parse and/or convert.
simeks wrote:The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3. The asymptotic speed is around O(2.6^n), the same as reported by Mark Niemiec.
This is much better than mine. The last recorded times I had for my earlier runs were 47 hours for the 21-bit ones, which would be 32 days for the 24-bit ones. I think my last runs were faster, but not nearly that fast.
simeks wrote:I'm sure the program can be adapted for other rules, but there are some assumptions about the properties of B3/S23 that will need some consideration.
Mine assumes that all birth and survival conditions occur in contiguous bands (i.e. deaths can occur from under-population or over-population, but not from an intermediate population, e.g. S35).
Apple Bottom wrote:actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable.
While this will eventually become an issue, the smallest known pseudo-object like this occurs at 32 bits, so it's not an issue now. My own pseudo-still-life filter currently treats these as real objects.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 8th, 2017, 6:50 am

simeks wrote:New result:

Number of on-cells: 28
Strict still lifes: 150613157
Pseudo still lifes: 136655095
And my first result, for subset 25 of the 25- to 30-bitters:

Code: Select all

subset = 25, min = 25
Not stable = 15872702118, not canonical = 219570234, not connected = 5250928

Number of on-cells:         25
Result for subset 25 in (0..99) of search space:
Strict still lifes:     135206
Pseudo still lifes:      86047

Number of on-cells:         26
Result for subset 25 in (0..99) of search space:
Strict still lifes:     332167
Pseudo still lifes:     223376

Number of on-cells:         27
Result for subset 25 in (0..99) of search space:
Strict still lifes:     815550
Pseudo still lifes:     574713

Number of on-cells:         28
Result for subset 25 in (0..99) of search space:
Strict still lifes:    2012827
Pseudo still lifes:    1490689

Number of on-cells:         29
Result for subset 25 in (0..99) of search space:
Strict still lifes:    4954954
Pseudo still lifes:    3857401

Number of on-cells:         30
Result for subset 25 in (0..99) of search space:
Strict still lifes:   12233916
Pseudo still lifes:   10020879
The search took about 6:25 hours, nicely fitting in with Simeks's above estimate:

Code: Select all

Performence timer report:
Timer ticks/s: 3435937
Elapsed time: 23116485.969 ms
The resulting files total about 2.55 GiB (144.4 MiB compressed). Which again leaves me wondering, where's the best place to upload/store these results?

Also, if noone else has claimed them yet, I'll do subsets 27-29 next.

EDIT: subset 26 has finished:

Code: Select all

subset = 26, min = 25
Not stable = 16291049904, not canonical = 222037575, not connected = 4251140

Number of on-cells:         25
Result for subset 26 in (0..99) of search space:
Strict still lifes:     105034
Pseudo still lifes:      66443

Number of on-cells:         26
Result for subset 26 in (0..99) of search space:
Strict still lifes:     258685
Pseudo still lifes:     171261

Number of on-cells:         27
Result for subset 26 in (0..99) of search space:
Strict still lifes:     638157
Pseudo still lifes:     444129

Number of on-cells:         28
Result for subset 26 in (0..99) of search space:
Strict still lifes:    1581116
Pseudo still lifes:    1151166

Number of on-cells:         29
Result for subset 26 in (0..99) of search space:
Strict still lifes:    3926574
Pseudo still lifes:    2989489

Number of on-cells:         30
Result for subset 26 in (0..99) of search space:
Strict still lifes:    9761305
Pseudo still lifes:    7777677
The search took a bit longer, roundabout 7 hours, but the resulting files are smaller, 2.06 GiB uncompressed. I've already created an account on GitHub to upload the results to. (This'll take a while, however, I don't have a very fast connection.)
Last edited by Apple Bottom on January 8th, 2017, 8:17 am, edited 1 time in total.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Enumerating Still Lifes (in C)

Post by calcyman » January 8th, 2017, 8:04 am

I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 8th, 2017, 8:25 am

calcyman wrote:I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.
And I've updated the counts on the wiki.

Calcyman, could you also submit an update for A056613 (pseudo-still life counts)?
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 8th, 2017, 10:37 am

mniemiec wrote:
simeks wrote:There is no database of 24 bit still lifes from Mark Niemiec's search, or anyone who has access to the code used for it? It would be interesting to find out if the extra still lifes I've found have any special propertly...
Definitely! Do you have any way of uploading your results in any format?
I had the database for 24 bits uploaded temporarily, but I deleted it because the files were a bit too large for GitHub where I placed it.

I can upload it again to a more suitable place, but not until tomorrow when I have a decent internet connection again.

However, since I posted my program to GitHub yesterday, the simplest way would be if you downloaded it from here, compiled it for Linux, or ran the precompiled Windows executable with this command:

> sc128 w 24 24

and you will have the two 24 bit database files generated to the current directory in an hour or two.
mniemiec wrote:
simeks wrote:Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?
I have a tool that takes a pattern list, and splits it into four separate output buckets - objects, pseudo-objects, quasi-objects (i.e. two adjacent tubs), and non-objects (e.g. constellations). I use this to post-process my own searches, as those output objects and pseudo-objects together. Ideally, the last two categories are always empty, unless something is seriously wrong.
chris_c wrote a tool to verify that all objects in the database are either strict och pseudo still lifes, but without being able to tell those two categories apart. If you can use your tool to verify this, that would be good!

I have also since then written a verification tool with mostly independent code, to verify that all objects in the 24-bit database are unique.
It would still be nice if someone could verify independently that all objects in the 24-bit database are stable and without duplicates. A nice way to do this would be if you were able to compare my database to your 24-bit database and we could figure out by which objects they differ.
mniemiec wrote:This looks like RLE without the header
Yes, I removed the header to keep the size of the databases down, the output would normally look like this:

Code: Select all

x = 8, y = 5, rule = LifeHistory
6.A$5.A.A$2A3.2A$A2.2A$.2A.A!
mniemiec wrote:
Apple Bottom wrote:actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable.
While this will eventually become an issue, the smallest known pseudo-object like this occurs at 32 bits, so it's not an issue now. My own pseudo-still-life filter currently treats these as real objects.
My search program correctly detects triple/quad pseudo still lifes as pseudo still lifes, and because they are interesting, the program outputs any pseudo still life it finds that can't be partitioned in just two parts, to the console. I've verified that this works by running the small part of the search space for 32 bits that contains the smallest known such pattern. So far Apple Bottom and I have covered 31% of the search space for 30-bit still lifes without finding any smaller triple/quad pseudo still life.
Apple Bottom wrote:The resulting files total about 2.55 GiB (144.4 MiB compressed). Which again leaves me wondering, where's the best place to upload/store these results?
I don't really know... A free Google Drive account can hold 15 GB, but maybe there are better options? Does anyone else know of a good solution?
Apple Bottom wrote:Also, if noone else has claimed them yet, I'll do subsets 27-29 next.
I'll consider subsets 25-49 reserved by you until further notice.
I've completed subsets 0-24 and 50-53. 54-56 are running now.
Apple Bottom wrote:I've already created an account on GitHub to upload the results to. (This'll take a while, however, I don't have a very fast connection.)
A read about GitHub and it seems there's a limit of only 100 MB data for each account. EDIT: Actually, that seems to be the file size limit, but I still don't think GitHub will be suitable.
calcyman wrote:I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.
Thanks!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 8th, 2017, 12:12 pm

simeks wrote:
Apple Bottom wrote:Also, if noone else has claimed them yet, I'll do subsets 27-29 next.
I'll consider subsets 25-49 reserved by you until further notice.
I've completed subsets 0-24 and 50-53. 54-56 are running now.

[...]
A read about GitHub and it seems there's a limit of only 100 MB data for each account. EDIT: Actually, that seems to be the file size limit, but I still don't think GitHub will be suitable.
OK, I'll consider subsets 25-49 "mine" for now then.

Github does indeed have a 100 MiB file size limit, as I found out much to my chagrin (and only AFTER trying to upload a larger file). However, for 30-bitters, the individual compressed files are well below the limits, so I'm using Github for now anyway. The data files for subsets 25 and 26 are all available here.

In the long run, I still think archive.org is our best bet: able (and willing) to host large amounts of data, dedicated to keeping it permanently accessible to both researchers and lay users, and operating as a non-profit, without competing business interests.

EDIT: subset 27 is done:

Code: Select all

subset = 27, min = 25
Not stable = 14882234241, not canonical = 257337784, not connected = 2331392

Number of on-cells:         25
Result for subset 27 in (0..99) of search space:
Strict still lifes:      48777
Pseudo still lifes:      20951

Number of on-cells:         26
Result for subset 27 in (0..99) of search space:
Strict still lifes:     126280
Pseudo still lifes:      57586

Number of on-cells:         27
Result for subset 27 in (0..99) of search space:
Strict still lifes:     324210
Pseudo still lifes:     156643

Number of on-cells:         28
Result for subset 27 in (0..99) of search space:
Strict still lifes:     833059
Pseudo still lifes:     426780

Number of on-cells:         29
Result for subset 27 in (0..99) of search space:
Strict still lifes:    2132660
Pseudo still lifes:    1155711

Number of on-cells:         30
Result for subset 27 in (0..99) of search space:
Strict still lifes:    5461868
Pseudo still lifes:    3132629
The database files are up on Github.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

mniemiec
Posts: 1590
Joined: June 1st, 2013, 12:00 am

Re: Enumerating Still Lifes (in C)

Post by mniemiec » January 8th, 2017, 7:43 pm

I just wrote a converter to convert the RLE format into the LIS format that my own still life enumerator uses, and compared my lists with those generated by s128.exe. (LIS format is a bit more compact; the output files are about 1/3 of the size of the RLE files). The lists are identical, which verifies that not only are the numbers the same, but the acutal generated objects are the same as well (this was highly probable, but not 100% certain until verified).

There is one particular kind of expansion that my program did not handle: expanding a single bit into a new island beginning with a line of 5 adjacent bits. (I had later added a specific fix for this one case, but that fix made one pseudo-still-life disappear, so I didn't consider the change to be robust until I tracked down the source of the error). Without that fix, there were two kinds of objects that would not be found automatically. These were of the form a<-b->c and a->b<-c, where "->" means a line of 5 that requires a 1-bit stabilization, and where b cannot occur at an external corner.

Of the former type, there are 1 22-bit, 5 23-bit, 26 24-bit, and hundreds of 25-bit ones (which is why I never attempted the 25s, until this could be dealt with automatically). Of the latter type, there are 20 24-bit ones.

Your new lists include 6 new still-lifes that were missing from my list. Curiously, all six were in my list of 20 a->b<-c ones to be manually added, dating back to 2011-02-20, but were colored differently than the others (perhaps because I had not yet instantiated them? I am not sure). I had always known that the process of adding the extra still-lifes was error-prone; adding 1 22-bit still-life and 5 23-bit still-lifes manually didn't seem to be a problem, but apparently 46 24-bit ones was.

The one additional pseudo-still-life is one that should have been found, and I have no idea why it would have been missed. It indicates that there is still some kind of subtle bug in my search program.

One good thing that comes from all of this is that, with one single exception that can't be explained, both algorithms produce the same results, and there are no old objects that the new algorithm has missed.

Code: Select all

x = 101, y = 9, rule = B3/S23
oo13boo13boo13boobobbo8boo13boo13boo$obbo5boo4bobbo5boo4bobbo5boo4bob
5o8bo14bo14bo9bo$bboobbobbo7boobbobbo7boobbobbo21bo5boo8bo5boo7boboobb
3o$3bobobobo8bobobobo8bobobobo9bo10boobbobbo8boobbobbo7boobobbo$3bobbo
bboo7bobbobboo7bobbobboo7bobo10bobobobo9bobobobo12booboo$bboo5bobbo4b
oo5bo7boo5bo9bo11bobbobboo8bobbobboo12boboo$11boo12bo15bo18boo5bo8boo
5bo13bo$24boo14boo5b5obo15bo15bo10boo$47bobboboo14boo14boo!
EDIT:
simeks wrote:In my program I don't grow patterns from a corner, but instead from this start, where the white cell must be on and the red cells are open to define:
When I use the word "corner" in my still-life enumerator, this is what I mean - the leftmost cell on the top row (equivalent to the bottommost cell on the leftmost row in your illustration - rotated 90 degrees from my model).

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 9th, 2017, 10:31 am

Subsets 28 and 29 are done:

Code: Select all

subset = 28, min = 25
Not stable = 14979308409, not canonical = 237449271, not connected = 4399162

Number of on-cells:         25
Result for subset 28 in (0..99) of search space:
Strict still lifes:      83406
Pseudo still lifes:     112513

Number of on-cells:         26
Result for subset 28 in (0..99) of search space:
Strict still lifes:     203316
Pseudo still lifes:     288291

Number of on-cells:         27
Result for subset 28 in (0..99) of search space:
Strict still lifes:     493719
Pseudo still lifes:     733470

Number of on-cells:         28
Result for subset 28 in (0..99) of search space:
Strict still lifes:    1207706
Pseudo still lifes:    1880765

Number of on-cells:         29
Result for subset 28 in (0..99) of search space:
Strict still lifes:    2954346
Pseudo still lifes:    4805353

Number of on-cells:         30
Result for subset 28 in (0..99) of search space:
Strict still lifes:    7253577
Pseudo still lifes:   12314462

Code: Select all

subset = 29, min = 25
Not stable = 15348642958, not canonical = 224121702, not connected = 5925915

Number of on-cells:         25
Result for subset 29 in (0..99) of search space:
Strict still lifes:     199757
Pseudo still lifes:      69639

Number of on-cells:         26
Result for subset 29 in (0..99) of search space:
Strict still lifes:     487139
Pseudo still lifes:     184103

Number of on-cells:         27
Result for subset 29 in (0..99) of search space:
Strict still lifes:    1188491
Pseudo still lifes:     486392

Number of on-cells:         28
Result for subset 29 in (0..99) of search space:
Strict still lifes:    2914720
Pseudo still lifes:    1284669

Number of on-cells:         29
Result for subset 29 in (0..99) of search space:
Strict still lifes:    7142996
Pseudo still lifes:    3375082

Number of on-cells:         30
Result for subset 29 in (0..99) of search space:
Strict still lifes:   17548957
Pseudo still lifes:    8867024
Data files are on Github again (or will be soon).

EDIT: subset 30 is done:

Code: Select all

subset = 30, min = 25
Not stable = 14755232644, not canonical = 217867764, not connected = 4240169

Number of on-cells:         25
Result for subset 30 in (0..99) of search space:
Strict still lifes:     103411
Pseudo still lifes:      79819

Number of on-cells:         26
Result for subset 30 in (0..99) of search space:
Strict still lifes:     251235
Pseudo still lifes:     206816

Number of on-cells:         27
Result for subset 30 in (0..99) of search space:
Strict still lifes:     609531
Pseudo still lifes:     529905

Number of on-cells:         28
Result for subset 30 in (0..99) of search space:
Strict still lifes:    1489214
Pseudo still lifes:    1365701

Number of on-cells:         29
Result for subset 30 in (0..99) of search space:
Strict still lifes:    3636068
Pseudo still lifes:    3502094

Number of on-cells:         30
Result for subset 30 in (0..99) of search space:
Strict still lifes:    8934298
Pseudo still lifes:    9008027
Last edited by Apple Bottom on January 9th, 2017, 4:04 pm, edited 1 time in total.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 9th, 2017, 12:20 pm

mniemiec wrote:I just wrote a converter to convert the RLE format into the LIS format that my own still life enumerator uses, and compared my lists with those generated by s128.exe. (LIS format is a bit more compact; the output files are about 1/3 of the size of the RLE files). The lists are identical, which verifies that not only are the numbers the same, but the acutal generated objects are the same as well (this was highly probable, but not 100% certain until verified).
Thanks for doing that! I think it makes a pretty strong case for assuming we've found all 24 bit still lifes now.
mniemiec wrote:The one additional pseudo-still-life is one that should have been found, and I have no idea why it would have been missed. It indicates that there is still some kind of subtle bug in my search program.
I don't know how you feel about sharing source code, but I would find it interesting to take a look.
mniemiec wrote:When I use the word "corner" in my still-life enumerator, this is what I mean - the leftmost cell on the top row (equivalent to the bottommost cell on the leftmost row in your illustration - rotated 90 degrees from my model).
Ok, I misinterpreted your description of it at codercontest.com

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 10th, 2017, 6:18 am

Subsets 31 and 32 are done:

Code: Select all

subset = 31, min = 25
Not stable = 15476376904, not canonical = 235503141, not connected = 5335848

Number of on-cells:         25
Result for subset 31 in (0..99) of search space:
Strict still lifes:      45514
Pseudo still lifes:     204512

Number of on-cells:         26
Result for subset 31 in (0..99) of search space:
Strict still lifes:     113090
Pseudo still lifes:     518854

Number of on-cells:         27
Result for subset 31 in (0..99) of search space:
Strict still lifes:     278318
Pseudo still lifes:    1297059

Number of on-cells:         28
Result for subset 31 in (0..99) of search space:
Strict still lifes:     691597
Pseudo still lifes:    3283975

Number of on-cells:         29
Result for subset 31 in (0..99) of search space:
Strict still lifes:    1704229
Pseudo still lifes:    8256309

Number of on-cells:         30
Result for subset 31 in (0..99) of search space:
Strict still lifes:    4223567
Pseudo still lifes:   20916560

Code: Select all

subset = 32, min = 25
Not stable = 15147671097, not canonical = 251164650, not connected = 4583256

Number of on-cells:         25
Result for subset 32 in (0..99) of search space:
Strict still lifes:     107428
Pseudo still lifes:     116785

Number of on-cells:         26
Result for subset 32 in (0..99) of search space:
Strict still lifes:     267093
Pseudo still lifes:     299577

Number of on-cells:         27
Result for subset 32 in (0..99) of search space:
Strict still lifes:     665269
Pseudo still lifes:     757010

Number of on-cells:         28
Result for subset 32 in (0..99) of search space:
Strict still lifes:    1659748
Pseudo still lifes:    1939297

Number of on-cells:         29
Result for subset 32 in (0..99) of search space:
Strict still lifes:    4136943
Pseudo still lifes:    4946348

Number of on-cells:         30
Result for subset 32 in (0..99) of search space:
Strict still lifes:   10316211
Pseudo still lifes:   12687719
EDIT:

Subset 33 is done:

Code: Select all

subset = 33, min = 25
Not stable = 15580327151, not canonical = 273108705, not connected = 3490538

Number of on-cells:         25
Result for subset 33 in (0..99) of search space:
Strict still lifes:      96701
Pseudo still lifes:      41898

Number of on-cells:         26
Result for subset 33 in (0..99) of search space:
Strict still lifes:     243844
Pseudo still lifes:     113763

Number of on-cells:         27
Result for subset 33 in (0..99) of search space:
Strict still lifes:     615501
Pseudo still lifes:     309894

Number of on-cells:         28
Result for subset 33 in (0..99) of search space:
Strict still lifes:    1549588
Pseudo still lifes:     833594

Number of on-cells:         29
Result for subset 33 in (0..99) of search space:
Strict still lifes:    3907337
Pseudo still lifes:    2247558

Number of on-cells:         30
Result for subset 33 in (0..99) of search space:
Strict still lifes:    9827256
Pseudo still lifes:    6012514
EDIT 2:

Subset 34:

Code: Select all

subset = 34, min = 25
Not stable = 12696432706, not canonical = 250716684, not connected = 1882949

Number of on-cells:         25
Result for subset 34 in (0..99) of search space:
Strict still lifes:      53264
Pseudo still lifes:      19909

Number of on-cells:         26
Result for subset 34 in (0..99) of search space:
Strict still lifes:     132072
Pseudo still lifes:      56093

Number of on-cells:         27
Result for subset 34 in (0..99) of search space:
Strict still lifes:     328591
Pseudo still lifes:     153695

Number of on-cells:         28
Result for subset 34 in (0..99) of search space:
Strict still lifes:     816717
Pseudo still lifes:     419791

Number of on-cells:         29
Result for subset 34 in (0..99) of search space:
Strict still lifes:    2037290
Pseudo still lifes:    1138699

Number of on-cells:         30
Result for subset 34 in (0..99) of search space:
Strict still lifes:    5093087
Pseudo still lifes:    3080753
EDIT 3: subsets 35 and 36:

Code: Select all

subset = 35, min = 25
Not stable = 13449974033, not canonical = 224407969, not connected = 4677979

Number of on-cells:         25
Result for subset 35 in (0..99) of search space:
Strict still lifes:     150902
Pseudo still lifes:      83695

Number of on-cells:         26
Result for subset 35 in (0..99) of search space:
Strict still lifes:     369955
Pseudo still lifes:     218836

Number of on-cells:         27
Result for subset 35 in (0..99) of search space:
Strict still lifes:     905379
Pseudo still lifes:     563656

Number of on-cells:         28
Result for subset 35 in (0..99) of search space:
Strict still lifes:    2220689
Pseudo still lifes:    1464846

Number of on-cells:         29
Result for subset 35 in (0..99) of search space:
Strict still lifes:    5449979
Pseudo still lifes:    3780671

Number of on-cells:         30
Result for subset 35 in (0..99) of search space:
Strict still lifes:   13397827
Pseudo still lifes:    9815235

Code: Select all

subset = 36, min = 25
Not stable = 15526926210, not canonical = 258542785, not connected = 5287097

Number of on-cells:         25
Result for subset 36 in (0..99) of search space:
Strict still lifes:     159142
Pseudo still lifes:      99062

Number of on-cells:         26
Result for subset 36 in (0..99) of search space:
Strict still lifes:     390281
Pseudo still lifes:     252951

Number of on-cells:         27
Result for subset 36 in (0..99) of search space:
Strict still lifes:     955540
Pseudo still lifes:     648751

Number of on-cells:         28
Result for subset 36 in (0..99) of search space:
Strict still lifes:    2347691
Pseudo still lifes:    1667496

Number of on-cells:         29
Result for subset 36 in (0..99) of search space:
Strict still lifes:    5764604
Pseudo still lifes:    4294379

Number of on-cells:         30
Result for subset 36 in (0..99) of search space:
Strict still lifes:   14186295
Pseudo still lifes:   11081870
EDIT 4: subsets 37 and 38:

Code: Select all

subset = 37, min = 25
Not stable = 16005838413, not canonical = 261576264, not connected = 5588534

Number of on-cells:         25
Result for subset 37 in (0..99) of search space:
Strict still lifes:     141549
Pseudo still lifes:     116218

Number of on-cells:         26
Result for subset 37 in (0..99) of search space:
Strict still lifes:     345965
Pseudo still lifes:     295399

Number of on-cells:         27
Result for subset 37 in (0..99) of search space:
Strict still lifes:     848611
Pseudo still lifes:     764187

Number of on-cells:         28
Result for subset 37 in (0..99) of search space:
Strict still lifes:    2087586
Pseudo still lifes:    1958030

Number of on-cells:         29
Result for subset 37 in (0..99) of search space:
Strict still lifes:    5153712
Pseudo still lifes:    5054253

Number of on-cells:         30
Result for subset 37 in (0..99) of search space:
Strict still lifes:   12709729
Pseudo still lifes:   12983493

Code: Select all

subset = 38, min = 25
Not stable = 14670887962, not canonical = 277761653, not connected = 3363721

Number of on-cells:         25
Result for subset 38 in (0..99) of search space:
Strict still lifes:      90779
Pseudo still lifes:      47252

Number of on-cells:         26
Result for subset 38 in (0..99) of search space:
Strict still lifes:     229629
Pseudo still lifes:     125725

Number of on-cells:         27
Result for subset 38 in (0..99) of search space:
Strict still lifes:     578853
Pseudo still lifes:     335652

Number of on-cells:         28
Result for subset 38 in (0..99) of search space:
Strict still lifes:    1451681
Pseudo still lifes:     887829

Number of on-cells:         29
Result for subset 38 in (0..99) of search space:
Strict still lifes:    3637245
Pseudo still lifes:    2361652

Number of on-cells:         30
Result for subset 38 in (0..99) of search space:
Strict still lifes:    9128205
Pseudo still lifes:    6253320
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 12th, 2017, 11:41 am

Apple Bottom wrote:EDIT 4: subsets 37 and 38:
I've been running 4 hypertreads of this in the cloud, and now I've completed subsets 50-99 and also 45-49. I'm starting subsets 41-44 now, should be done in about 7 hours.

I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.

I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23. What I would need is a function like:

int evolve_cell (int tile [3] [3], const char *rule_string)

that takes a 3-by-3 grid and a rule string, and returns the correct next cell state for the center cell.
It doesn't have to be fast, because it will only be used to build tables while initializing, and any programming language is fine!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 12th, 2017, 12:03 pm

simeks wrote:I've been running 4 hypertreads of this in the cloud, and now I've completed subsets 50-99 and also 45-49. I'm starting subsets 41-44 now, should be done in about 7 hours.
Nice, that works out really well. I'm done with subset 39, and subset 40 is running right as I'm writing this and should be done in a few hours, so if you are doing/have done all of 0 to 24 and 41 to 99, we should be complete.
I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.
That would be excellent. And if I understand the next bit correctly, "any rule" includes non-/semi-totalistic rules? Even better.
I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23. What I would need is a function like:

int evolve_cell (int tile [3] [3], const char *rule_string)

that takes a 3-by-3 grid and a rule string, and returns the correct next cell state for the center cell.
It doesn't have to be fast, because it will only be used to build tables while initializing, and any programming language is fine!
Hmm, my first instinct there is to treat the neighborhood as a bitstring of length 8 (i.e. a number from 0..255) and look up whether or not the center cell should be alive or dead in the next generation in an array. (No need to "canonicalize" the orientation, either, each subcondition will simply correspond to multiple array elements.)

The array would be hardcoded, so this should be no slower than doing the same for totalistic rules, either. (Famous last words!)

EDIT: Oh yeah, completely forgot, here's the results for subset 39:

Code: Select all

subset = 39, min = 25
Not stable = 15671906842, not canonical = 279200823, not connected = 4027698

Number of on-cells:         25
Result for subset 39 in (0..99) of search space:
Strict still lifes:     105606
Pseudo still lifes:      82365

Number of on-cells:         26
Result for subset 39 in (0..99) of search space:
Strict still lifes:     256837
Pseudo still lifes:     212237

Number of on-cells:         27
Result for subset 39 in (0..99) of search space:
Strict still lifes:     630209
Pseudo still lifes:     553134

Number of on-cells:         28
Result for subset 39 in (0..99) of search space:
Strict still lifes:    1544956
Pseudo still lifes:    1423014

Number of on-cells:         29
Result for subset 39 in (0..99) of search space:
Strict still lifes:    3795608
Pseudo still lifes:    3692340

Number of on-cells:         30
Result for subset 39 in (0..99) of search space:
Strict still lifes:    9342118
Pseudo still lifes:    9534378
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Enumerating Still Lifes (in C)

Post by calcyman » January 12th, 2017, 12:45 pm

simeks wrote:I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23.
The following 512-character string encodes complete information about the notation:

Code: Select all

                String lord = "";
                lord += "_ceaccaieaeaknja_ceaccaieaeaknjaekejanaairerririekejanaairerriri";
                lord += "ccknncqnaijaqnwaccknncqnaijaqnwakykkqyqjrtjnzrqakykkqyqjrtjnzrqa";
                lord += "ekirkyrtejerkkjnekirkyrtejerkkjnekejjkrnejecjyccekejjkrnejecjycc";
                lord += "anriqyzraariqjqaanriqyzraariqjqajkjywkqkrnccqkncjkjywkqkrnccqknc";
                lord += "cnkqccnnkqkqyykjcnkqccnnkqkqyykjaqjwinaarzjqtrnaaqjwinaarzjqtrna";
                lord += "ccyyccyennkjyekeccyyccyennkjyekenykknejeirykrikenykknejeirykrike";
                lord += "aqrznyirjwjqkkykaqrznyirjwjqkkykaqrqajiarqcnnkccaqrqajiarqcnnkcc";
                lord += "intrneriaanajekeintrneriaanajekeajnkaeaeiaccaec_ajnkaeaeiaccaec_";
For each i in {0, 1, ..., 511}, we have:
  • centre cell = (i >> 4) & 1;
  • neighbour count = popcount(i & 495);
  • shape = lord;


I constructed lord algorithmically from a screenshot of the following webpage:

http://www.ibiblio.org/lifepatterns/neighbors2.html

together with the list of row letters. It seems to be correct, since it's in the Catagolue source code for displaying animated SVGs (and no-one has complained about the SVGs).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 12th, 2017, 4:25 pm

And finally, here's the results for subset 40:

Code: Select all

subset = 40, min = 25
Not stable = 15119821223, not canonical = 261321633, not connected = 3524319

Number of on-cells:         25
Result for subset 40 in (0..99) of search space:
Strict still lifes:      85111
Pseudo still lifes:      64568

Number of on-cells:         26
Result for subset 40 in (0..99) of search space:
Strict still lifes:     214399
Pseudo still lifes:     173013

Number of on-cells:         27
Result for subset 40 in (0..99) of search space:
Strict still lifes:     533731
Pseudo still lifes:     453357

Number of on-cells:         28
Result for subset 40 in (0..99) of search space:
Strict still lifes:    1337707
Pseudo still lifes:    1200731

Number of on-cells:         29
Result for subset 40 in (0..99) of search space:
Strict still lifes:    3332824
Pseudo still lifes:    3131438

Number of on-cells:         30
Result for subset 40 in (0..99) of search space:
Strict still lifes:    8341582
Pseudo still lifes:    8215526
The data files are uploading to my Github repo right now. And I believe that with this, we're finally done!
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 14th, 2017, 10:50 pm

Apple Bottom wrote:And finally, here's the results for subset 40:
...
The data files are uploading to my Github repo right now. And I believe that with this, we're finally done!
Thanks for helping out!

I've summed up all the output files. Fortunately the sums for 25 to 28 bits match those I've previously reported. Sums for 29 and 30 bits are new:

Code: Select all

Bits	 Strict		Psuedo

25	  9971377	  7906676
26	 24619307	 20463274
27	 60823008	 52816265
28	150613157	136655095
29	373188952	353198379
30	926068847	914075620
I've made a copy of all databases uploaded to your GitHub account, and I'll consider how to bundle them up into suitable files for the final database.

Also, there has been no sign of any triple or quad pseudo still life, so it seems the smallest such still life has at least 31 bits (the smallest known has 32 bits).

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Enumerating Still Lifes (in C)

Post by calcyman » January 14th, 2017, 11:15 pm

simeks wrote:I've summed up all the output files.
Excellent work! I've updated both the pages in the OEIS to include terms up to 30 (as usual, it may take a day or so for these changes to be approved).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Apple Bottom » January 15th, 2017, 6:45 am

simeks wrote:Thanks for helping out!

I've summed up all the output files. Fortunately the sums for 25 to 28 bits match those I've previously reported. Sums for 29 and 30 bits are new:

I've made a copy of all databases uploaded to your GitHub account, and I'll consider how to bundle them up into suitable files for the final database.

Also, there has been no sign of any triple or quad pseudo still life, so it seems the smallest such still life has at least 31 bits (the smallest known has 32 bits).
You're welcome, pardner! :) *tips hat* Glad to have been able to contribute.

I'll keep the Github repo around for when we inevitably decide to tackle the 31- and 32-bitters (I'd suggest increasing the number of subsets then, however, to e.g. 1000 for the 32-bitters, to offset the increase in both file size and computation time).

I've also updated the relevant pages on the LifeWiki.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Enumerating Still Lifes (in C)

Post by simeks » January 15th, 2017, 1:26 pm

Apple Bottom wrote:
simeks wrote:I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.
That would be excellent. And if I understand the next bit correctly, "any rule" includes non-/semi-totalistic rules? Even better.
Yes, and I guess even for anisotropic rules, but that will require changes to the is_canonical function too.

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?
calcyman wrote:The following 512-character string encodes complete information about the notation:
...
Thanks, that will be helpful!
calcyman wrote:Excellent work! I've updated both the pages in the OEIS to include terms up to 30 (as usual, it may take a day or so for these changes to be approved).
Thanks!
Apple Bottom wrote:I'll keep the Github repo around for when we inevitably decide to tackle the 31- and 32-bitters (I'd suggest increasing the number of subsets then, however, to e.g. 1000 for the 32-bitters, to offset the increase in both file size and computation time).
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.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Still Lifes (in C)

Post by dvgrn » January 15th, 2017, 3:26 pm

simeks wrote: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?
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?

Post Reply