wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Game of Life
        
(Message started by: JocK on Jul 11^th, 2005, 10:37am)

Title: Game of Life
Post by JocK on Jul 11^th, 2005, 10:37am

In the Game of Life (http://mathworld.wolfram.com/Life.html after some time not all states can occur any more. In fact, independent of the exact starting configuration: when one waits long enough, only states that form part of a cycle can occur.

Can you determine for repetitive patterns of NxN cells (i.e. the same NxN configuration extended indefinitely in all spatial directions) how many states can survive after an indefinite time? (It suffices to give the asymptotic expression for the number of states for large N.)

Title: Re: Game of Life
Post by towr on Jul 11^th, 2005, 12:00pm

I can give an upper limit of 2^nxn ;D

btw, If the field isn't finite and not periodic, then it can have more states than just those that are part of a cycle, no matter how long you wait.

Title: Re: Game of Life
Post by Leonid Broukhis on Jul 11^th, 2005, 6:50pm

on 07/11/05 at 12:00:06, towr wrote:

I can give an upper limit of 2^nxn ;D

btw, If the field isn't finite and not periodic, then it can have more states than just those that are part of a cycle, no matter how long you wait.

I think the trick is to find a set of small patterns that cannot appear in a periodic configuration.

Title: Re: Game of Life
Post by towr on Jul 12^th, 2005, 12:29am

on 07/11/05 at 18:50:49, Leonid Broukhis wrote:

I think the trick is to find a set of small patterns that cannot appear in a periodic configuration.

Like shooters?

Title: Re: Game of Life
Post by Barukh on Jul 12^th, 2005, 12:52am

I am sorry, I don't understand what's the question (although it looks intriguing ;)).

Could anybody elaborate, please?

Title: Re: Game of Life
Post by SMQ on Jul 12^th, 2005, 6:26am

Quote:

Could anybody elaborate, please?

Delighted. :) The "game of life" is a celular automaton developed by mathematician John Conway in the 70's and popularized in Sci. Am.'s Mathematical Recreations column.

The basic rules are simple; imagine an infinite sheet of (square) graph paper, with each cell either "alive" (filled) or "dead" (unfilled). This is the current "generation." The next generation is calculated by applying the following three rules to every cell simultaneously:

1) If a cell is alive and has fewer than two neighboring (orthogonally or diagonally) cells alive, it dies of lonliness.

2) If a cell is alive and has more than three neighboring cells alive, it dies of starvation.

3) If a cell is dead and has exactly three neighboring cells alive, it comes alive.

By applying these simple rules to repeated generations, a surprising variety of stable, pulsing, and moving "life forms" develop. (For instance, an isolated 2x2 square is stable as each cell has three neighbors.)

----------

Now, the question is: given a repeating N by N grid (or, alternatively, an NxN toroidal grid) rather than an infinite planar grid, how many of the 2^N*N states are possible after sufficient number of generations have elapsed for the pattern to "settle"?

For instance, the all-cells-alive state is not a possible "settled" state, as every cell has eight neighbors and so dies of starvation on the next generation, leaving the all-cells-dead state, which is stable.

Somewhat clearer?

--SMQ

Title: Re: Game of Life
Post by Leonid Broukhis on Jul 12^th, 2005, 8:07am

on 07/12/05 at 00:29:51, towr wrote:

Like shooters?

I could not find shooters in Life lexicon: http://www.bitstorm.org/gameoflife/lexicon/

What are they?

Title: Re: Game of Life
Post by Grimbal on Jul 12^th, 2005, 9:44am

I'd say a glider gun or any periodic pattern that sends out an infinite stream of gliders.

http://en.wikipedia.org/wiki/Conway's_Game_of_Life

Title: Re: Game of Life
Post by JocK on Jul 12^th, 2005, 11:31am

on 07/12/05 at 06:26:14, SMQ wrote:

[..] the question is: given a repeating N by N grid (or, alternatively, an NxN toroidal grid) rather than an infinite planar grid, how many of the 2^N*N states are possible after sufficient number of generations have elapsed for the pattern to "settle"?

Excellent explanation SMQ!

Let me add a simple example. Consider a 4x4 square grid with periodic or toroidial boundary conditions (just imagine the left hand edge to be connected to the right hand edge, and the upper edge to the lower edge).

Starting from a certain configuration, a cycle of period 2 develops (see picture, blue squares indicate 'active' cells, white squares indicate 'dead' cells). In this case the configuration evolves to the 2-cycle in just one step. Clearly, the initial pattern will never appear again. Even a stronger conclusion can be drawn: no matter what starting configuration is chosen on this 4x4 toroidial grid, after a sufficiently large number of timesteps the pattern shown as the starting pattern in the figure will never appear. In other words: after many timesteps 'transient patterns' will have died out; what remains are the cyclic patterns (incl. cyclic patterns with period 1 i.e. stationary patterns).

Out of the 2^NxN states of the game-of-life on a toroidal NxN grid, for large values of N, what fraction can be classified as cyclic?

Title: Re: Game of Life
Post by JocK on Jul 12^th, 2005, 11:52am

To get you going I will give away the solution for N=2:

For a 2x2 torroidial grid out of the 16 possible patterns, the only cyclic patterns are five patterns with period 1 (see figure).

Checking a total of 16 states is quite manageable. However, the number of possible states grow rapidly with the gridsize: a 3x3 grid has 512 possible states, and a 4x4 grid (as shown in the post above) has a whopping total of 65,536 states.

Just in case you wondered why it is in the 'hard' category... 8)

Title: Re: Game of Life
Post by River_Phoenix on Jul 12^th, 2005, 1:25pm

do stable configurations count? ie period=0

Title: Re: Game of Life
Post by JocK on Jul 12^th, 2005, 1:32pm

on 07/12/05 at 13:25:12, River_Phoenix wrote:

do stable configurations count? ie period=0

Stable configurations do count as cycles of period 1.

(We define the period as the minimum number of timesteps needed for the pattern to recur.)

Title: Re: Game of Life
Post by SMQ on Jul 14^th, 2005, 7:57am

The first few values (by exhaustive computation):

1 - 1 (of 2; 50%)
2 - 5 (of 16; 31.25%)
3 - 127 (of 512; 24.80%)
4 - 1245 (of 65536; 1.90%)
5 - 8406 (of 33554432; 0.025%)

I can probably compute 6x6, and maybe 7x7 in a reasonable amount of time using the method I've been using (create a digraph of all the 2^N*N states to their successors, count the number of nodes belonging to a cycle), but I'm going to need to modify my program substantially to handle states > 32 bits and tables > available memory...
;D

--SMQ

Title: Re: Game of Life
Post by Barukh on Jul 15^th, 2005, 12:56am

Very impressive, SMQ! :D

Maybe, the following page (http://dotat.at/prog/misc/life.html) will help you in your computations.

Title: Re: Game of Life
Post by SMQ on Jul 15^th, 2005, 8:09am

on 07/15/05 at 00:56:08, Barukh wrote:

Maybe, the following page (http://dotat.at/prog/misc/life.html) will help you in your computations.

An interesting read, but I think I'm to the point where time spent managing data structures outweighs time spent actually calculating state. Reaching to 7x7 would require a 64 TB bitmap (or its equivalent) just to track which states have already been seen.
:o

--SMQ

Title: Re: Game of Life
Post by Barukh on Jul 15^th, 2005, 9:35am

SMQ, what is the maximal size of a cycle you've found so far?

Title: Re: Game of Life
Post by SMQ on Jul 15^th, 2005, 10:25am

for 5x5 there are 5181 distinct cycles, with a maximal period of 20 generations.

My current algorithm works like this:

for every possible state {
loop until an already-considered state is encountered {
mark this state considered
calculate the next state
}
if this is a new cycle {
add the number of states in the cycle to the total
}
}

This requires a rather modest data structure to store all cycles encountered, and a huge datastructure to store all states encountered. The savings from the huge datastructure is in not recalculating traversals for every state in the traversal--a savings which increases dramatically with larger N--but lacking the storage space, even on disk, I may have to see if I have the time instead...

--SMQ

Title: Re: Game of Life
Post by Leonid Broukhis on Jul 15^th, 2005, 1:33pm

on 07/15/05 at 10:25:07, SMQ wrote:

For 6x6 a modest 64-bit machine (with 8+ Gb of virtual memory) should be enough. I hope you're using 1 bit per state to mark if it has been encountered.

Title: Re: Game of Life
Post by JocK on Jul 16^th, 2005, 5:52am

Impressive progress SMQ!

The big question is: do these extensive search data for grids up to 5x5 allow you to postulate - with some confidence - an asymptotic expansion for the number of cyclic (attractor) states?

If not, would solving the 6x6 (and 7x7) problem allow you to do so?

Or do you need much larger grids? :-/

Even if the asymptotic expansion has not been derived yet, the data obtained by SMQ already contain a whealth of information. For instance: the smallest non-trivial case (3x3) has all 126 states with 4 active cells as stationary (cycle-1) solutions. (Why?) SMQ's data shows that for a 3x3 grid, apart from the vacuum state (zero active cells) and these 4-active-cell states, there are no other cyclic solutions. (Can you explain why?)

The cyclic configurations for grids larger than 3x3 can not be captured with such a simple rule. However, for grids up to 5x5, SMQ should have complete information on the average density of active cells in the cyclic configurations.

Also, SMQ will be able to tell you for each cycle what is the size of the 'attractor basin' (the number of initial states that evolve into this cycle). Furthermore, SMQ can tell you what cycle lengths do occur.

Finally, to do exhaustive computer searches on progressively larger grids, you may want to use symmetries to reduce the memory requirements. For instance, if you know the evolution from a certain specific state, you also know the evolution from a configuration that is shifted (an integer number of lattice units in each direction) compared to the original state. And apart from this invariance of the evolution under translations, you also have an invariance under 90^o rotations (i.e. a fourfold rotational symmetry).

Title: Re: Game of Life
Post by Barukh on Jul 18^th, 2005, 12:07am

What do you think about the plausibility of the following statements:

1. No repetitive pattern has an isolated live cell.

2. For n sufficiently large, every repetitive pattern has at least n dead cells that are disjoined from any live cell.

:-/

Title: Re: Game of Life
Post by SMQ on Jul 18^th, 2005, 11:06am

As JocK said above, I can indeed provide all sorts of nifty statistics. :)

N = 1:
Cycle Length = 1:
Cycles: 1
Cycle States: 1 (50%)
Basin States: 2 (100%)
Density: avg = 0, stddev = 0
Overall:
Cycles: 1
Cycle States: 1 (50%)
Basin States: 2 (100%)
Density: avg = 0, stddev = 0

N = 2:
Cycle Length = 1:
Cycles: 5
Cycle States: 5 (31.25%)
Basin States: 16 (100%)
Density: avg = 0.4, stddev = 0.2
Overall:
Cycles: 5
Cycle States: 5 (31.25%)
Basin States: 16 (100%)
Density: avg = 0.4, stddev = 0.2

N = 3:
Cycle Length = 1:
Cycles: 127
Cycle States: 127 (24.8%)
Basin States: 512 (100%)
Density: avg = 0.440945, stddev = 0.0392825
Overall:
Cycles: 127
Cycle States: 127 (24.8%)
Basin States: 512 (100%)
Density: avg = 0.440945, stddev = 0.0392825

N = 4:
Cycle Length = 1:
Cycles: 53
Cycle States: 53 (0.08%)
Basin States: 56328 (85.95%)
Density: avg = 0.301887, stddev = 0.112419
Cycle Length = 2:
Cycles: 180
Cycle States: 360 (0.55%)
Basin States: 3896 (5.94%)
Density: avg = 0.361111, stddev = 0.10449
Cycle Length = 4:
Cycles: 16
Cycle States: 64 (0.1%)
Basin States: 64 (0.1%)
Density: avg = 0.375, stddev = 0
Cycle Length = 8:
Cycles: 96
Cycle States: 768 (1.17%)
Basin States: 5248 (8.01%)
Density: avg = 0.359375, stddev = 0.0441942
Overall:
Cycles: 345
Cycle States: 1245 (1.9%)
Basin States: 65536 (100%)
Density: avg = 0.352174, stddev = 0.0930063

N = 5:
Cycle Length = 1:
Cycles: 3456
Cycle States: 3456 (0.01%)
Basin States: 3.1115e+007 (92.73%)
Density: avg = 0.416667, stddev = 0.0855267
Cycle Length = 2:
Cycles: 1225
Cycle States: 2450 (0.01%)
Basin States: 1.4918e+006 (4.45%)
Density: avg = 0.40898, stddev = 0.107138
Cycle Length = 3:
Cycles: 200
Cycle States: 600 (0%)
Basin States: 5600 (0.02%)
Density: avg = 0.44, stddev = 0
Cycle Length = 4:
Cycles: 200
Cycle States: 800 (0%)
Basin States: 733400 (2.19%)
Density: avg = 0.39, stddev = 0.0519615
Cycle Length = 5:
Cycles: 20
Cycle States: 100 (0%)
Basin States: 7300 (0.02%)
Density: avg = 0.32, stddev = 0
Cycle Length = 10:
Cycles: 60
Cycle States: 600 (0%)
Basin States: 30500 (0.09%)
Density: avg = 0.4, stddev = 0.0432049
Cycle Length = 20:
Cycles: 20
Cycle States: 400 (0%)
Basin States: 170800 (0.51%)
Density: avg = 0.2, stddev = 0
Overall:
Cycles: 5181
Cycle States: 8406 (0.03%)
Basin States: 3.35544e+007 (100%)
Density: avg = 0.413318, stddev = 0.0893921

--SMQ

[edit]OOPS! Corrected Std. Dev.s[/edit]

Title: Re: Game of Life
Post by rmsgrey on Jul 18^th, 2005, 3:11pm

on 07/18/05 at 00:07:16, Barukh wrote:

1) Possible but implausible - for instance, having multiple glider guns arranged so that their gliders collide and mutually annihilate, it may be possible to arrange that the decaying products of the collision include an isolated live cell.

2) I'm not sure exactly what you mean - if you mean for n to also be the side length of the universe, then I'd point out that [hide]a chessboard is a scalable (for even n) stable configuration with every dead cell adjacent to 4 live cells...[/hide]

Title: Re: Game of Life
Post by JocK on Jul 19^th, 2005, 4:01pm

on 07/18/05 at 15:11:08, rmsgrey wrote:

a chessboard is a scalable (for even n) stable configuration with every dead cell adjacent to 4 live cells...

a 'chessboard' configuration stable? It gets eradicated in one single step...! ;)

Title: Re: Game of Life
Post by SMQ on Jul 20^th, 2005, 3:28pm

Hot off the presses: results for 6x6 after ~22 hours calculation. (That would put 7x7 well out of reach at ~20 years...maybe as little as a year on the best hardware I have available to me...)

N = 6:
Cycle Length = 1:
Cycles: 15335
Cycle States: 15335 (0%)
Density: avg = 0.323436, stddev = 0.100935
Cycle Length = 2:
Cycles: 1584
Cycle States: 3168 (0%)
Density: avg = 0.24865, stddev = 0.102528
Cycle Length = 3:
Cycles: 50
Cycle States: 150 (0%)
Density: avg = 0.282778, stddev = 0.108995
Cycle Length = 4:
Cycles: 379
Cycle States: 1516 (0%)
Density: avg = 0.305812, stddev = 0.0598782
Cycle Length = 5:
Cycles: 14
Cycle States: 70 (0%)
Density: avg = 0.264683, stddev = 0.0649449
Cycle Length = 6:
Cycles: 116
Cycle States: 696 (0%)
Density: avg = 0.344588, stddev = 0.0604157
Cycle Length = 7:
Cycles: 26
Cycle States: 182 (0%)
Density: avg = 0.301129, stddev = 0.0215201
Cycle Length = 8:
Cycles: 192
Cycle States: 1536 (0%)
Density: avg = 0.269513, stddev = 0.0411078
Cycle Length = 10:
Cycles: 4
Cycle States: 40 (0%)
Density: avg = 0.244444, stddev = 0
Cycle Length = 12:
Cycles: 47
Cycle States: 564 (0%)
Density: avg = 0.279748, stddev = 0.00645926
Cycle Length = 24:
Cycles: 6
Cycle States: 144 (0%)
Density: avg = 0.125386, stddev = 0.00272804
Overall:
Cycles: 17753
Cycle States: 23401 (0%)
Density: avg = 0.315548, stddev = 0.101981

--SMQ

Title: Re: Game of Life
Post by rmsgrey on Jul 21^st, 2005, 11:03am

on 07/19/05 at 16:01:44, JocK wrote:

a 'chessboard' configuration stable? It gets eradicated in one single step...! ;)

Blech. Misremembered the ruleset (I keep wanting 4 neighbours to be a third survival case)

In that case, vertical stripes does the same thing as I claimed for chessboard.

Title: Re: Game of Life
Post by JocK on Jul 22^nd, 2005, 8:43am

on 07/18/05 at 00:07:16, Barukh wrote:

Rmsgrey has given a counterexample for 2. A counterexample for 1 can be found for a 5x5 grid (see picture).

This configurations is one of the 800 configurations on a toroidial 5x5 grid (as simulated by SMQ) that are part of a 4-cycle (blue squares denote active cells, and white regions represent dead cells).

Title: Re: Game of Life
Post by JocK on Jul 22^nd, 2005, 8:57am

on 07/20/05 at 15:28:46, SMQ wrote:

Hot off the presses: results for 6x6 after ~22 hours calculation. (That would put 7x7 well out of reach at ~20 years...maybe as little as a year on the best hardware I have available to me...)

Ahhh... the limits of 'brute force'... ;)

So we have to do with:

1, 5, 127, 1245, 8406, 23401, ...

... unless we approach this differently...?

Title: Re: Game of Life
Post by SMQ on Jul 23^rd, 2005, 7:03am

Yep, I always knew brute forc wasn't going to win this one, but it was fun to see how far I could get. :)

The results for 2 through 6 are very nearly linear when plotted log-log, giving a nice exponential relationship, but there is a clear trend at the end toward lesser slope, so I don't trust the exponential to hold as a reasonable approximation much further out...

For my next trick, I plan to convert my brute force simulator to monte carlo and use the known values for 1-6 to see how many cases might need to be run for higher N to get reasonable approximate results.

--SMQ

Title: Re: Game of Life
Post by JocK on Jul 23^rd, 2005, 8:16am

on 07/23/05 at 07:03:42, SMQ wrote:

Yep, I always knew brute forc wasn't going to win this one, but it was fun to see how far I could get. :)

Way further than I would have deemed possible!

I find it truly amazing to see what can be achieved these days with standard of-the-shelf hardware: computing the successors of all 68,719,476,736 configurations of a 6x6 grid to map out the complete set of dynamic cycles... wow!

Title: Re: Game of Life
Post by SMQ on Jul 28^th, 2005, 6:05am

Hmm, I'm not getting anywhere with the monte carlo analysis.

Thing is, trying to do it the straightforward way is obviously futile. The number of cycle states is such a vanishingly small fraction of the total number of states as to make the analysis infeasible. If only one state in a gadzillion is a cycle state, you need to run somewhere around two gadzillion trials to get anything approaching a reasonable estimate, and so the effort grows very nearly with 2^N*N!

I tried a neat statistical trick based on the assumption that encountering any of the cycles was equally likely from a random starting point, but that assumption proved wildly inaccurate. For N=5, for instance, the attractor basin of the vacuum state (all cells dead) is over 2/3 of the state space, while there are 110 stable patterns (still lifes) with no predecessors, and so an attractor basin of 1 state.

There are three values I can think of which are readily obtainable from a monte carlo analysis of reasonable computational complexity: average cycle length, average cell density in a cycle, and average number of non-cycle states before encountering a cycle. Unfortunately, I can't think of any way to correllate any of those values to the total number of cycle states.

Any other ideas?

--SMQ

Title: Re: Game of Life
Post by Barukh on Jul 28^th, 2005, 9:35am

SMQ, knowing what's persistence, I'm really impressed by yours!

I still believe that there should be some basic characteristics (invariants) specific for cyclic patterns. SMQ, your database contains now several tens of thousands of those. You may extract some useful information.

Your tables already supply a lot of (statistical) information. Interestingly enough, the cell densities are mainly distributed in a falrly small interval. For N=6, all but one group falls into interval [0.24, 0.34]. It may well be that when N grows, the "main" interval becomes smaller.

So, what about generating configurations with density 0.3?

Another idea is to appeal to a large community of "Game of Life" researchers. I am sure they will find this problem interesting enough.