Conway's Game of Life: Difference between revisions

Jump to navigation Jump to search

Conway's Game of Life (view source)

Revision as of 10:19, 12 April 2020

13,520 bytes removed ,  10:19, 12 April 2020
Move the John Scholes tutorial to its own page
No edit summary
(Move the John Scholes tutorial to its own page)
Line 5: Line 5:
       Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
       Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
</source>
</source>
This implementation is also explained [[#How Scholes' implementation works|later in this article]].
This implementation is also explained [[John Scholes' Conway's Game of Life|in its own article]].
 
== The Glider ==
 
One interesting pattern that occurs in Life is a [[wikipedia:Glider (Conway's Life)|Glider]]:
<source lang=apl>
      glider←3 3⍴1 1 1 1 0 0 0 1 0
      glider
1 1 1
1 0 0
0 1 0
</source>
 
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:
<source lang=apl>
      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
</source>
 
After one generation the pattern becomes:
<source lang=apl>
      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
</source>
 
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 <source lang=apl inline>⌺</source> symbol where there's a cell and a <source lang=apl inline>·</source> otherwise, for example:
<source lang=apl>
      Show←{'·⌺'[⎕IO+⍵]}
      Show grid
··········
··········
··········
··········
··········
··········
··········
·······⌺⌺⌺
·······⌺··
········⌺·
</source>
 
Here's how the Glider evolves over the first ten generations, computed using the [[Power operator]] for iteration:
<source lang=apl>
      Show¨{Life⍣⍵⊢grid}¨0,⍳9
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│······⌺···│
│··········│··········│··········│··········│··········│·······⌺··│······⌺⌺··│······⌺⌺··│·····⌺⌺⌺··│·····⌺⌺···│
│··········│········⌺·│·······⌺⌺·│·······⌺⌺·│······⌺⌺⌺·│······⌺⌺··│······⌺·⌺·│·····⌺⌺···│·····⌺····│·····⌺·⌺··│
│·······⌺⌺⌺│·······⌺⌺·│·······⌺·⌺│······⌺⌺··│······⌺···│······⌺·⌺·│······⌺···│·······⌺··│······⌺···│··········│
│·······⌺··│·······⌺·⌺│·······⌺··│········⌺·│·······⌺··│··········│··········│··········│··········│··········│
│········⌺·│··········│··········│··········│··········│··········│··········│··········│··········│··········│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
</source>
 
== How Scholes' implementation works ==
If you're completely new to APL, this explanation is probably not the place to start, rather check out our [[Tutorials#Introductions|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:
 
<source lang=apl>
      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
</source>
=== Rotation ===
If we rotate each row of the grid one place left by using APL's [[Rotate]] function <source lang=apl inline>⌽</source>, 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:
 
<source lang=apl>
      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
</source>
 
Similarly we can rotate right to find the left-hand neighbour by using <source lang=apl inline>¯1⌽currentGeneration</source>. By using APL's [[Outer Product]] operator <source lang=apl inline>∘.</source> 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:
 
<source lang=apl>
      ¯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│
└─────────┴─────────┴─────────┘
</source>
 
Here <source lang=apl inline>currentGeneration</source> must be [[enclose]]d 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 <source lang=apl inline>⊖</source>. Used with an Outer Product this gives us a series of 9 grids:
 
<source lang=apl>
    ¯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│
└─────────┴─────────┴─────────┘
</source>
 
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 [[ravel]]ling the [[shape]] <source lang=apl inline>3 3</source> [[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 [[Boolean]]s 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:
 
<source lang=apl>
      +/,¯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│
└─────────┘
</source>
 
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]] <source lang=apl inline>3 4</source> 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 [[enclose]]d, we could obtain a similar, but flat, result using another [[Outer Product]].
 
<source lang=apl>
    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│
└─────────┴─────────┘
</source>
 
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, <source lang=apl inline>∧</source>
<source lang=apl>
    (⊂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│
└─────────┘
</source>
 
(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:
<source lang=apl>
      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│
└─────────┘
</source>
 
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:
<source lang=apl>
      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│
└─────────┘
</source>
 
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, <source lang=apl inline>∨</source>. We could write this rather long-windedly as:
<source lang=apl>
    (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│
└─────────┘
</source>
 
=== 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 <source lang=apl inline>∨.∧</source> in the following:
 
<source lang=apl>
    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│
└─────────┘
</source>
 
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 ==
Line 266: Line 19:
* [http://youtube.com/watch?v=a9xAKttWgP4 John Scholes' famous video] on YouTube
* [http://youtube.com/watch?v=a9xAKttWgP4 John Scholes' famous video] on YouTube
* [http://dfns.dyalog.com/n_life.htm John Scholes' notes], as part of the [[dfns workspace]], includes a more in-depth treatment
* [http://dfns.dyalog.com/n_life.htm John Scholes' notes], as part of the [[dfns workspace]], includes a more in-depth treatment
== References ==
== References ==
<references />
Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/3242’

Navigation menu