Finite Life’s long trajectories

2021-11-27, post № 252

simulation, #cellular-automata

Conway’s Game of Life is classicly played on the infinite two-state grid $\mathbb{F}_2^{\mathbb{Z}^2}$ with only a finite number of cells lit in the starting configuration. Due to its particular rules, Turing machines can be embedded within it, making it equivalently powerful computationally. Paired with the non-existence of a uniform distribution on countably infinite discrete sets, homogenously reasoning about trajetories of all Games of Life is hindered by both an unclear enumeration and fundamental limits of computation.
More tractably, Life can be played on a discrete torus with finitely many states. Because of this global size limitation, Turing completeness is lost since only finitely many world states exist. For host architecture’s compatibility’s sake, I chose to play in an 𝟪 ⨉ 𝟪-sized toric world represented as an uint64_t; with Life’s rules implemented by bit-fiddling. C++20 kindly offers std::pop_count which, paired with bit-wise neighbourhood masks, allows for a clean rule encoding:

const int pc{std::popcount(w & neighbourhood_masks[j])};
if (pc == 3 || (w & (1ULL << j) && pc == 2))
    v |= 1ULL << j;

The corresponding masks are compile-time generated using a constexpr-evaluated lambda returning a std::array<world_t, 64>. Source: fgol-traj.cpp

With finite Life defined and implemented, the question I set out to ask can be posed:

For how long can one play finite Life until revisiting a world state?

In the finite directed graph of all $2^{64}$ states with edges representing one time step of evolution according to Life’s rules, one seeks to find world states which either take a long time to fall into a cycle or ones which lead into large cycles. In that regard, this maximum time is an indicator of the ‘entropic depth’ of this simulation.

Since the search space is too vast to be exhaustively searched, the 64 bits which make up a state are pseudo-randomly uniformly chosen and evolved. Keeping track of previously simulated initial state’s times, a record is kept. As of now, the longest trajectory length has been 401, achieved by the following starting configuration:

$ ./fgol-traj 0558cdc8400d3b35
world 0558cdc8400d3b35:
[]  []  [][]    
[][]  [][][]    
[]  [][]        
            []  
      []    [][]
[]  [][]    [][]
      [][]  []  
[]  []          

trajectory length until first self-colision: 401
periodicity: 132
first point of periodicity: 0000c0b070000000

Before this trajetory length, two states were found with a score of 375: 8e423847408ec519 and 94c0f9892ad05be8.

Yet this method only achieves lower bounds. Starting states which take longer than 300 steps to repeat already seem to be quite rare; finding the above state took multiple hours of searching. And because of this problem’s highly non-continuous nature, a rogue state could be lurking out there in the vastness of thought, waiting to be discovered by someone.