Special case of CellularAutomaton

Question

I’m interested in multi-state CA in a closed 2D space and try to implement them using CellularAutomaton but do not understand how to do it.
The first question is, is it possible to implement a board as closed torus with CellularAutomaton options?

Next, there is a simple scheme: N states(colors), 8 neighbors. The cell changes the state to the most common among neighbours.
If there are several of these with the same weight, then at random one of them is chosen. Can this be realized with CellularAutomaton?

Finally, an additional question for those familiar with the topic. I implemented such process on a pure core language, and see that it always leads to stationary a picture like a political map.

Is such a result already known and can it be proved that the process always ends in a static state?

Answer 1

Is such a result already known and can it be proved that the process always ends in a static state?

For asynchronous updates (where one cell at a time is chosen, deterministically or at random, and the update rule is applied only to that single cell), it's easy to show that any change in a cell's state must strictly decrease the total number of pairs of adjacent cells with different states. Since this total number is monotone decreasing under the application of the rule, and also bounded from below, it follows that it must converge to a minimum where no more changes to any cell states are possible.

However, this simple proof does not carry over into the case of synchronous updates across the whole board. In particular, even with only two cell states, it is possible to have board states that either:

1. oscillate periodically while maintaining a constant total number of mismatched adjacent cells, or
2. where applying the CA rule will increase the number of mismatched adjacent cells.

---

For a simple example of a board state of the first type, consider a periodic board state where cells in odd-numbered columns are all in state A and cells in even-numbered columns are all in state B. On such a board every cell is in a local minority (having two neighbors in the same state and six in the opposite state) and thus changes state on each update step, creating a stable period 2 cycle:

ABABABABAB       BABABABABA
ABABABABAB       BABABABABA
ABABABABAB  <->  BABABABABA
ABABABABAB       BABABABABA
ABABABABAB       BABABABABA

This page on LifeWiki, describing the two-state version of your rule, also includes some examples of periodically oscillating bounded local configurations on a static background.

For an example of a board state of the second type, flip the state of one cell on either of the boards above. This decreases the number of mismatched neighbor pairs by four, but applying the CA rule twice undoes the state flip, thereby increasing the number of mismatched neighbor pairs:

ABABABABAB       BABABABABA       ABABABABAB
ABABABABAB       BABABABABA       ABABABABAB
ABABBBABAB  -->  BABABABABA  <->  ABABABABAB
ABABABABAB       BABABABABA       ABABABABAB
ABABABABAB       BABABABABA       ABABABABAB

---

However, experimenting with the two-state version of the rule (e.g. using WebCA with algorithmic rule number 992, as suggested on this page), does show that it typically converges to a stable fixed point when started from a random initial state. It seems that periodically oscillating configurations, while possible, do not emerge very often from a random initial board state under this rule.

IMO the fact that the asynchronous version of this rule provably converges to a non-oscillatory state at least gives a hint as to why this is. Basically, for rules of this type to end up in an oscillating cycle, several adjacent cells must just by chance end up in a specific configuration where multiple cells changing state synchronously will endlessly frustrate each others' attempts to seek a stable local majority. And that requires some fine tuning that does not often emerge from a random initial board state.

Answer 2

If you read the documentation for CellularAutomaton, you will find the line:

Explicit initial conditions are assumed cyclic.

This works regardless of the dimensionality. For example, here is an automaton moving squares in different directions.

initial = ConstantArray[0, {15, 15}];
initial[[3, 5]] = 1;
initial[[8, 8]] = 2;
initial[[9, 2]] = 3;
initial[[2, 13]] = 4;

ArrayPlot[#, ColorRules -> {1 -> Red, 2 -> Blue, 3 -> Green, 4 -> Yellow}] & /@
 CellularAutomaton[{
  {{_, _, _}, {_, _, _}, {_, _, 1}} :> 1,
  {{_, _, _}, {_, _, _}, {2, _, _}} :> 2,
  {{_, _, _}, {_, _, 3}, {_, _, _}} :> 3,
  {{_, 4, _}, {_, _, _}, {_, _, _}} :> 4,
  {{_, _, _}, {_, _, _}, {_, _, _}} :> 0
  }, initial, 14]

And now you can simply use Commonest to get your desired automaton.

states = 6;
initial = RandomInteger[{1, states}, {30, 30}];
ArrayPlot[#, ColorFunction -> "DarkRainbow"] & /@ 
 CellularAutomaton[{
   {{n1_, n2_, n3_}, {n4_, _, n5_}, {n6_, n7_, n8_}} :> 
    RandomChoice[Commonest[{n1, n2, n3, n4, n5, n6, n7, n8}]]
   }, initial, 100]

If you need a larger neighborhood, you may consider an auxiliary function:

neighborhood[n_?OddQ] := Module[{patt},
  patt = Array[p, {n, n}] /. {p[(n + 1)/2, (n + 1)/2] :> _, 
     p[i_, j_] :> 
      Pattern[Evaluate@Symbol[StringTemplate["p``x``"][i, j]], Blank[]]};
  With[{vars = Cases[patt, _Symbol, All]}, 
   patt :> RandomChoice@Commonest[vars]]
  ]

(* Usage *)
CellularAutomaton[{neighborhood[7]}, initial, 20]

Comparison between different sizes of neighborhood:

Answer 3

Here is the solution. If someone could reproduce it with CellularAutomaton, I'll be very appreciated.

numStates = 5; sizeBoard = 40; sizeNeibghs = 1; iters = 12;
init = RandomInteger[{1, numStates}, {sizeBoard, sizeBoard}];

Clear[newCell,myPaletteMulti];
newCell[neighbs_] := RandomChoice@Commonest@Flatten@neighbs;
myPaletteMulti[m_] := 
  Table[Hue[1. k/ m, RandomReal[{0.4, 0.7}], 
    RandomReal[{0.7, 1}]], {k, m}];

colorRules = 
  MapThread[#1 -> #2 &, {Range@numStates, myPaletteMulti@numStates}];

res = NestList[
   ArrayFilter[newCell, #, sizeNeibghs, Padding -> "Periodic"] &, 
   init, iters];

Grid[Partition[
  ArrayPlot[#, ColorRules -> colorRules, ImageSize -> 100] & /@ res, 
  4]]

As for the rule, I have studied a lot of materials on multi-state cellular automata
and oddly nowhere have I met the analysis of the simplest rule "become the most common".
So I’ll continue my research and publish a little post on Wolfram Community.