CA with weighted neighbourhoods (discussion of algorithms)

[confocaloid]

The purpose of this thread is to discuss algorithms and mathematics that are useful to define/explore/understand cellular automata using weighted neighbourhoods.

Overview

Golly and LifeViewer support defining cellular automata using weighted neighbourhoods ("NW..."): https://golly.sourceforge.io/Help/Algor ... l#weighted
Instead of simply counting alive neighbours, here every neighbour gets an integer weight. (Currently, every weight must be less than 128, to be able to run the CA in Golly/LifeViewer.)
To compute the condition of a cell, weights of all alive neighbours of the cell are added together.
Let s be the sum of weights of alive neighbours of a cell. Let c be the current state of that cell. Then the condition of that cell can be communicated by giving/telling/writing down the ordered pair (c; s).
Then the birth/survival conditions listed in the rulestring are given in the same sense (as conditions needed for a cell to be alive in the next generation).

An example

Here is a two-state isotropic CA using a range-2 weighted neighbourhood:

Code: Select all

x = 24, y = 5, rule = R2,C0,S2-3,172-252,B3,245-253,NW01090109010951515109015100510109515151090109010901
21bo2$bo21bo$2bo$3o16bobobo!
#C [[ GRID THEME MCell ]]

In this case, the weights are as follows; there are three distinct nonzero weights (1, 9, 81); the assignment of weights is completely symmetric. In general, it can be asymmetric.

Code: Select all

01 09 01 09 01
09 81 81 81 09
01 81 -- 81 01
09 81 81 81 09
01 09 01 09 01

Previous discussion

Crossposting/linking some of previous relevant discussion:

[...] How did you find it?

Basically, by spending some time trying to understand which CA can be defined using weighted neighbourhoods, and by writing a bunch of scripts in unreleasable state to brute-force answers to several questions.

I think range 3 is roughly as far as one can get by brute-forcing possibilities. Beyond that, there are way too many different neighbourhood partitions (even restricting to only fully-symmetric partitions, like those I used above) to generate and test them all directly. One would need a faster algorithm.

Golly currently supports only weights smaller than 128, which implies that a Golly-compatible fully-symmetric weighted neighbourhood on the square tiling can have at most four distinct positive weights. (For example 1, 5, 25, 125 with each of these weights assigned to four different neighbours.) For range 3, that means investigating partitions of the set

Code: Select all

{ (0,0), (1,0), (1,1), (2,0), (2,1), (2,2), (3,0), (3,1), (3,2), (3,3) }

into 2, 3, 4 or 5 subsets; one of these subsets gets weight 0 (i.e. not considered a neighbour at all) and each of the other subsets gets its own positive weight. (For simplicity, a cell is not considered its own neighbour, so the subset containing (0,0) is the one that gets weight 0.)

The above is only a simplification that assumes weights are chosen and assigned in an appropriate way to allow distinguishing all conditions that can be distinguished in principle (with a given partition). The reality is more complicated than that, because there are weighted neighbourhoods such as NW121202121 or NW212101212 which distinguish fewer conditions than the corresponding "canonical forms" NW151505151 or NW515101515. The advantage of non-canonical weighted neighbourhoods is that they can be supported in Golly/LifeViewer (they have sufficiently small weights) even if the corresponding "canonical form" would require too large weights and is not supported in Golly/LifeViewer.

For range 4 or higher there would be way too many partitions into 2, 3, 4 or 5 subsets to test them explicitly, so some additional algorithmic trickery will be necessary.

[...] My wish was to explore INT R3 Cross, but since LifeViewer does not support CAViewer or Durnak-Cole, this is the closest I can go. [...]

It's possible to go a bit closer to isotropic range-3 cross, using an "atlas" of multiple overlapping rulespaces, with each "chart" in the "atlas" defined by a weighted neighbourhood like this:

Code: Select all

00 00 00 01 00 00 00
00 00 00 0F 00 00 00
00 00 00 2D 00 00 00
01 05 2D 00 2D 05 01
00 00 00 2D 00 00 00
00 00 00 0F 00 00 00
00 00 00 01 00 00 00

The range-1 neighbours and the range-3 neighbours are treated as before. The four range-2 neighbours are split into two pairs, allowing to distinguish the situation "two alive range-2 neighbours opposite each other" from the situation "two non-opposite alive range-2 neighbours". One needs to be careful to choose living conditions so that the resulting CA is isotropic (for example if B58 is included then B78 also should be). Otherwise it seems to work: [...]

That "distinguishing trick" could be performed for any one of three ranges, and would work in Golly/LifeViewer.
I think it's also possible to do that for two ranges at once. However, one would need to use the highest weight on the remaining range where all four neighbours have the same weight.
It appears to be impossible to perform the "distinguishing trick" on all three ranges at once. That would require some cells to be weighted 243. [...]

[...] Related:
CWCFSMNCA https://web.archive.org/web/20150422212 ... words.html
A discussion of CA definition formats https://web.archive.org/web/19990224055 ... /0007.html

Moore-neighbourhood, E^2 lattice:
There is a nontrivial set of cellular automata rules between isotropic nontotalistic and outer-totalistic set, where only the number of diagonal and orthogonal neigbours count. Using Hensel-notation, only the following rulestring parts are valid in a birth or survival section:

• 0 diagonal, 0 orthogonal: 0
• 1 d., 0 o.: 1c
• 0 d., 1 o.: 1e
• 2 d., 0 o.: 2cn
• 1 d., 1 o.: 2ak
• 0 d., 2 o.: 2ei
• 3 d., 0 o.: 3c
• 2 d., 1 o.: 3inqy
• 1 d., 2 o.: 3akjr
• 0 d., 3 o.: 3e
• ...

and so on.
Is it worth to list already investigated nontotalistic rules if they fit into the above category?

Other links

• viewtopic.php?f=11&t=6736 "666 rules" (hexagonal tiling, range 2, three distinct weights 1, 7, 49)
• viewtopic.php?f=11&t=936 "Non-totalistic Rules - notations, projects, & discussion"
• viewtopic.php?f=11&t=477 "Rule Tables + Weighted Life + Larger than Life"

[confocaloid]

[...] I think range 3 is roughly as far as one can get by brute-forcing possibilities. Beyond that, there are way too many different neighbourhood partitions (even restricting to only fully-symmetric partitions, like those I used above) to generate and test them all directly. One would need a faster algorithm. [...]
[...] For range 4 or higher there would be way too many partitions into 2, 3, 4 or 5 subsets to test them explicitly, so some additional algorithmic trickery will be necessary.

The "naive" algorithm is basically as follows. It works for ranges up to 3, and can take up to 10-20 minutes to complete and likely can be significantly improved. I think it will not complete in reasonable time for range 4 in those cases when there is no solution but that cannot be determined immediately without considering specific partitions.

• The input consists of:
  • a pattern p (the starting generation of the object/reaction to be preserved),
  • a two-state isotropic cellular automaton from which the object/reaction to be preserved was taken,
  • a nonnegative integer n (the number of ticks to be preserved starting from p),
  • a positive integer r (the weighted neighbourhood range to be used).
  Choosing n = 1 means preserving just the first tick from generation 0 to generation 1.
• Collect all rules that are used in the first n ticks of evolution of p. To do that, scan the first n ticks of evolution of the pattern p. For every pair of consecutive generations (p[t]; p[t+1]), scan all nonempty (2r+1)-by-(2r+1) configurations in p[t]. For every such configuration, read from the correct coordinates in p[t+1] the future state of the middle cell. This gives the set of rules used in the reaction to be preserved, with rules expressed in the form of ordered pairs:

  Code: Select all

  (current states of a cell and its neighbours; future state of the cell)

  where "current states of a cell and its neighbours" is the condition of the rule.
• Convert the ruleset, by converting the condition of every rule into an ordered tuple of the form

  Code: Select all

  (current state of the cell;
  the number of alive (1,0) neighbours;
  the number of alive (1,1) neighbours;
  the number of alive (2,0) neighbours;
  the number of alive (2,1) neighbours;
  the number of alive (2,2) neighbours;
  the number of alive (3,0) neighbours; ...)

  up to and including the number of alive (r,r) neighbours.
  
  In general, this step reduces the number of rules in the ruleset, because rules with different conditions and the same prescribed future state of the cell can get merged into a single rule.
• Check for contradictions in the ruleset. A contradiction happens when there are two different rules with identical condition. That would mean a cell must become/remain alive sometimes while remaining/becoming dead other times, and that cannot be determined from the information available by "counting alive neighbours in every ring" as described above.
  If there are any contradictions, exit with "failure".
• Iterate over all partitions of the set

  Code: Select all

  { (0,0), (1,0), (1,1), (2,0), (2,1), (2,2), (3,0), ..., (r,r) }

  into two or more subsets (parts). For the square tiling, in a simple implementation ignoring "non-canonical" weighted neighbourhoods, it suffices to consider only partitions with 2, 3, 4 or 5 parts (see previous post).
• For every such partition, check whether the weights can be assigned with every weight less than 128. For every such Golly-compatible assignment of weights, convert the ruleset again, this time by converting the condition of every rule from an ordered tuple of the form described above into an ordered tuple of the form

  Code: Select all

  (current state of the cell; sum of weights of alive neighbours of the cell)

  After that, again check for contradictions in the resulting ruleset.
  • In the event that there are no contradictions (the resulting ruleset is self-consistent), that means the currently considered partition with the currently considered assignment of weights does allow to define a CA where the reaction of interest is preserved. Depending on implementation choices/user preferences, either report the first found solution and exit with "success", or collect all solutions, or look for the "best" solution according to some metric.
  • In the event that there is a contradiction, that means the currently considered partition causes a contradiction. If only "canonical" weighted neighbourhoods are considered, then the contradiction cannot be resolved merely by switching to another "canonical" weighting while keeping the same partition. Hence the algorithm can stop processing this partition, and continue with the next Golly-compatible partition.
• After iterating over all Golly-compatible partitions (up to the range r), report any solutions found and exit. (Depending on implementation choices/user preferences, there may be early exit with "success" when any solution is found.)

This algorithm can be used, for example, to determine that the following p11 orthogonal c/11 spaceship (from a two-state isotropic CA with range-1 neighbourhood) can be preserved using a range-2 fully-symmetric weighted neighbourhood, as shown. You can compare the evolution phase-by-phase and verify that it's the same in both cases, even though the rules determining the evolution are significantly different.

Code: Select all

x = 2, y = 3, rule = B3/S2-n36c
o$2o$o!

Code: Select all

x = 2, y = 3, rule = R2,C0,S28-41,78-94,130,132-149,182,B39-44,92-95,143-146,NW010100010101410D4101000D000D0001410D41010101000101
o$2o$o!

[confocaloid]

Here is an additional example, from a recent request:

A bit different but can someone tame B2n3ai4cr7/S1e2-c3aeir4a by cleaning up the random junk happens in soups and keep the r pentomino spaceship (the rep would be cool too)

Code: Select all

x = 3, y = 12, rule = B2n3ai4cr7/S1e2-c3aeir4a
b2o$2o$bo6$bo$bo$bo$bo!

The algorithm described above can be used to determine that the replicator can be preserved in a cellular automaton defined using a fully-symmetric range-2 weighted neighbourhood:

Code: Select all

x = 1, y = 4, rule = R2,C0,S30-32,55-66,B27,56,84,NW00000500000001190100051900190500011901000000050000
o$o$o$o!

but the spaceship cannot be preserved in any two-state CA defined using a fully-symmetric weighted neighbourhood (of any range).
The spaceship has two "essentially different" phases (up to translations, rotations and reflections). Out of the two marked dead cells, one must become alive and the other must remain dead:

Code: Select all

x = 13, y = 3, rule = B2n3ai4cr7/S1e2-c3aeir4aHistory
D2A7.ADA$2A8.A$.A8.2A!
#C [[ GRID ]]

However, both marked cells are in the same condition, as far as can be computed with the "counting neighbours in every ring" approach:

Code: Select all

(0; 2; 1; 1; 1; 0; 0; 0; 0; 0)
The cell is currently dead
with precisely two alive (1,0) neighbours,
with precisely one alive (1,1) neighbour,
with precisely one alive (2,0) neighbour,
with precisely one alive (2,1) neighbour,
and without any other alive neighbours.

After collecting the rules used in the spaceship's evolution and converting each rule, the resulting ruleset will include the following two rules:

Code: Select all

((0; 2; 1; 1; 1; 0; 0; 0; 0; 0); 0)
((0; 2; 1; 1; 1; 0; 0; 0; 0; 0); 1)

which is a contradiction (two different rules with identical condition), so the above algorithm will exit with "failure".

[...] the assignment of weights is completely symmetric. In general, it can be asymmetric. [...]

Continuing with the same example: the spaceship can be preserved in an isotropic cellular automaton using a weighted neighbourhood that isn't fully-symmetric, for example:

Code: Select all

x = 25, y = 25, rule = R1,C0,S5-7,11,15-17,20,31,B7,17,21,NW0105010F000F010501
5bobo$5bo$5b2o3$22b3o$22bo$24bo10$o$2bo$3o3$18b2o$19bo$17bobo!

Allowing such partitions in the algorithm would further increase the number of possibilities to be tested, though.

[confocaloid]

[...] The "naive" algorithm is basically as follows. [...]

• [...]
• Check for contradictions in the ruleset. A contradiction happens when there are two different rules with identical condition. That would mean a cell must become/remain alive sometimes while remaining/becoming dead other times, and that cannot be determined from the information available by "counting alive neighbours in every ring" as described above.
  If there are any contradictions, exit with "failure".
• [...]

I'm currently trying the algorithm semi-manually for concrete examples (collecting the examples along the way).

Below is a (known) period-124 mod-62 diagonal c/124 glider rake in B3-c/S23-ceky. Can someone else double-check that it's impossible to preserve this evolutionary sequence in any two-state cellular automaton that uses a fully-symmetric weighted neighbourhood (even for higher ranges, regardless of the range)?

Two-state RLE:

Code: Select all

x = 8, y = 6, rule = B3-c/S23-ceky
5b2o$3b2o2bo$3bo2b2o$2o2b2o$ob2o$b2o!
#C [[ GRID ZOOM 8 ]]

[R]History version of the same pattern (see OCA:LifeHistory):

Code: Select all

x = 12, y = 10, rule = B3-c/S23-cekyHistory
10.D$11.D3$5.2A$3.2A2.A$3.C2.2A$2A2.CA$A.2A$.2A!
#C [[ GRID ZOOM 8 ]]

As far as I can tell, the obstacle is in the two marked alive cells (which happen to be in the same generation) and their future states.
In the next tick, one of those two cells will survive and the other will die.
The less obvious part is that those two cells appear to be in the same condition, as far as can be computed with the "counting alive neighbours in every ring" approach. For example each of those two cells has precisely three alive "knight's move" neighbours.

The situation repeats 62 ticks later with two marked dead cells (which become alive).

[confocaloid]

[...] I'm currently trying the algorithm semi-manually for concrete examples (collecting the examples along the way). [...]

Golly's help gives the example 'R3,C2,M0,S24..31,B24..28,NG' for what it calls "Gaussian neighbourhood". Running a few soups in Golly quickly leads to a rediscovery of the following p8 orthogonal 5c/4 spaceship:

Code: Select all

x = 3, y = 8, rule = R3,C2,M0,S24..31,B24..28,NG
o$bo2$2bo4$o!
#C [[ THEME MCell GRID ZOOM 12 ]]

I believe the following is an equivalent definition using an explicitly weighted neighbourhood:

Code: Select all

#C optional birth conditions (192): 37, 47, 49, 51-52, 55-56, 58, 64, 68-72, 74-75, 77-83, 85, 87-88, 90-93, 95-256
#C optional survival conditions (228): 0-15, 17-18, 20-21, 23, 25-26, 29-30, 35-49, 51, 53-57, 59, 61, 63-65, 68-69, 72-74, 82-87, 90-91, 93-256
x = 3, y = 8, rule = R3,C0,S24-31,B24-28,NW01020304030201020406080604020306090C09060304080C100C08040306090C0906030204060806040201020304030201
o$bo2$2bo4$o!
#C [[ THEME MCell GRID ZOOM 12 ]]

01 02 03 04 03 02 01
02 04 06 08 06 04 02
03 06 09 12 09 06 03
04 08 12 16 12 08 04
03 06 09 12 09 06 03
02 04 06 08 06 04 02
01 02 03 04 03 02 01

In this case, the neighbour weights are "non-canonical" in the sense that there is no one-to-one correspondence between possible sums of weights and possible ordered tuples "counting alive neighbours in every ring". For example, the sum of weights of alive neighbours would be equal to 3 in either of the following cases:

• precisely one alive (3,1) neighbour (the sum of weights is 3),
• precisely one alive (3,2) neighbour and precisely one alive (3,3) neighbour (the sum of weights is 3 = 2 + 1),
• precisely three alive (3,3) neighbours (the sum of weights is 3 = 1 + 1 + 1).

I tried to find a (Golly-compatible) "canonical" assignment of weights which would allow distinguishing all possible ordered tuples "counting alive neighbours in every ring", while also supporting the spaceship shown above. With range up to and including 3, I did not find any such weighted neighbourhood. I think this illustrates how the ability to use a "non-canonical" assignment of weights may be useful (or even indispensable) in practice.