Sunday, July 20, 2014

Frequency-based CA visualization (using Single Rotataion as an example)

Single Rotation rule, color shows flashing rate. Note that different spaceships have different colors.

In the binary cellular automata, cells can have only 2 states: ON and OFF. This, monochrome images are the most natural choice to visualize such automata. While informative, this visualization method produces somewhat dull images, especially when spaceships don't have easily recognizable form. My first idea to make it a bit fancier was to add some motion blur, emphasizing spaceships, and it worked well:

Single Rotation rule, with motion blur

Motion blur is effectively a low-pass filter applied to the original BW image. The next idea was to use a combination of several filters to make image more colorful. In my final application, 3 filters were used:

  • Low-pass filter, detecting cells that are constantly ON. This filter was assigned to the red channel.
  • High-pass filter, detecting cells that are flashing with period 2 (ON-OFF-...). Green channel was used for this filter.
  • Band filter (2-nd order), detecting cells, flashing with period 4. If was used for blue.
Together, these 3 filters produce images like this:

Single Rotation rule, with 3 different frequency filters for each color channel.

The picture above shows the Single Rotation rule, where random reactions produce many different kinds of spaceships. Interestingly, this colorization scheme allows to distinguish different spaceships by their colors. Finally, by applying these filters to the animation, you'll get the video above. In this video, the field is initialized with random block at the center (at first it appears red because of high cell concentration), and a vertical bar of 2 cells. In the "Single Rotation" rule, such bar of cells is an example of indestructible still life. After the simulation is started, dense random block starts dissipating, emitting multiple spaceships of different kinds. Single Rotation rule supports a lot of them!

For those who prefer higher resolutions, a HD version is available. Full screen and "HD" quality are recommended.

This colorization algorithm can be applied to any other cellular automata too. For example, here is Conway's Life. Note how still lifes are colored in red, and p2 oscillators are green:

Conway's Life, colorized using the same algorithm. See also HD version.


All sources for this post are published at Github:

To use them, clone the repository above, build C++ modules, executing
$ make
and then run
$ python
This will create a sequence of animation frames, that can later be converted to video, using ffmpeg. I used the following command line for conversion (not sure it is the best one though):
ffmpeg -i frame%04d.png -movflags faststart -c:v\
     libx264 -preset veryfast -bf 2 -g 15 -crf 23\
     -pix_fmt yuv420p -r 30 animation.mp4
At the time of writing, settings for the script above are done inside the source code.


Three discrete time filters are used to detect flashing frequencies:
$$\begin{eqnarray} x_{t+1} &=& k x_t + s_t,\\ y_{t+1} &=& - k y_t + s_t,\\ z_{t+1} &=& i z_t + s_t. \end{eqnarray}$$
Where \(k \approx 0.99\) is a decay coefficient, \(s_t\) is a t-th state of the cell (0 or 1), i is a complex unity. Then, RGB color for the pixel is obtained by formulas:
$$ \left( \begin{array}{c}r\\g\\b \end{array} \right) = k_\gamma rgb',$$ $$rgb' = \mathbf{K} \left( \begin{array}{c}x \\ |y| \\ |z| \\ \end{array} \right), $$
where K is color transformation matrix and \(k_\gamma\) is gamma correction coefficient. The latter is calculated like this:
$$k_\gamma = \max(r', g', b')^{\gamma-1}.$$
where \(\gamma\) is the gamma correction value (in the video above, 0.2 was used). For the top picture, the following colorization matrix was used:
$$\mathbf{K}=\left(\begin{array} 18.7& 0 & 0 \\ 0 & 94 & -15.7 \\ 0 & 0 & 68 \end{array}\right).$$

Sunday, July 13, 2014

Single Rotation Spaceships (205 of them)

TL;DR: 205 Single rotation spaceships.

The “Single Rotation” rule (it's my personal naming, it could be already known under the different name) is a very simple reversible cellular automaton, acting on a field with Margolus neighborhood. In this rule, each 2x2 block is rotated by 90° if it has exactly one alive cell. All other blocks remain unchanged. Despite its simplicity, this rule supports a multitude of different pattern types, and is especially interesting for me because of its spaceships. There are hundreds of spaceships with different periods.

Some spaceships of the Single Rotation rule. All spaceships on this animation are different.

Live version of this animation can be seen in the online simulator.

Even simple observations showed that random reactions in this rule naturally produce more than ten different spaceships. Of course, ten was not enough so I tried to find more of them. This post is a digest of what I have found.

Spaceship search method

Random initial block produces multiple spaceships. Motion blur added to emphasize moving patterns.

The method to search for spaceships was simple: take an empty field and put a random initial block in its center. During evolution, random reaction would produce multiple spaceships, which are then removed from the field and automatically classified. Typical parameters, used for search:

  • Field size: 128x128.
  • Initial random block size: 80x80.
  • Initial pattern density: 40%.
  • Simulation time: 30000 generations.
Several days of search brought a list of 205 different spaceships. To identify them, 108'720'436 moving patterns were analyzed. Here are the top 10 most frequent spaceships from this list:

First 10 spaceships, ordered by the natural production rate. See the whole list.

Posting the whole list of 205 spaceships here would blow up the post, so I've uploaded it to a separate page. You can download the data for this list in different formats:

  • JSON library for the online simulator. To use it in the simulator, copy-paste it to the bottom text area on the “Library” pane of the simulator, and click “Import from JSON”
  • CSV file.
  • Google documents spreadsheet.

Digesting the data

Size distribution

All discovered spaceships have 4 to 9 cells. The distribution of their sizes shows good agreement with power law:

Logarithmic plot of the probability to catch spaceship of size n, for n 4...9.
Probability of the natural production plotted against spaceship weight. Dashed line is a best-fit power law distribution.

Power law approximation (dashed line on the plot) gives the following distribution: $$P_n \approx \frac{0.679} {{17.55}^{n-4}},$$ where Pn is a probability of a randomly produced spaceship having weight n. For 10-cell spaceships, this formula gives expected probability P10=2.33·10-8. Thus, the expected number of 10-cellers is 2 or 3, while none were discovered. Either I have bad luck, or the actual probability is lower, or maybe these spaceships have too large periods, and were not detected.

4-cell spaceships

Lightest spaceships have 4 cells and there are exactly 6 different spaceships of such size (I don't have a proof, but it should be easily provable by enumeration). Lightest spaceships have some interesting properties, mentioned in the previous post.

5-cell spaceships

Only 6 spaceships made of 5 cells were discovered during the search, all with significant hit counts. This suggests that there are no other 5-cell spaceships. From them, 2 are diagonal, and 4 are orthogonal. Curious coincidence: the most common diagonal 5-celler have a phase, that looks exactly as the Conway's Life glider.

The most common diagonal 5-cell spaceship, suspiciously resembling a phase of the Conway's glider

It moves by 1 cell every 15 generations, and its intermediate steps don't resemble glider at all, so this resemblance is nothing more than a coincidence. The other diagonal 5-celler is the R-pentomino.

Heavier spaceships

Number of different spaceships increases with weight, the experiment discovered 57 different 6-cell spaceships and 69 spaceships of 7 cells. Some of them are extremely rare, having probability less than 3.31e-07, which suggests that there are more spaceships, too rare to be discovered. The heaviest spaceships discovered are 10 different 9-cellers. Of them the most common one, detected 26 times, is $b2o$b3o$3bo$obo$2bo, fast diagonal spaceship with period 31 and velocity c/31.

The most common 9-cell spaceship and its evolution. Try it in the simulator.

No heavier spaceships were detected.


Smalest periods

Among the discovered spaceships, the smallest period are:

  • orthogonal: 12 generatons, achieved by the 4-cell spaceship b2o2$b2o,
  • diagonal: 11 generations, 6-cell spaceship obo$obo$b2o.
Two spaceships with smallest periods: p12 orthogonal (left) and p11 diagonal (right)

Interestingly, record for the diagonal spaceships is achieved by the relatively heavy (6 cells) and rare (probability 0.08%) pattern. Are there any heavier moving patterns with smaller periods? I don't know (though intuition says no).

Highest period

While in the Conway's Game of Life naturally produced spaceships and oscillators commonly have small periods, in the "Single Rotation" rule there are numerous patterns taking extremely long time to start repeating.

Obviously, there is no upper limit for the spaceship period. But among known (to me) patterns the one with highest period is orthogonal 8-cell spaceship b3o$o3b2o2$bo$2bo. It takes whopping 9046 generations to move horizontally by 2 cells (thus its speed is c/4523).

Spaceship with the highest known period 9046.


Fastest spaceships

As one may expect, the pair of the spaceships with the smallest periods also hold the speed record. Their movement speeds are:

Two fastest spaceships (same pair that has smallest periods).

Whether there are any faster patterns is an open question. It is easy to prove that in the "Single Rotation" rule spaceship velocity can not exceed c/2, but this estimation is very rough.

Slowest spaceships

The slowest spaceship found is the 8-cell pattern 2bo$b2o$2bo4$bo$bo$2b2o. Its speed is c/4755.

The slowest known (to me) spaceship, c/4755.

The period of this spaceship is not the largest, but it moves only by 1 cell, where the P9046 moves by 2 cells.

Open questions

  • Smallest period. Current record is 11 generations, held by the 6-cell pattern: obo$obo$b2o. Are there spaceships with faster period?
  • Fastest spaceship. It is easy to prove that spaceship velocity can't be more than c/2. Currently, the speed record is c/6 for orthogonal and c/11 for diagonal spaceships. Are there any faster ones?
  • Oblique spaceships (knightships). So far, no oblique (neither diagonal nor orthogonal) spaceships were found. Are there any?
  • Spaceship families. Some spaceships are clearly forming families. For example, family of period 31 spaceships with 7, 8 and 9 cells. How to find them? Are there infinite families?
  • 10-cellspaceships. None found yet.