On Sat, Jan 21, 2023 at 00:48 Stéphane Rollandin <lecteur@zogotounga.net> wrote:

 
> I can not map
> that implementation to the rules of the game... Can someone explain to
> me or point me to a paper/description of why that implementation works?

There is the Byte paper, around
https://archive.org/details/byte-magazine-1981-08/page/n205/mode/2up?view=theater

The figure there shows how ancilliary forms are used to count, in
parallel, the number of neighbors for each point in the pattern.

For each direction in the Moore neighborood, the pattern is shifted and
these eight shifted grids are combined together.

This is an addition in base two, and we need to count up to eight, so
the algorithm uses three forms (nbr1, nbr2 and nbr4) to store the
corresponding bits, and two other forms (carry2 and carry4) to store the
bits carried from one bit to the next (so here from nbr1 to nbr2, and
from nbr2 to nbr4), just as you need to do when performing an addition
by hand.

The last step (the last four lines in #nextLifeGeneration from the Byte
paper) generates the next pattern from nbr1, nbr2 and nbr4. The rules of
the Game of Life are encoded here in the successive combination rules,
in a nifty and quite obfuscated way that I did not even tried to
comprehend.

Stef

Right. You basically need to understand how binary counting works at a logic-gate level, to be able to comprehend the neighbor counting code. 

Typically that logic is invisible. I love this mechanical version:

https://youtu.be/zELAfmp3fXY

You can see the bits (the big 0s and 1s). The carry is the little latch sticking out to the left, and it gets set whenever a bit flips from 1 to 0, which means the next bit has to flip. 

The “bit + carry” logic is called a “half adder”, you can google that, but basically it generates the next bit and carry from the previous bit and carry using two logic operations, an XOR for the bit and an AND for the carry. 

With that understanding, Dan’s explanation in the Byte article might make more sense – it does the XOR and AND for all pixels at the same time. 

The 3 bit result count is then used to determine if a cell should be born, survive, or die. Again, logic ops do that for all pixels at once. 

The Life rule is that cells with 2 or 3 neighbors survive, any with fewer or more neighbors die, and any empty cell with 3 neighbors is born. 

To implement that rule with minimal logic, we restructure it a bit

A live cell will be there in the next generation if

(1) the cell is alive AND has 2 neighbors

(2) OR has 3 neighbors (independent of itself being alive or not)

(3) BUT it must not have 4 or more neighbors 

(1) is implemented as “self AND 2s” because the 2s bit is only set for 2, 6 and 7 neighbors (010, 110 and 111 in binary), and we deal with the >= 4 neighbors case in (3)

(2) is implemented as “self OR (1s AND 2s)” because those bits are only set together for 3 and 7 neighbors (011 and 111 in binary), and we deal with the 7 neighbors case in (3)

(3) is implemented as “self AND NOT 4s” which kills any remaining 6 and 7 neighbor cells (4, 5, and 8 neighbor cells wouldn’t have made it to this step anyways because their lower bits look like 0 and 1 neighbors: 100, 101, and 000)

This also explains why we don’t need to count to 8. With 3 bits we can only count to 7, if we add one more to 7 we get 0. But in Life this is fine because both cells with 8 and 0 neighbors have the same result. 

Hope that helps,

Vanessa