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

[Michael Vanier <mvanier@bbb.caltech.edu>]

It might interest you folks that we assigned the game of life as one of the
final exam questions in CS 1 at Caltech.  Although the question led people
through the problem step by step, I was amazed at how many of the students
(> 80%) couldn't follow directions and thus violated the spec in one way or
another.  One student wrote something to the effect of "I have no idea what
you're asking here" and then wrote a solution in a totally imperative style
(I suspect he never attended lectures, figuring he was "above it all" since
he already knew C).  We're bucking a very strongly entrenched C culture
here, and it's been tough sledding.  Hopefully next year will be easier.

Merry Christmas to all,

Mike


> Date: Tue, 25 Dec 2001 15:22:21 -0600
> From: 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!
>