Conway's Game of Life: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
Line 252: Line 252:
</source>
</source>


The final expression ends with a bit of housekeeping using <source lang=apl inline>↑</source> to turn the result back into a simple array (it's currently nested).
The final expression ends with a bit of housekeeping using [[Mix]] (<source lang=apl inline>↑</source>) to turn the result back into a simple array (it's currently nested).


== Historical implementations ==
== Historical implementations ==

Revision as of 09:15, 12 April 2020

Conway's Game of Life is a well-known cellular automaton in which each generation of a population "evolves" from the previous one according to a set of predefined rules. The Game of Life is defined on an infinite Boolean grid, but usually only finite patterns, where all 1 values fit in a finite Boolean matrix, are studied. Because it involves interactions between adjacent elements of the matrix, and can take advantage of APL's convenient and fast Boolean handling, implementing the Game of Life is a popular activity for APLers. Published APL implementations have appeared since 1971, a year after the rules of the Game of Life were first published.

A famous video by John Scholes[1] explains the following Dyalog APL implementation step by step. The implementation takes advantage of nested arrays and the Outer Product to produce many copies of the argument array. It finds adjacent elements by rotating the original array, causing elements at the edge to wrap around (giving a torus geometry).

      Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

This implementation is also explained later in this article.

The Glider

One interesting pattern that occurs in Life is a Glider:

      glider←3 3⍴1 1 1 1 0 0 0 1 0
      glider
1 1 1
1 0 0
0 1 0

To see how the Glider evolves over the generations, we need to give it some space to move around. The Game of Life takes place on an infinite two-dimensional grid, but that might be a bit large for our computer! Let's start the Glider off in the bottom right-hand corner of a 10 x 10 grid:

      grid←¯10 ¯10↑glider
      grid
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0

After one generation the pattern becomes:

      Life grid
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0

The Glider has slightly changed shape and also moved up and to the left.

Visualising it

To make the pattern easier to see, we can use indexing to place a symbol where there's a cell and a · otherwise, for example:

      Show←{'·⌺'[⎕IO+⍵]}
      Show grid
··········
··········
··········
··········
··········
··········
··········
·······⌺⌺⌺
·······⌺··
········⌺·

Here's how the Glider evolves over the first ten generations, computed using the Power operator for iteration:

      Show¨{Life⍣⍵⊢grid}¨0,⍳9
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│······⌺···│
│··········│··········│··········│··········│··········│·······⌺··│······⌺⌺··│······⌺⌺··│·····⌺⌺⌺··│·····⌺⌺···│
│··········│········⌺·│·······⌺⌺·│·······⌺⌺·│······⌺⌺⌺·│······⌺⌺··│······⌺·⌺·│·····⌺⌺···│·····⌺····│·····⌺·⌺··│
│·······⌺⌺⌺│·······⌺⌺·│·······⌺·⌺│······⌺⌺··│······⌺···│······⌺·⌺·│······⌺···│·······⌺··│······⌺···│··········│
│·······⌺··│·······⌺·⌺│·······⌺··│········⌺·│·······⌺··│··········│··········│··········│··········│··········│
│········⌺·│··········│··········│··········│··········│··········│··········│··········│··········│··········│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

How Scholes' implementation works

If you're completely new to APL, this explanation is probably not the place to start, rather check out our introductions. However, you should be able to get some idea of what's happening even if the details are not yet clear. Just bear in mind that APL evaluates expressions from right to left unless you use parentheses.

To compute a new generation in the Game of Life we first need to find out how many neighbours each live cell has. To keep things simple let's consider the following 5-by-5 grid:

      currentGeneration←5 5⍴0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0
      currentGeneration
0 0 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0

Rotation

If we rotate each row of the grid one place left by using APL's Rotate function , each element is replaced by its right-hand neighbour. In other words, the new grid will have a 1 for all cells whose right-hand neighbour was 1:

      1⌽currentGeneration
0 0 0 0 0
0 1 1 0 0
1 1 0 0 0
0 1 0 0 0
0 0 0 0 0

Similarly we can rotate right to find the left-hand neighbour by using ¯1⌽currentGeneration. By using APL's Outer Product operator ∘. together with the Rotate function we can get a set of three grids containing the left-hand neighbour, the original grid, and the right-hand neighbour:

      ¯1 0 1∘.⌽⊂currentGeneration
┌─────────┬─────────┬─────────┐
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 1 1│0 0 1 1 0│0 1 1 0 0│
│0 0 1 1 0│0 1 1 0 0│1 1 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┴─────────┘

Here currentGeneration must be enclosed before applying the outer product so that it is treated as a single element rather than rotating each of its Boolean elements (which would have no effect).

Extending to two dimensions

Now we can use a similar trick but rotate up and down by using APL's First Axis Rotate function . Used with an Outer Product this gives us a series of 9 grids:

     ¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┬─────────┬─────────┐
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 1 1│0 0 1 1 0│0 1 1 0 0│
│0 0 1 1 0│0 1 1 0 0│1 1 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
├─────────┼─────────┼─────────┤
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 1 1│0 0 1 1 0│0 1 1 0 0│
│0 0 1 1 0│0 1 1 0 0│1 1 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
├─────────┼─────────┼─────────┤
│0 0 0 1 1│0 0 1 1 0│0 1 1 0 0│
│0 0 1 1 0│0 1 1 0 0│1 1 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┴─────────┘

The grid in the centre is our original grid, and the others give the neighbours above, below, left, right and diagonally.

Summing it up

Now we can find out how many neighbours each cell in the original grid has by summing (Plus Reduce) the corresponding elements in each of the 9 grids. We sum all the grids at once by ravelling the shape 3 3 matrix of grids to obtain a 9-element vector; otherwise Reduce would only allow us to sum rows or columns. Here APL's representation of Booleans as numbers is advantageous, since otherwise counting the number of true values would require converting them to numbers or using conditional logic. For a live cell the sum is 1 more than the number of neighbours—for example, a 4 in the result means a cell has three neighbours. For a dead cell the result is just the number of neighbours:

      +/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 1 2 2 1│
│1 3 4 3 1│
│1 4 5 4 1│
│1 3 3 2 0│
│0 1 1 1 0│
└─────────┘

For a cell to exist in the next generation, one of two rules must be met:

  • Any live cell with two neighbours lives, unchanged, to the next generation
  • Any cell, live or dead, with exactly three neighbours is live in the next generation

This means that all cells which might be live in the next generation will have a sum of 3 (from the first rule) or 3 or 4 (from the second rule).

So we're interested in cells with a sum of 3 or 4. We can find these cells with a simple application of Equal to, relying on pervasion and scalar extension to distribute the data properly. The result of the last step was a scalar containing one grid; when paired with the vector 3 4 it is extended to give two grids. Within each grid 3 and 4 are compared with every element by scalar extension again. If the right argument were a flat array rather than being enclosed, we could obtain a similar, but flat, result using another Outer Product.

     3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┬─────────┐
│0 0 0 0 0│0 0 0 0 0│
│0 1 0 1 0│0 0 1 0 0│
│0 0 0 0 0│0 1 0 1 0│
│0 1 1 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┘

The next step is best understood by first considering the two scores 4 and 3 separately.

(a) A score of 4 corresponds either to a live cell with three neighbours or a dead cell with four neighbours. Only in the former case do we get a cell in the next generation - i.e. we get a cell if the score is 4 and the cell is currently live. Here we're using APL's And function,

    (⊂currentGeneration)∧4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 0 0 0 0│
│0 0 1 0 0│
│0 1 0 0 0│
│0 0 0 0 0│
│0 0 0 0 0│
└─────────┘

(b) A score of three corresponds either to a live cell with two neighbours or a dead cell with three neighbours. In either case we get a cell in the next generation:

      3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 0 0 0 0│
│0 1 0 1 0│
│0 0 0 0 0│
│0 1 1 0 0│
│0 0 0 0 0│
└─────────┘

We can write this slightly redundantly by and-ing with 1 (meaning "and the cell is alive or dead") for reasons which will become apparent shortly:

      1∧3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 0 0 0 0│
│0 1 0 1 0│
│0 0 0 0 0│
│0 1 1 0 0│
│0 0 0 0 0│
└─────────┘

So the next step is to say that a cell is live if either test (a) or test (b) is met. We need to use APL's Or function, . We could write this rather long-windedly as:

     (1∧3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration)∨(⊂currentGeneration)∧4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 0 0 0 0│
│0 1 1 1 0│
│0 1 0 0 0│
│0 1 1 0 0│
│0 0 0 0 0│
└─────────┘

Refactoring

But we can take advantage of APL's Inner Product operator to do the and operations of each test and then or the result - the ∨.∧ in the following:

     1 currentGeneration∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
┌─────────┐
│0 0 0 0 0│
│0 1 1 1 0│
│0 1 0 0 0│
│0 1 1 0 0│
│0 0 0 0 0│
└─────────┘

The final expression ends with a bit of housekeeping using Mix () to turn the result back into a simple array (it's currently nested).

Historical implementations

First published in October 1970 by Martin Gardner in Scientific American[2], Conway's Game of Life quickly became a popular target of APL implementation. Jean Jacques Duby's 7-line interactive implementation appeared in APL Quote Quad exactly a year later[3], and was followed by a 9-line implementation in February 1972[4] and both a 6-line and a 4-line implementation in June 1972[5].

A survey of previous APL implementations along with two new 23-token implementations was given by Eugene McDonnell in "Life: Nasty, Brutish, and Short", published in the APL88 conference proceedings.[6] McDonnell also described how future language features, such as the Commute operator and a tesselation operator related to Cut and the much later Stencil, might reduce this to as few as 11 tokens (one of which is a long list of integers), or to 9 tokens when using a pre-defined vector of matrices.

John Scholes published a video in which he explains his own implementation of Life, the same as the function Life above, in 2009.[1] Scholes' function resembles McDonnell's APL2 implementation in its use of three-element vertical and horizontal rotation vectors, but uses Inner Product and Outer Product rather than Each as well as a different arithmetic scheme.

External links

References

  1. 1.0 1.1 Scholes, John. "Conway's Game of Life in APL". 2009-01-26.
  2. Gardner, Martin (October 1970). "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123.
  3. Jean Jacques Duby. "Conway's Game "Life"", APL Quote Quad Vol. III No. 2 & 3. 1971-10-01.
  4. Bruce A. Beebe. "Life". APL Quote Quad Vol III No. 4. 1972-02-10
  5. W. J. Jones, "Game of Life" and D. A. Bonyun, "Game of Life". APL Quote Quad Vol III No. 5. 1972-06-05
  6. McDonnell, Eugene. "Life: Nasty, Brutish, and Short". APL88 Conference Proceedings, APL Quote-Quad Vol. 18 No. 2, 1987-12.