Cellular Automata Rules Optimizing a Global Pattern Value

Abstract

The objective is to find Cellular Automata (CA) rules that can evolve 2D patterns that are optimal with respect to a global value function. Here we define the global value as the sum of locally computed utilities. A utility, or local value function, assigns a score based on the states in the local neighborhood. The problem is solved in four steps: (0) defining the utility function, (1) finding optimal master patterns with a Genetic Algorithm, (2) extracting templates (local neighborhood configurations), (3) inserting the templates into a general CA rule. The constructed CA rules generate optimal or near-optimal patterns for both even and odd grid sizes. Optimal patterns of odd size contain exactly one thin spot, which is a 2 $\times$ 2 block of zeroes.