Can game of life be used as a pseudo random generator ? Maybe so.

After having fun doing bidirectionnal python <=> tk programming I thought that an hexagonal game of life experiment would be a nice way to saturate the PIPE from python to tcl to assert how much load the concept could take.

So I made a game of life with a twist inspired from this article about using strange attractors to qualify randomness.

Conway's game of life is a pretty simple example of cellular automata. The tradition version is on a square grid, here we not only change for an hexagonal grid, we also let users change the rules and we add a feature : we plot in real time a graph with u(n-1) on the x-axis and u(n) on the y-axis every turn and I'll explain why later.

But first let's look at a classical run with the normal rules : it's boring because it converges pretty fast to oscillators.

. But, by tweaking rules, you can have all kind of boring oscillators, patterns that repeat themselves with often a period of only two.

And also configurations for which we cannot tell it they are periodical :

The tool

But actually, let's have a look at the complete interface for playing with hexagonal game of life :

As you can see, you can set the rules for both dead cells that gives birth to new one, or lively cells that spreads. As a result, it becomes interesting to explore when the game of life does not converge.

It has an assymetry due to the coding techniques of python to pure tk for which python output is priorized over tk input, hence the feedback from the pure tk interfaces that may take several full long seconds.

Takens serie usage

Game of life being a deterministic game given a configuration Cn: if we already see it we can assert with certainty what Cn+1 will be. Hence if you plot Cn, Cn1 on respectively the x and y axis you can ascertain that if new points appear in the space phase you have not yet entered a period. It is a pretty darn KISS (Keep it Simple Stupid) method for evaluating not only if we hit a repetition but also biases in the space phase.
As refered at the beginning of this post in lcamtuf post on exploring randomness : a good PRNG (pseudo random number generator) should not only have a very long period it should cover the space phase equiprobably. And you know what tool is very good at seeing non uniformity? Your eyes coupled with your brain.

Spoiler alert : if I show you this : you are gonna tell me : hum ... Why does your space phase tends to looks like sierpinsky triangles?

My greek teacher used to say the pĥilosophs are not the one who gives smart answers but those who asks clever questions. And here you are touching an interesting point. Is the sierpinsky pattern inherent to randomness ? No. Is it inherent to topology ? Maybe. Is hit inherent to the hexagonal variation on the game of life ? Surely. Is it due to the Periodic Condiditions at the Borders ? No (because patterns who don't evolve from configurations touching the borders also have it).

In one simple eye analysis we have an interesting fact : suites of numbers generated by using game of life have a signature in the space phase that reflects the topology (here hexagonal).
Even though it my not be obvious at first sight :

Qualitative analysis of the hexagonal game of life for use as a PRNG

After a little bit of trial and errors we can notice that when we set for either dead or living cells to 3, 4, 5 we have often more long lasting sequences. As you can see there for alive = 4,5,6, dead = 2,3,6, it is also very sensitive to initial conditions making it tougher to analyse by differential analysis.



Even though it seems to do a pretty good job at generating a long list of non repeating numbers, however, as is it as the following problem :

evaluating entropy seeding

Given intial entropy we may enter the following problems :

• Initial configuration may converge fast to a null of full one configuration not evolving anymore
• Can we quantify how much pseudo entropy we generate ?
• How much round of non repeating numbers do we have given a known size of grid and given suitable rules ?
• Which rules generates the maximum chaos ? Are there equivalent sets of rules we can switch too to keep the same entropy level ?
• Real life randomness accepts to repeat preceding seen values, how much the non repetition (sign of a non converging serie) is a weakness ?

Thinking of designing a PRNG based on hexagonal game of life

Real life cryptography have good practices like regenerating an initialization vector every round to avoid leaking information since ... enigma. Here, we could actually use the entropy we generate to alter ever the configuration or the rules in a deterministic way that would actually make the Takens serie cover the full space uniformely showing no sign of priviledging a siperinsky triangle kind of shape.

Actually, Takens series are an helpful tool in determining the quality of randomness so we already have one tool available.

Also, game of life is a fairly easy to code and understand algorihtm, thus, by lowering the entry barrier to coding the chore of the engine we have more eyeballs that can spot bugs and contribute to a better solution.

As they are easy to code, they are also easy to synthethize as an ASIC or FGPA, bringing an easy gain in acceleration by going full hardware with algorithm that being intrinsicly massively parallel will be tougher to brake with thread based computing, and mathematically it's a non linear system for which theory provides fewer tools of analysis.

Talking about FGPA we also can study not only the alteration of configuration but explore the alteration of topology breaking the hexagonal symmetry that may be the root cause of the sirpinksy triangle in the space phase.

I think game of life as a base for a PRNG is a funny topic of hobby research that could empower a lot of amateurs in this field building not only better algorithms but also dispelling myth and obscurantism around this field of computer science.