Author |
Topic: Game of Life (Read 2867 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Game of Life
« on: Jul 11th, 2005, 10:37am » |
 Quote  Modify
|
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.)
|
| « Last Edit: Jul 11th, 2005, 10:45am by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Life
« Reply #1 on: Jul 11th, 2005, 12:00pm » |
Quote Modify
|
I can give an upper limit of 2nxn 
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Game of Life
« Reply #2 on: Jul 11th, 2005, 6:50pm » |
Quote Modify
|
on Jul 11th, 2005, 12:00pm, towr wrote:I can give an upper limit of 2nxn
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Life
« Reply #3 on: Jul 12th, 2005, 12:29am » |
Quote Modify
|
on Jul 11th, 2005, 6:50pm, Leonid Broukhis wrote:
I think the trick is to find a set of small patterns that cannot appear in a periodic configuration. |
|
Like shooters?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Game of Life
« Reply #4 on: Jul 12th, 2005, 12:52am » |
Quote Modify
|
I am sorry, I don't understand what's the question (although it looks intriguing  ).
Could anybody elaborate, please?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #5 on: Jul 12th, 2005, 6:26am » |
Quote Modify
|
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 2N*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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Game of Life
« Reply #7 on: Jul 12th, 2005, 9:44am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
on Jul 12th, 2005, 6:26am, 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 2N*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 2NxN states of the game-of-life on a toroidal NxN grid, for large values of N, what fraction can be classified as cyclic?
|
| « Last Edit: Jul 12th, 2005, 11:38am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
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... 
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Game of Life
« Reply #10 on: Jul 12th, 2005, 1:25pm » |
Quote Modify
|
do stable configurations count? ie period=0
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Life
« Reply #11 on: Jul 12th, 2005, 1:32pm » |
Quote Modify
|
on Jul 12th, 2005, 1:25pm, 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.)
|
| « Last Edit: Jul 12th, 2005, 2:40pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #12 on: Jul 14th, 2005, 7:57am » |
Quote Modify
|
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 2N*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...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Game of Life
« Reply #13 on: Jul 15th, 2005, 12:56am » |
Quote Modify
|
Very impressive, SMQ! 
Maybe, the following page will help you in your computations.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #14 on: Jul 15th, 2005, 8:09am » |
Quote Modify
|
on Jul 15th, 2005, 12:56am, Barukh wrote:
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.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Game of Life
« Reply #15 on: Jul 15th, 2005, 9:35am » |
Quote Modify
|
SMQ, what is the maximal size of a cycle you've found so far?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #16 on: Jul 15th, 2005, 10:25am » |
Quote Modify
|
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
|
| « Last Edit: Jul 15th, 2005, 10:26am by SMQ » |
IP Logged |
--SMQ
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Game of Life
« Reply #17 on: Jul 15th, 2005, 1:33pm » |
Quote Modify
|
on Jul 15th, 2005, 10:25am, SMQ wrote: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 |
|
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.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Life
« Reply #18 on: Jul 16th, 2005, 5:52am » |
Quote Modify
|
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 90o rotations (i.e. a fourfold rotational symmetry).
|
| « Last Edit: Jul 16th, 2005, 6:13am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Game of Life
« Reply #19 on: Jul 18th, 2005, 12:07am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #20 on: Jul 18th, 2005, 11:06am » |
Quote Modify
|
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]
|
| « Last Edit: Jul 18th, 2005, 11:57am by SMQ » |
IP Logged |
--SMQ
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Game of Life
« Reply #21 on: Jul 18th, 2005, 3:11pm » |
Quote Modify
|
on Jul 18th, 2005, 12:07am, Barukh wrote: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.
|
|
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 a chessboard is a scalable (for even n) stable configuration with every dead cell adjacent to 4 live cells...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Life
« Reply #22 on: Jul 19th, 2005, 4:01pm » |
Quote Modify
|
on Jul 18th, 2005, 3:11pm, 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...!
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Game of Life
« Reply #23 on: Jul 20th, 2005, 3:28pm » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Game of Life
« Reply #24 on: Jul 21st, 2005, 11:03am » |
Quote Modify
|
on Jul 19th, 2005, 4:01pm, 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.
|
| « Last Edit: Jul 21st, 2005, 11:04am by rmsgrey » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print