Aperiodic Game of Life

We begin by breaking down the term aperiodic monotile:

• A tiling is a set of prototiles which tile the plane without any gaps or overlaps. A prototile is the smallest unit — a single shape — in a tiling such as the Einstein Hat (Figure 1) and the Spectre (Figure 2). The shapes may be translated, rotated and reflected to form the tiling.
• A monotile is a tile which covers the plane while being the only prototile in its tiling.
• An aperiodic monotile tiles the plane, but never periodically. To emphasize: A monotile which tiles the plane aperiodically and also periodically (by using a different arrangement of the prototiles) is not an aperiodic monotile. A periodic tiling is a tiling with translational symmetry, i.e., there exists a translation which yields the same tiling.

Recently, Smith et al. discovered the first aperiodic monotile [1], the Einstein Hat (Figure 1). More precisely, they discovered an infinite set of aperiodic monotiles of which the Einstein Hat is a member. The definition of monotile permits using the monotile’s reflection in the tiling, which is also necessary for the Einstein Hat’s tiling.

Soon after, Smith et al. noticed an interesting property of the Tile(1,1), another member of this infinite set of aperiodic monotiles: while their original schema for generating tilings revealed Tile(1,1) as only tiling periodically (if using reflections), they discovered that it also tiles aperiodically (without using reflections) [2]. As such, Tile(1,1) is a weakly chiral aperiodic monotile: an aperiodic monotile which tiles only aperiodically when reflections are forbidden. However, having a periodic and an aperiodic tiling is not permitted for an aperiodic tiling as described earlier. The solution in this case is easy: by modifying the edges of Tile(1,1), the authors gain a strictly chiral aperiodic monotile, an aperiodic monotile which only tiles aperiodically, even when allowing reflections. The authors dubbed this as the Spectre (Figure 2).

Game of Life, invented by mathematician John Conway in 1970, is an example of a cellular automaton. It is a simulation that is run on a grid of cells. Each cell is either alive or dead. Typically, an alive cell is displayed black and a dead cell is displayed white. These cells evolve through generations, with their states determined by the states of neighboring cells and accompanying rules. The rules dictate that a live cell with exactly two or three neighbors survives and otherwise dies, while a dead cell with three live neighbors becomes alive. This interplay of cells gives rise to complex patterns that demonstrate emergent behavior.

This standard rule set alone has been studied extensively, yielding structures dubbed as Spaceships, Oscillators, and Puffers among many others. They are documented in the LifeWiki here. Additionally, different rule set have been explored as well, and even exensions of the rules such as considering the age of a cell.

We denote the standard rule set as described above as B3/S23, i.e., a dead cell comes alive (Birth) in the next generation if it has 3 neighbors and an alive cell stays alive (Survival) until the next generation if it has either 2 or 3 neighbors.

The neighbors or neighborhood of a cell refers to the Moore neighborhood which is defined as all cells that are orthogonally or diagonally-adjacent to the cell. Extending this definition to an aperiodic tiling, we define the neighborhood of a cell as all cells which share at least one vertex with the cell (modulo floating-point imprecision).

To tile the plane with Einstein Hats or Spectres, we re-implemented the algorithm for generation of supertiles used by Smith et al. in Rust. We will describe only the gist of the algorithm here since the algorithm is conceptually simple but complex in the finer details. We will take the tiling of the Einstein Hat as an example, but the Spectre tiling works very similarly.

The algorithm is based on the same idea that the authors use to prove their tilings’ aperiodicity. Starting from the Hat prototile, we construct four different metatiles and call them \(H\), \(T\), \(P\), and \(F\) (Figure 5). This is level \(0\) in Figure 4. For constructing level \(1\), we follow the rules shown in Figure 6 to assemble the supertiles using the tiles from level \(0\). Generally, for constructing level \(n\), we use the tiles from level \(n-1\). Iterating on this process yields a tree datastructure, because we reference the tiles from one level below. Note that in Figure 4, arrows pointing from level \(1\) down to level \(0\) point to different instances of the metatiles. This is only for clarity of the visualization. In our implementation, these arrows would all be pointing on the same single instances of the \(H\), \(T\), \(P\), \(F\) metatiles.

Following this process, we generate arbitrarily large tilings.

An essential part of calculating new generations of Game of Life is finding the state of each cell’s neighbors.

In a traditional periodic grid of squares, finding neighbors of a cell is straightforward. Neighbors are found by simple index access. Consider a \(5\times5\) grid which is stored as single array of length \(25\), then the \(8\) neighbors of a cell with index \(x\) are found by subtracting and adding \(1\) from \(x\) for the left and right neighbors, and additionally considering the grid’s width \(w\) for the neighbors above and below \(x\) (Figure 9).

For aperiodic tilings this approch is not feasible — precisely because the tiling is aperiodic there is no flat grid structure which indirectly stores neighbors. One option to determine a cell’s neighbors in the aperiodic case is to use the tree structure of supertiles as explained in Constructing Aperiodic Tilings. Taking the \(H\) metatile of the Einstein Hat as an example, some of the neighbors of a cell \(c\) are already known by the metatile’s definition. However, for the other neighbors, we would need to traverse the tree to the metatile’s parent and determine which of \(H\)’s siblings contain more of \(c\)’s neighbors. In (literal) edge cases, this would still not suffice: Some of \(c\)’s neighbors could be at the edge of the current supertile, necessitating another traversal to its parent, etc. While this algorithm for determining neighbors is likely performant, it is highly complex. Apart from that, it is only applicable to one specific tree structure of meta-tiles, i.e., if we implemented this algorithm for the Einstein Hat, we could not reuse it for the Spectre tiling.

Another option is to use a k-d tree. A k-d tree is a binary space-partitioning data structure often used in computer graphics. It is useful for our application because it enables fast neighbor search in a k-dimensional space (\(\mathcal{O}(\log n)\) on average). A tiling on the plane resides in a 2-dimensional space, so its binary partition is a 2-d tree. A major benefit of this approach is that it is generic: Finding a cell’s neighbors this way works for any periodic or aperiodic tiling. Additionally, performance characteristics are not crucial for neighbor determination since we only need to do it once. For every cell, we save which other cells are its neighbors and use the results in every new generation.

The steps of the algorithm are as follows:

1. For each cell, query cells within a distance.
   The distance needs to large enough to include at least all true neighbors of the cell. However, this also includes cells which are not adjacent to the cell. Due to the aperiodic nature of the tiling, there is no single fixed distance which always includes all neighbors and only neighbors of the cell.
2. Keep only those cells which are adjacent to the cell.

One of the basic and most famous configurations in Conway’s Game of Life is the glider (Figure 11): a pattern which moves across the board indefinitely (if undisturbed) in one direction. Structures like the glider are also called spaceships. Unfortunately, it is very unlikely (or maybe even impossible) to find such a structure in an aperiodic tiling, precisely because it is aperiodic. Spaceships rely on returning to their initial state in a different location after a number of generations in order to move across the board. An aperiodic tiling does not guarantee this by definition.

When filling the whole board with alive cells and stepping through B356/S0123456 (and variations thereof), we observe intricate aperiodic patterns. Figures 12 and 14 show the first step after filling the whole board with alive cells. In Figure 14, there are straight lines of alive (black) cells angled at -15°, 45°, and 105°, forming triangles. However, most of them are not continuous which is due to the aperiodicity of the tiling. What we essentially see here is the visualization of how many neighbors each cell has: Since we used the rule S0123456, all cells with more than 6 neighbors died, i.e., are white. The black cells are those with 7 neighbors. (This can also be verified by following the same steps with the rule S0123457 and observing the inverse of Figure 14.) All cells have either 6 or 7 neighbors (excluding the cells at the edge of our generated tiling). The same is true for the Spectre tiling.

Stepping through these configurations further, we observe intricate patterns emerging, changing at every step and — depending on the specific rule used — devolving into chaos (figures to the right of 13 and 12). The patterns seem to be periodic at first glance, but they’re not. When looking at the details there are always slight differences in the pattern. (Compare with Figure 14, where we observe straight lines and repeating structures, which are not quite continuous and periodic upon further inspection.)

Another interesting structure becomes apparent when adding some random noise to the board and letting the rule B3/S234 evolve. We observe that cells form “crystals”, shapes which have many straight edges and seem to expose an underlying pattern in the aperiodic tiling. This happens for both Spectre and Einstein Hats. Additionally, these shapes are resilient to negative noise: if we remove a random amount of alive cells (up to around 50%), the shapes mostly reorganize into their previous form.