Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

Need help in finding topic for research project

9 views

Skip to first unread message

Nick Bennett

unread,

Dec 15, 1996, 3:00:00 AM12/15/96

I am a high school student who would like to do a science fair research
project in the area of cellular automata, perhaps focusing on two
dimensional cellular automata (Conway's game of life), but I cannot think
of what to do that would make it a project. I have made a simple program
in Pascal and C which is a simple implementation of Conway's game of
life, and it is fun to play with the patterns and change the rules, but I
need to find a way in which I can conduct an experiment in this area, and
produce data.

If you could give me any information that might help me in finding a
particular topic, or if you might direct me in finding an experiment in
which I may find data, or results, I would greatly appreciate it.

Nick Bennett
ni...@jtan.com
ni...@kd3bj.ampr.org

Paul Callahan

unread,

Dec 16, 1996, 3:00:00 AM12/16/96

I started writing this posting with reference to the subject line, but
it's grown into something more general, namely an open-ended summary of
the Game of Life problems that strike me as interesting. So I hope
that this will be of interest to others besides high school students
looking for science fair projects.

Of course, all of this is contained in some form on my web page, but I
have never tried to summarize it in one article.

In article <nick.85...@kd3bj.ampr.org>,

Nick Bennett <ni...@kd3bj.ampr.org> wrote:
>I am a high school student who would like to do a science fair research
>project in the area of cellular automata, perhaps focusing on two
>dimensional cellular automata (Conway's game of life), but I cannot think
>of what to do that would make it a project. I have made a simple program
>in Pascal and C which is a simple implementation of Conway's game of
>life, and it is fun to play with the patterns and change the rules, but I
>need to find a way in which I can conduct an experiment in this area, and
>produce data.

Actually, there are a lot of potential projects that go beyond just
implementing the game, and are suitable to all levels of
mathematical depth and programming expertise. I suspect that Life projects
have been done before for science fairs, and a lot of them have
looked very much alike. But if you inform yourself of the state of the
art, you can do something that has never been proposed or implemented for
a science fair, and possibly has never been done before by anyone. OK, I'm
biased here, since I've spent more time than makes any sense studying this CA,
but I would be pretty interested in seeing someone put together a truly
original science fair project based on it. In fact, I can think of one
specific project offhand that I haven't done yet, but can be completed
within a predictable time frame and will yield some results. I'll get to
that after some general comments.

I'm more than happy to propose a list of problems, but I'm not sure whether
you are expected to come up with your own problem or are allowed to use one
that is suggested by someone else. Coming up with a good problem is often
the hardest part of research. If outside help is allowed to any extent,
and if you like any of my suggestions or use any of my advice, I expect
you to disclose this fact to the committee judging your project. That's
just the way scholarship is done.

First, if you haven't done this already, find the following books in
your local public library (or local university library):

- Berlekamp, Conway, and Guy: Winning Ways (for your Mathematical
Plays), Volume 2, (c)1982. ISBN 0-12-091152-3.

- Gardner, Martin: Wheels, Life, and Other Mathematical Amusements,
(c)1983. ISBN 0-7167-1589-9.

- Poundstone, William: The Recursive Universe, (c)1985.
ISBN 0-688-03975-8.

I'm cutting and pasting from Alan Hensel's bibliography here. He also
notes that the following Scientific American issues refer to Life:

- Scientific American: Oct 70, Nov 70, Jan 71, Feb 71, Mar 71,
Apr 71, Nov 71, Jan 72, Dec 75, Mar 84, May 85, Feb 87, Aug 88,
Aug 89, Sep 89, Jan 90.

If you have access to a web browser (ideally with Java), see
my web page for a survey of what is known or considered interesting
about the game. The URL is http://www.cs.jhu.edu/~callahan/lifepage.html
This also has links to other Life pages.

Even implementing the game is a challenge if you want it to be fast.
There are a lot of tricks for accelerating the generation code by
exploiting sparsity (i.e. most cells are dead at any time) and
bit parallelism (some operations can be done simultaneously by packing
cell values into 32-bit words). See http://users.vnet.net/alanh/life/
to see just how much of a programming challenge this can be.

I am not sure what you mean by a simple implementation, but if what
you have so far is just a direct implementation of the rules with all
the cells in a 2D array, then I recommend you at least write a sparse
implementation before proceeding any further. In a sparse implementation,
the live cells are stored in a list and the work in computing a generation
is proportional to the number of live cells. The simplest way I ever
found of doing this is by keeping an array of cells in row major order.
This is used in the applet on my web page, as well as in an X Motif
implementation, also on my web page.

Another method proposed for accelerating Life is Gosper's "Hashlife." This
achieves dramatic speedups for certain regular patterns. However, it is
not nearly as useful for producing animated displays of smaller, less
structured interactions. An implementation of it would still make an excellent
data structures exercise. I'll just quote the information from an old posting
by Chris Langton:

For a better description of the algorithm Gosper used, see his chapter
``Exploiting regularities in Large Cellular Spaces'' in the book: Cellular
Automata, edited by Farmer, Toffoli, and Wolfram, published by North Holland
in 1984. This was a book version of the proceedings of the 1983 CA conference
at Los Alamos, originally published as a special issue of the Journal
Physica-D.
The original citation is: Physica 10D, (1984) pp.75-80. There are many other
interesting articles on CA's in this volume as well...., especially those by
Toffoli, Margolus, Vichniac, Grassberger, and Wolfram.

Unfortunately, I don't recall any source code for Gosper's algorithm being
included in his article...

But running Life as fast as possible is just the tip of the iceberg. There
are some interesting search problems too. Here are just the categories
I can think of offhand:

* Syntheses, or ways of colliding gliders and simple objects
to produce more complex objects. I wrote a program once to solve some of
these problems automatically. You can find it linked to my page. The
more complex syntheses have to be found by human beings. A good
web source is http://www.halcyon.com/hkoenig/LifeInfo/LifeInfo.html

* Perturbations, in which an object affects an interaction but is not
itself destroyed. I recently did some work on this, but have not put
the code in any usable form. My main result was to find a way of
building a stable reflector using the outcome of such a search and some
recent results by David Buckingham.
See http://www.cs.jhu.edu/~callahan/patterns/p1/p1.html

* Methuselahs, or small patterns that take a very long time to stabilize.
The first known methuselah was the r pentomino, but even longer lasting ones
have been found by enumerating and testing small patterns. The following,
called "rabbits," takes over 10000 generations to stabilize.

*...***
***..*
.*

Writing an efficient methuselah search is a challenge, and if you
can beat rabbits (which I think is the longest running methuselah
known so far) then it would be a very interesting result.

* Oscillators and spaceships. This is probably the most active area of
search problems. For exhaustive search techniques for finding low period
oscillators, see David Bell's ANSI C program
(http://www.cs.jhu.edu/~callahan/lifesearch.txt).
The more complicated oscillators need to be found "by accident" for the
most part, and many surprising ones were found by Achim Flammenkamp
using "random soup" experiments. His web page is
http://www.minet.uni-jena.de/~achim/gol.html

* Still lifes, or period-1 oscillators are easy to find by exhaustive
constraint-satisfaction search (compared to the higher periods), but
I also found a randomized fixed point approach that worked surprisingly
well. See http://www.cs.jhu.edu/~callahan/stilledit.html
This includes a Java applet and a description of the method. One project
would be to vary the parameters and see what choice leads to fastest
convergence. Another would be to generalize the technique to period 2
and higher. Finally, if someone could explain to me why my program works
at all, I would be grateful. I suppose it shares some properties of
simulated annealing.

* A garden of eden is a pattern with no predecessor. These can probably
be found with a variation of David Bell's technique. Achim provides a
small example on his page, and an even smaller one would be a new result.

Personal biases here: I don't find methuselahs and garden of eden patterns
as interesting as the others, because they can't be combined to build
patterns that behave in interesting ways. However, it's still an interesting
challenge to write search programs to look for them.

The specific problem I alluded to up at the top is something that
I have been thinking of doing, but probably won't do for a long time if
ever. David Buckingham's Herschel conduits (see
http://www.cs.jhu.edu/~callahan/patterns/p1/p1.html)
can be used to construct arbitrary period guns and oscillators.
I constructed a few guns by doing a backtracking search just on
algebraic criteria to find sequences of conduits that put the
Herschel back in its original spot. However, this completely ignores
the fact that a track found this way might cross itself and might (will
usually) release internal gliders that destroy the construction.
I ignored this fact and simply tried to fix up the constructions by
hand. Some obviously don't work, while others can be be repaired by
placing eaters in the right spots.

So what I thought about doing was to augment all 8 of the conduits
with eaters to destroy the excess gliders and then do a backtracking
search of just the closed tracks that don't interfere. The criteria
for interference is a little conservative, but the enumeration is
automatic. The goal would be to enumerate closed tracks or track segments
realizing a certain transformation. Two track segments, each of which
realizes the same transformation in a different number of generations
are particularly useful for obtaining oscillator periods. It should
be possible to find many compact "Herschel guns" of periods 70 and higher.
There are potentially ways to accelerate the search by doing dynamic
programming to take care of the algebraic criteria. I think that tracks
of up to several thousand generations can be enumerated this way, since
I already made it up to 1800 or so using a backtracking method with
fewer constraints.

Anyway, hope this (a) helps (b) is not more than I should be telling someone
who wants to do a science fair project and (c) is of interest to readers
who are not high school students.

--
Paul Callahan (call...@inf.ethz.ch)
Web Page: http://wwwjn.inf.ethz.ch/paul/

Eugene Leitl

unread,

Dec 27, 1996, 3:00:00 AM12/27/96

to Nick Bennett, ca

Implement your rules via lookup table, and step through several rules,
quantizing resulting behaviour. If space's too big, make a representatve
sample. Estimate the size of those rules producing qualitatively
different behaviour. Try to describe the boundary between those producing
qualitatively different behaviour.

ciao,
'gene

On Sun, 15 Dec 1996, Nick Bennett wrote:

> I am a high school student who would like to do a science fair research
> project in the area of cellular automata, perhaps focusing on two
> dimensional cellular automata (Conway's game of life), but I cannot think
> of what to do that would make it a project. I have made a simple program
> in Pascal and C which is a simple implementation of Conway's game of
> life, and it is fun to play with the patterns and change the rules, but I
> need to find a way in which I can conduct an experiment in this area, and
> produce data.
>

> If you could give me any information that might help me in finding a
> particular topic, or if you might direct me in finding an experiment in
> which I may find data, or results, I would greatly appreciate it.
>
> Nick Bennett
> ni...@jtan.com
> ni...@kd3bj.ampr.org
>
>

0 new messages