Re: Conway's Game of Life (cellular automata)

[Bill Richter <richter@math.northwestern.edu>]

    (board-map new-cell-state game-board))

Thanks, Anton & Matthias, I understand now.  I blew 2 principles:

1] Make the high level abstractions independent of the low-level
implementation details.

2] Solve the Math problem first!

Here's the high-level code, a variation on Anton's, then a Math
discussion.  This isn't a trivial C program, as I falsely claimed.

(define (next-generation-Life game-board)
  (let* ((padded-game-board (add-double-white-border game-board))
         
         (padded-next-generation (board-map-interior Conway 
						     padded-game-board)))
        (trim-blank-borders padded-next-generation)))


`add-double-white-border' takes a NxM-dimensional game board and
returns the (N+4)x(M+4)-dimensional game board obtained by padding
with 2 layers of white cells on all sides.

`board-map-interior' applies a local cellular automata function (a
function from 3x3-dimensional game boards to colors) to the compute
the next generation of the interior of a game board.

`trim-blank-borders game-board' strips off any blank edges (top,
bottom, left or right) of the border of game-board.

Conway is our local cellular automata function, with possibly this
implementation-specific definition:

(define (Conway nw n ne
                w cell e
                sw s se)
  ;; Returns new cell value in Conway Game of Life iteration on the cell 
  ;; whose value is `cell', using Anton's simplified formula:
  (let ((count (count-surrounding-black-cells nw n ne
                                               w    e
                                               sw s se)))  
    (if (or (= count 3)
            (and (= count 2) 
                 (cell-black? here)))
        black-cell-value
        white-cell-value)))


And then the implementation of game boards & board-map can be done
either as lists of lists (as I did), or vectors of vectors (matrices),
or OOP-ishly, where a cell has a state and functions `north', `east'
... which returns it's nearest neighbors.   

The Math jaw:

A *game board* is a rectangular array of *cells*, and each cell has a
state (for us, black or white).  A game board is a disjoint union of
its *border* (union of the edges on top, bottom, left & right) and its
*interior* (everything else).  Note that an interior cell has 8
nearest neighbors, and a cell on the border has either 5 (edge) or 3
(corner) nearest neighbors.  A game board can be "padded" with white
cells, by adding in a larger border of white cells.

A local cellular automata function takes a 3x3 game board and returns
the next generation state for the one interior cell.  The local
function is required to return white for an all-white 3x3 game board.

A cellular automata takes a game board and returns the next
generation, which is a game board of possibly larger size, by applying
the local cellular automata function to each cell.  

By the `white->white' local function requirement, we can embed the
game board is a larger game board obtained by padding the game board
with extra white cells.  

We must pad the game board with extra white cells in order to handle
the border of the game board, and also in order for the game board to
"grow": Possibly a cell that's just off the game board (by definition
white) should change colors on account of the states of cells on the
border.

My `three-in-row-real?' testing was of marginal value.  Essentially
the only way to see if the border must be expanded is to compute just
past the border.  So might as well do that, and then strip off the
blank edges.  And for a general local cellular automata function, it's
not clear how to generalize `three-in-row-real?'.  



So thanks for explaining, and sorry for posting my ignorance so often.
I was whining I couldn't handle the low-level implementation details,
and you guys pointed out that my problems were high-level!  Part of it
was that I assumed that CS folks would know cellular automata much
better than a pure mathist like me.  I'll post the code when I get it
finished, or just put it on my web site if I can figure out how.  I
need to learn Dorai's Slitex or something like that.

I liked the Michelangelo Sistine Chapel Christmas picture in DrScheme!
Merry Christmas and Happy Hanukkah!