Notation for 2D, semitotalistic, 9-neighbor Moore cellular automata

Question

I am trying to run the semitotalistic rule B45678/S5678 on a torus, I found a program that runs game of life (B3/S23):

gameOfLife = {224, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}};

board = RandomInteger[1, {64, 64}];

Dynamic[ArrayPlot[
  board = Last[CellularAutomaton[gameOfLife, board, {{0, 1}}]], 
  ImageSize -> Large]]

(1) I have no idea how the rule notation works.

(2) I don't really need to see it run, what I really need is a "run one iteration" function.

Answer 1

Simulating only a single generation is trivial. Just omit the Dynamic and the tspec.

gameOfLife = {224, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}};

board = RandomInteger[1, {64, 64}];
ArrayPlot@board
ArrayPlot[board = CellularAutomaton[gameOfLife, board]]

The trickier part is understanding the rule specification. There are many forms of these specifications, but I'll focus on the form in your question only, because it's the only one you need to simulate any life-like automaton. There are several parts to it:

{224,  {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}

{rule, {k,              weights             }, range }

Let's ignore rule for now and look at the rest. Those things will be identical for any life-like cellular automaton:

• A range of {x, y} tells Mathematica that we're looking at a 2-dimensional cellular automaton where the next state of any cell depends on a neighbourhood of size $(2x+1, 2y+1)$ centred on the current cell. Specifically for {1, 1} that's just the 3x3 Moore neighbourhood you want for life-like automata.
• k is simply the number of states. In our case that's 2, dead and alive.

• The weights are interesting. A semitotalistic automaton can be expressed as a weighted cellular automaton. That is, the given weights are applied to the neighbourhood, which is then summed up. The next state depends only on that sum. This allows us to look only at a few different cases instead of having to redundantly specify the next state for every possible neighbourhood (many of which will have the same number of living adjacent cells). The simplest and least wasteful way to specify the weights is

  {{2, 2, 2},
   {2, 1, 2},
   {2, 2, 2}}
  

  The weights are chosen such that a dead cell will have an even sum and a living cell will have an odd sum, where the sum minus that parity bit is twice the number of living neighbours. That means all 18 relevant cases (B0 to B8 and S0 to S8) are mapped to sums from 0 to 17. As a side note, the following weight table would also be an option but result in different rule numbers:

  {{1, 1, 1},
   {1, 9, 1},
   {1, 1, 1}}
  

  The former seems to be conventional in Mathematica (if only because it's used in the docs), so I'm going with that for now. See the bottom of the post if you prefer this second weight table.

Finally, there's the rule number, which is the trickiest part. These are essentially a generalisation of Wolfram's rule notation, which is explained on Wikipedia. The documentation has a tutorial on how this generalisation works, but I'll outline the parts that are relevant for life-like automata below.

For a general rule you'd simply list all the states for all possible neighbourhoods and treat that list as the digits of a base-k number.

For a weighted rule, you list the states for all possible (weighted) sums instead.

So let's write out B3/S23 for this notation:

Case        B0  S0  B1  S1  B2  S2  B3  S3  B4  S4  B5  S5  B6  S6  B7  S7  B8  S8
Sum          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
Next state   0   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   0   0

Now there are k = 2 states, so we want to interpret this as a binary number. But note that the smallest sum should correspond to the least significant number, so we'll reverse this digit list:

FromDigits[Reverse@{0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 2]
(* 224 *)

And that's where the rule number comes from. With this, we can now easily encode B5678/S45678 or any other rule:

FromDigits[Reverse@{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 2]
(* 261632 *)

So the full rule specification you're looking for is

gameOfLife = {261632, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}};

Here is a function which converts standard Game of Life notation to Mathematica's rule numbers (input validation taken from J. M.'s improved code below):

gol2mma[spec_] /; 
  StringMatchQ[spec, RegularExpression["B\\d+/S\\d+"]] := 
  FromDigits[
    Flatten[Reverse /@ 
      Transpose[
        Table[Boole@StringContainsQ[#, ToString@i], {i, 8, 0, -1}] & /@ 
          StringSplit[spec, "/"]
      ]
    ], 
    2
  ]

gol2mma["B3/S23"]
(* 224 *)
gol2mma["B5678/S45678"]
(* 261632 *)

---

If you prefer the other weight table (which is maybe a bit more natural coming from the standard life notation, since here the cases are grouped by birth/survival instead of number of live neighbours), the states would be listed like this for standard Game of Life:

Case        B0  B1  B2  B3  B4  B5  B6  B7  B8  S0  S1  S2  S3  S4  S5  S6  S7  S8
Sum          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
Next state   0   0   0   1   0   0   0   0   0   0   0   1   1   0   0   0   0   0

Again, remember to reverse this before interpreting it as a binary number. Here is a corresponding implementation of the rule conversion function (using J. M.'s improved code, including input validation):

gol2mma[spec_String] /; 
  StringMatchQ[spec, RegularExpression["B\\d+/S\\d+"]] := 
  FromDigits[
    Reverse@Flatten[
      StringCases[
        spec, 
        s : DigitCharacter .. :> ReplacePart[
          ConstantArray[0, 9], 
          Thread[FromDigits /@ Characters[s] + 1 -> 1]
        ]
      ]
    ], 
    2
  ]

gol2mma["B3/S23"]
(* 6152 *)
gol2mma["B5678/S45678"]
(* 254432 *)

And indeed, the following rule specification also correctly simulates the standard Game of Life:

gameOfLife = {6152, {2, {{1, 1, 1}, {1, 9, 1}, {1, 1, 1}}}, {1, 1}};