How to assess how far a pattern is from randomness

[HartmutHolzwart]

Suppose you are given a pattern on a say 100x100 grid. You know that it was produced from a random field by evolving a few generations.

Can one estimate from some statistical properties what was the number of generations?

If we know that the number of generations was less than 10, does that change the assessment?

I would guess from having looked at many random universes evolve that it should be possible for the first few generations, but never got a grip on it neither formalyy nor heuristically.

It might be possible to get somewhere by transforming the pattern in e.g the frequency domain, but I never tried.

How would you tackle this question?

[tracefleeman]

Life is non-reversible. Unless the pattern was a Garden of Eden, it would be impossible.

[codeholic]

How would you tackle this question?

I would write a program that would collect some statistics about certain patterns appearing in a certain generation from the starting broth. The challenge is that unstable patterns are most valuable ones for making an assessment. I expect common evolutionary sequences to be quite representative, such as honey farm, lumps of muck, teardrop etc. The longest living common evolutionary sequence that has a chance to survive in a relatively thick broth to be recognisable is probably the pi. So I don't think that one can estimate the "age" of a pattern older than 170 generations anyhow reliably. But if a broth is not as thick, one could even probably spot some evolving r-pentomino debris. So it depends.

[knightlife]

Assuming CGOL and randomness per bit (therefore 50% density) I find that the simple population metric is enough to tell the first few generations (even 50 gen) because there is a consistent monotonic decrease in the population with a large enough sample size. The population drops by certain percentage with each generation, ever decreasing past 100 gens and sometimes even 150 gens for a 1000 x 1000 soup. In other words, on gen 1 the population drops dramatically by almost 45% every time, from 500K cells to about 274K cells, then on gen 2 it drops 7% to about 255K cells, and so on. Of course the numbers vary but population numbers are predictable well within 1%, meaning 274K could be 275K or 273K, but plus or minus 1K cells is much less than 1% of the remaining cells. I was surprised how consistent this simple method is for 1000 x 1000. Of course 100 x 100 will be less consistent, I don't know if that is a priority.

By evolving a given pattern (that came from a random soup) say 5 generations and measuring the percentage decrease in population for each step, you could correlate with a chart of the average percentage decreases of a large number of soups of the same size as the soup that generated the given pattern. The generation of gliders at the edges is also a telltale sign of how evolved it is, and could be a pretty good indicator: the census as well as the thickness of the outer glider layer in later generations. The size and number of "solar flares" that project out from the original boundary is another indicator to look at.

I noticed that in gen 1 there are a LOT of single cells that are completely isolated cells that will die and be missing in gen 2, then the number of new single isolated cells will be consistently less until there are very few. The same sort of disproportionate percentage of blocks appear when there is room for them around gens 15-20, decreasing slowly as the number of blinkers and beehives increases and then decreases to a nominal level for a CGOL 50% random soup. The loaf needs even more room and so its census increases then decreases to a nominal level later ("nominal" as in Achim's top-100 frequency table).

These are simple observations, I haven't done definitive statistical tests. It would be interesting to know the statistical probability that you could nail the generation number exactly, even just for the first 20 gens.

At first I wondered why anyone would want to know the generation number of a given evolved random pattern, but I think you may be working on a program to calculate ancestor patterns. Am I right? Or you just like hard puzzles?

[HartmutHolzwart]

I was thinking more about a smaller original probability than 0.5! Then population is not such a differentiator. Also it is important that the field is a torus.

I still want to get a grasp on the notion of "natural" in the sense of typical.

I'm mostly interested in the first 10 generations, because further on, the typical small constellations start to dominate the evolution. So the to speak the opposite end of the sparse universe discussion.

[codeholic]

If you mean Sparse Life, then it would only depend on how lucky you are. Most of the cells in Sparse Life die out in the second generation, pre-block also stabilises on the second one. If I'm not mistaken, the best "methuselah" consisting of 4 cells is the y-pentaplet, which evolves into a traffic light in 10 generations. But if you're lucky enough to get a soup with an r-pentomino or one of its parents or siblings, you'll be able to predict the age of a sparse soup up to 1100+ generations, depending on how big the region you've got is and if it includes gliders flying away from the ash.

[HartmutHolzwart]

As I wrote: I'm mainly interested in the first few generations!

[Extrementhusiast]

What about by blurring the squares something like this?

Code: Select all

11111
12221
12321
12221
11111

...so that the resulting field would be something akin to a Minesweeper field:

Code: Select all

06 06 08 11 12 13 10 07 05 06 10 12 14 15 13 10
08 10 12 14 17 17 15 10 08 09 13 18 18 19 19 14
09 12 13 15 19 21 17 15 14 15 19 21 22 23 21 15
10 11 14 17 19 19 19 17 18 19 21 22 24 25 21 13
09 11 14 18 18 17 19 20 20 21 23 25 26 27 22 14
06 11 15 16 18 18 18 19 20 20 24 25 28 27 23 15
08 13 17 18 19 21 19 18 19 20 21 24 26 26 22 16
10 15 18 19 20 20 20 17 15 16 19 20 21 22 20 15
12 16 19 21 22 23 21 20 17 17 20 19 18 20 18 15
13 17 21 22 22 22 21 21 21 20 18 18 18 19 18 16
11 17 20 21 20 21 21 24 25 23 19 19 19 22 21 17
11 18 22 21 20 21 22 24 24 23 22 21 21 24 21 15
12 17 20 20 19 21 23 24 22 23 23 24 22 22 17 12
12 16 18 19 19 20 21 21 19 19 22 23 20 17 11 07
09 14 16 18 19 18 17 17 15 16 18 19 15 12 07 04
06 09 13 14 14 13 11 11 11 12 13 12 09 07 04 03

Or, if you want to convert it to digits à la hexadecimal:

Code: Select all

668BCDA756ACEFDA
8ACEHHFA89DIIJJE
9CDFJLHFEFJLMNLF
ABEHJJJHIJLMOPLD
9BEIIHJKKLNPQRME
6BFGIIIJKKOPSRNF
8DHIJLJIJKLOQQMG
AFIJKKKHFGJKLMKF
CGJLMNLKHHKJIKIF
DHLMMMLLLKIIIJIG
BHKLKLLOPNJJJMLH
BIMLKLMOONMLLOLF
CHKKJLNOMNNOMMHC
CGIJJKLLJJMNKHB7
9EGIJIHHFGIJFC74
69DEEDBBBCDC9743

I would then say to toss out the first two and last two columns and rows (as those are artificially low, due to the forced zeroes), unless if you are using a torus, and run some statistical tests on the set of the 144 (256 if torus) remaining numbers. Or something like that.

[Scorbie]

I feel that the 'Entropy' decreases and the pattern forms into clusters (which we call methuselahs) as the pattern is generated. Maybe defining the appropriate 'Entropy' function would make a good indicator.

I'm mostly interested in the first 10 generations, because further on, the typical small constellations start to dominate the evolution. So the to speak the opposite end of the sparse universe discussion.

You mean you're interested in some sort of "Dense Life", opposed to "Sparse Life"? That sounds interesting!