--- title: Conway's Game of Life navTitle: Game of Life slug: guides/gol kind: tutorial section: Guides order: 111 status: active summary: Implement Conway's Game of Life in Utomata. ---------------------------------------------------- # Game of Life In 1970, Martin Gardner published a [Scientific American article](https://www.ibiblio.org/lifepatterns/october1970.html) describing a "zero-player game" devised by mathematician John Conway. Despite its name, the system was not intended to simulate any particular form of life. Its evocative metaphor and remarkably simple rules nevertheless helped make [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) one of the best-known and most extensively studied cellular automata. A complete implementation of this algorithm in Utomata looks like this: ```uto &V9 = #.SUM((-1, -1), (1, 1)); &V8 = sub(&V9, #); #GOL { dim = (256, 256); set = sml(rand(), 0.1); run = max(eql(&V8, 3), eql(&V9, 3)); } ~vis { col = #GOL; } ``` [Run this sketch](https://uto.run/AU2PXWvbMBSG_8sJBAtOjWUnIZbxzT4ZtBSW1TfFF7Ilu2KylEly1hHc3z6Upt1uhHjP0aPnPcMJGEXwMgRlRg_sDIZPEhg8mKCClgLiVApgQPNiswWEwN0ow5ejB7bLEHgf1Ek2Sv4-WheAgZADn3UAhJ5P0vEIPVqvgrIG2GOGGebphm7y9o11TbMWYbIi_n7__cO3H7AgjE6Ju9fs-Q8gDNZNPJJueSe1BzZw7SVCb01wVvvPhnfRmgU3S4TZqPjCA3tsEZw0QrrDf2U73v8cnZ2NiA5ptsfrUUQ7rcan8Em5qx9tEfjUKWnCIThpxvAELEsLBKGGYfbyX0rfNz9abS-AtESKWVq27-tvI4r0whZ27rQ8KBH9L72WBcHb2fWx_7op61V6eLhLkhuKN5RgQpESUq2bfe3nLlk3Ja5Itfp6f3sWaqqTfLvDfLsjlZeh9pNOHDciIZillFRuNvXEnxP5SyfrZo8FwddriQUh1fJyUv7cW11HXrXA8hc "Game of Life") In this guide, we will break the sketch down into its basic parts and use it to introduce how cellular automata can be expressed in Utomata. We will then move beyond Conway's original rule and explore how small changes to the same structure can produce different cellular dynamics. ## What is a cellular automaton? A cellular automaton (CA) consists of a regular grid of cells. Each cell stores a value and all cells are updated at regular intervals, while typically taking into account the states of their neighboring cells. Many cellular automata algorithms, including Game of Life, use a two-dimensional grid where each cell only has two possible states: `0` and `1`, referred to as a binary state CA. At every step each cell in the grid: 1. reads its own current state value and its neighborhood 2. uses these values to calculate its new state according to the transition rule 3. commits its state to be made accessible on the next step The transition rule is shared by all cells and applied uniformly so cells never read their neighbors mid-step. This synchronous update scheme is built directly into Utomata fields. ## Setting up We begin with a field to hold the grid and a formation to display it: ```uto #GOL { dim = (256, 256); } ~vis { col = #GOL; } ``` `#GOL` contains a `256 × 256` grid of cells. We will use each cell to store a single binary state value. The algorithm itself will exists entirely in `#GOL`. The formation does not participate in the simulation; it only projects the current field values as surface color for visualization. ## Initial state Every CA algorithm starts by assigning initial values to all cells in the grid. In Game of Life, we like to describe cells as *dead* or *alive*, but that simply means they can either bear a value of (`0`) or (`1`) respectively: ```uto set = sml(rand(), 0.1); ``` `rand()` generates a random value between `0` and `1`. `sml(a, b)` compares its two inputs and returns `1` where `a < b`, and otherwise `0`. The expression therefore gives each cell a 10% chance of starting out alive. Changing the threshold changes the initial population density: ```uto set = sml(rand(), 0.5); // a 50-50 chance ``` CA algorithms are quite often *deterministic*, meaning that their evolution over time depends entirely on their transition rule and initial state. In Utomata, the pseudorandom values generated by `rand()` are seeded. This means that fields will generate the exact same outcome over any number of steps. ## The neighborhood Game of Life uses the [Moore neighborhood](https://en.wikipedia.org/wiki/Moore_neighborhood), which includes the eight cells immediately surrounding the current cell. ```text ■ ■ ■ ■ X ■ ■ ■ ■ ``` Because Game of Life uses binary state, counting the number of living neighbors is equivalent to summing their values. The neighborhood count can therefore range from `0` to `8`, ot `9` including the cell itself. In Utomata, we can begin by summing the complete `3 × 3` region centered on the current cell using the `SUM` operator: ```uto &V9 = #.SUM((-1, -1), (1, 1)); ``` This looks at cells in relative units, extending from `-1` to `+1` on both x and y. The return value is then summed and returned. note that this includes the currently evaluating cell. For convenience, we store the result in a *¯o*. To obtain only the eight surrounding cells we can subtract the current value: ```uto &V8 = sub(&V9, #); ``` Here, `#` refers to the current value of the cell being evaluated. We now have two useful quantities representing the Moore neighborhood for each cell in the field, representing the number of live neighbors, inclusive (`&V9`), and exclusive (`&V8`). ## The transition rule The algorithm for Game of Life is typically described as follows: * **Survivals:** Every cell with two or three living neighbors survives. * **Deaths:** Each cell with four or more neighbors dies from overpopulation; every cell with one neighbor or none dies from isolation. * **Births:** Each dead cell adjacent to exactly three neighbors becomes alive. Utomata lets us articulate these rules numerically: ```uto eql(&V8, 3) // part A ``` Part A is true (returns `1`) whenever the cell has exactly three live neighbors (not including itself). This covers two situations from the algorithm above: a live cell with three live neighbors (survival), or a dead cell with three (rebirth). ```uto eql(&V9, 3) // part B ``` Part B looks similar but note that the comparison uses `&V9` this time. It is therefore true (returns `1`) when a live cell has exactly two live neighbors, or when a dead cell has three. Note that the former case completes the survival rule (live cell has two or three live neighbors), while the latter case is shared by both A and B (dead cell has three). Together, A and B fulfill the survivals and births requirement, leaving only deaths. But since deaths simply mean: "return `0` for all other cases", that rule can remain implicit because all remaining cases evaluate to zero anyway. In other words - the transitioning cell should live **IF** either (part A) **OR** (part B) return `1`, and otherwise dead. In Utomata, we can describe logical OR relationships with the `max()` operator, because it would be enough for either part to be `1` for `max()` to return a non-zero value: ```text max(0, 0) → 0 // neither a nor b max(0, 1) → 1 // b but not a max(1, 0) → 1 // a but not b max(1, 1) → 1 // both a and b ``` The complete GOL rule is therefore: ```uto max( eql(&V8, 3), eql(&V9, 3) ); ``` ## Variations Conway's Game of Life is only one possible, albeit a very interesting, cellular automaton out of countless possible others. Once a system has been created with neighborhood counters and numerical comparisons, other CA algorithms rules that bare familial resemblance to the Game of Life can be explored simply by mutating the transition rule. first, let's add a few more common CA neighborhoods to play with: ```uto // Von Neumann neighborhood &V4 = #.SUM.RAD(1.25); // only 4 orthogonal neighbors // Moore neighborhood &V9 = #.SUM((-1, -1), (1, 1)); // inclusive &V8 = sub(&V9, #); // exclusive // Extended Moore neighborhood &V25 = #.SUM((-2, -2), (2, 2)); // inclusive &V24 = sub(&V25, #); // exclusive ``` Exploring new CA algorithms does not necessarily have to be an analytical endeavor. Once a neighborhood has been expressed numerically, the transition rule becomes a relatively small part of the system that can be changed independently. This makes simple trial and error surprisingly productive. Changing a comparison, combining neighborhood counts differently, or substituting one neighborhood for another can produce entirely different dynamics. The examples below are a few such mutations of the same basic setup. Try running them and observing how each rule develops over time. ```uto run = eql( sub(5, &V25), eql(0, #)); ``` ```uto run = eql(mlt(3,&V9),add(3,&V24, #)); ``` ```uto run = eql( eql(&V24, 4), sub( sub(4, &V9), &V24)); ``` ```uto run = eql( eql(1,&V8), sub( sub(6,&V24), &V9)); ``` ```uto run = eql( eql(&V24, 3), sub( sub(5, &V8), &V8)); ``` These variations still operate within a fairly narrow family: binary states, regular neighborhoods, and a single transition rule. None of these constraints are fundamental to Utomata. We can experiment with multi-channel or floating-point state values, asymmetric neighborhoods, and complex initial configurations. Several rules can be compounded within the same field, or multiple fields can evolve in parallel while reading state values from one another. From this point, the same basic CA structure can be extended in many different directions. ### Further reading For a deeper understanding of Utomata concepts used in this guide, see [Expressions](/manual/foundations#expressions) and [Lookup semantics](/manual/fields#lookup-semantics). Game of Life has generated an unusually large body of mathematical, computational, and recreational research. A few useful directions for further exploration are: * [Life-like cellular automata](https://conwaylife.com/wiki/Life-like_cellular_automaton) generalize Conway's birth and survival conditions into a compact rule notation (ie `B3/S23`), making it possible to systematically explore binary rules of the same family. * [The Life Lexicon](https://conwaylife.com/ref/lexicon/lex_home.htm), compiled by Stephen Silver, catalogs a large vocabulary of known Game of Life patterns, structures, behaviors, and terminology. * [Conway's Game of Life: Mathematics and Construction](https://conwaylife.com/book/) by Nathaniel Johnston and Dave Greene provides an extensive treatment of the mathematics, patterns, engineering, and history surrounding the system. * [SmoothLife](https://rreusser.github.io/notebooks/smooth-life/) extends Life-like dynamics from a discrete grid into a continuous spatial domain.