Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

REPOST: Artificial Intelligence FAQ: General Questions & Answers 1/6 [Monthly posting]
Section - [1-17] What are the rules for the game of "Life"?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Part7 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Business Photos and Profiles ]


Top Document: REPOST: Artificial Intelligence FAQ: General Questions & Answers 1/6 [Monthly posting]
Previous Document: [1-16] What does it mean to say a 2-player game is 'solved'?
Next Document: [1-18] What AI competitions exist?
See reader questions & answers on this topic! - Help others by sharing your knowledge

Cellular Automata, of which Life is an example, were suggested by
Stanislaw Ulam in the 1940s, and first formalized by von Neumann.
Conway's "Game of Life" was popularized in Martin Gardner's
mathematical games column in the October 1970 and February 1971 issues
of Scientific American.  (Shorter notes on life are alse given in the
column in each month from October 1970 to April 1971, and well as
November 1971, January 1972, and December 1972.) There's also quite a
bit on the game in "The Recursive Universe", by William Poundstone,
Oxford University Press, 1987, 252 pages.
 
The rules for the game of life are quite simple. The game board is a
rectangular cell array, with each cell either empty or filled. At each
tick of the clock, we generate the next generation by the following rules:

        if a cell is empty, fill it if 3 of its neighbors are filled
        (otherwise leave it empty)

        if a cell is filled, it
                dies of loneliness if it has 1 or fewer neighbors
                continues to live if it has 2 or 3 neighbors
                dies of overcrowding if it has more than 3 neighbors

Neighbors include the cells on the diagonals. Some implementations use
a torus-based array (edges joined top-to-bottom and left-to-right) for
computing neighbors. 

For example, a row of 3 filled cells will become a column of 3 filled
cells in the next generation. The R pentomino is an interesting
pattern: 

      xx
     xx
      x

Try it with other patterns of 5 cells initially occupied. If you
record the ages of cells, and map the ages to colors, you can get a
variety of beautiful images.

When implementing Life, be sure to maintain separate arrays for the
old and new generation. Updating the array in place will not work
correctly. Another optimization to to maintain a list of the cells
that changed.

Conway has demonstrated that it is possible to construct the basic
building blocks of a computer from Life using modified glider guns.
See the last chapter of  

   Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, "Winning
   Ways", Academic Press, New York, 1982, ISBN 0-120911-507.

for details.

Some interesting patterns to use include:

                                        *
   *       *      **        *           *         
    **      *     **         *          *            *  *
  **      ***            *   *                       ****
    *                     ****      ***   ***       *    *
                                                    * ** *
 Clock  Glider  Block  Spaceship        *           *    *
                                        *            ****
                                        *
                                   Traffic Light  Cheshire Cat

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA