CHALLENGE: Find the longest-lived GOL pattern w/ the fewest / most alive cells as its initial state

[hash0]

sparse-dense-challenge.png (157.59 KiB) Viewed 508 times

Rules: Patterns must evolve according to B3/S23 on the 16x16 torus and may not enter into repeat cycles, e.g. Gliders on an otherwise empty torus will be halted once they reach a previously held config and their generations counted.

Here is the current leaderboard: ■ https://lifehashes.net/login/sparse-dense-challenge.php

Use this visualizer that automatically checks all these conditions and allows both binary and RLE input (which it also translates between the two): ■ https://lifehashes.net/fancy-glyphs/

Usually, the sweet spot for density is ~37% for optimal longevity, but I noticed some really interesting Glyphs being registered at our Glyph Registry which evolve from very sparse random soups but attain extremely high generational counts (p324 Agar).

[Vort]

With such rules leaderboard will be dominated by countless variations of P5024.

[hash0]

With such rules leaderboard will be dominated by countless variations of P5024.

I thought about that, too, so I will implement a logic that lets you toggle between Agars and non-Agar patterns (we can easily detect the former because they have the p314/5024 periodicity).

Still interesting to see where the lifespan limit of the Agars lies. If my hypothesis is correct, there should be a "regular" pattern that lives for 2000+ steps which eventually morphs into an Agar, giving rise to ultra-long lived patterns with 7000+ steps. So far, none of those have been found.

*** UPDATE: Toggle switch included

sparse-dense-challenge-toggle.png (12.91 KiB) Viewed 488 times

[Vort]

Here are few observations:

1.

... Usually, the sweet spot for density is ~37% for optimal longevity ...

It is possible to keep optimal density in some places while at the same time having arbitrary density on average:
https://lifehashes.net/login/registry.p ... nse-sparse

2. Exceptionally good results in fact "wipe" all slots with nearby density.
Two examples:
2.1. I found 1623 lifespan 14 population specimen. It means there are no reasons to submit 15+ population results with lower lifespan, because 15 pop for example can be achieved by adding single dot to 14 pop somewhere.
2.2. randomaccxd found 1450 dense with 194 pop. In this case not only 195 pop is trivially achievable, but 193 pop as well.

[hash0]

Right, we had a similar discussion back in February when Vort "hacked" my prize Ignis Draconis pattern with a one-off exploit. I shall implement logic that prevents this kind of copy & paste of existing patterns.

I'll keep you posted - I need to put some thought into it first to implement a watertight but fair logic.

[Vort]

I shall implement logic that prevents this kind of copy & paste of existing patterns.

I think it is not needed: such copy-paste won't be useful when lifespan will be pushed to its limit for each density.
I said about it not because I thought it is something which needs to be prevented.

[Vort]

I decided to publish my OpenCL miner:

TorusLifeCL16_v4.zip

(264.77 KiB) Downloaded 4 times

The reason is simple: I won't be able to properly compete with other people using my 12 year old CPU (despite it having GPU core).
Can anyone test what speeds can this miner achieve with modern GPU?
On GPU cores of my i5-4690 (TorusLifeCL16 gpu), it gets 385 KP/s. On single CPU core (TorusLifeCL16 cpu 25) - 39 KP/s.
This miner has complicated history, so it contains inefficiencies and bugs for sure.
But I think it can be useful anyway (at least it was able to discover 1988 sparse).

[Vort]

@bobinou, whay are you not submitting results from your database?
For example, 2269 lifespan 62 pop.

[hash0]

I think Bobinou got really into this challenge and is currently not replying because he's to busy mining patterns...

[bobinou]

@bobinou, whay are you not submitting results from your database?
For example, 2269 lifespan 62 pop.

Hi there
thats a good point, i will do that! It wont be many patterns though, as the current miner is rolling them in the 25%-75% starting range.
And just noticed the fpga broke down so its not mining any new patterns, great... xd

[bobinou]

On GPU cores of my i5-4690 (TorusLifeCL16 gpu), it gets 385 KP/s. On single CPU core (TorusLifeCL16 cpu 25) - 39 KP/s.

Super cool miner! On my rtx4070 its 17MP/s

[Vort]

... It wont be many patterns though, as the current miner is rolling them in the 25%-75% starting range. ...

It is also possible to upload different phases.
2269 gen 62 pop which I mentioned previously is in fact 2275 gen (or 2274 depending on how you count it) 105 pop advanced by 5 generations.

[hash0]

It is also possible to upload different phases.
2269 gen 62 pop which I mentioned previously is in fact 2275 gen (or 2274 depending on how you count it) 105 pop advanced by 5 generations.

Yes, that is a much harder problem to solve, though. This would - in essence - be tracing "lineages" of patterns, i.e. having different starting configurations that converge at one point or another in their evolution to a common halting state. Not sure how to restrict this, but for now it is absolutely viable!

[Vort]

While playing with this challenge and thinking about "lineages", odd thought came to me:
Looks like, despite having trillions of these 16x16 random soups, not much is really going on there.
There is randomness at the beginning, sure, but then everything converges into several noticeable sequences.
If my guess is right, it means efficient implementation of torus-compatible hash may skip lots of computation once known lineage is detected.
So the idea is: calculate 100-200 generations in a usual way, then start comparing hashes for every 100th generation.
If match is found, then just add precalculated lifespan for that "ending".

[hash0]

Vort, I think you are on to something, but to be honest: I don't know if I am qualified to answer your question there.

At the same time, I think there is actually more out there than just a few noticable patterns we have seen so far. My reasoning goes like this:
When I started exploring the 16x16 torus with browser-based miners, I could not break through the "ceiling" of patterns that live for more than 1,200 generations. Then I pivoted to CPU-based dedicated workers and quickly discovered patterns in the 1,800 range which I could previously not see.

When we then started mining on GPU kernels, we found the Agars with 5,000+ generations - which were utterly inaccessible to us previously.

All this convinces me that there are patterns out there that live for 10,000 steps, maybe 100,000 non-repeating steps - they are just not accessible to our miners because they are so rare.

It's a bit like particle physics where we had to build super-large detectors and accelerators for decades before we could find particles that have been there all along but were invisible to us, like the Higgs boson.

I, for one, think we have barely scratched the surface of what's out there on the 16x16 torus...

[Vort]

There is randomness at the beginning, sure, but then everything converges into several noticeable sequences.
If my guess is right, it means efficient implementation of torus-compatible hash may skip lots of computation once known lineage is detected.

There are several noticeable endings for long-lived patterns, right.
However, during mining, not only long-lived, but also short-lived (and more chaotic) patterns need to be processed.
I looked for endings which allow to save the most amount of computations in such mixed environment and choose 3 patterns.
They allow to skip 43% of calculations in 2.2% of the cases.
However, not only resulting 1% skip is small, but also checking if current generation matches one of these endings takes about the same amount of time, which was planned to be saved.
I don't know if it is possible to improve such result, but if possible, it won't be easy for sure.

Here are these endings with lifespans of 152, 55 and 183, in case anyone is interested:

Code: Select all

x = 4, y = 5, rule = B3/S23:T16,16
2bo$b2o$2obo$bobo$2b2o!

Code: Select all

x = 7, y = 6, rule = B3/S23:T16,16
4bo$4b2o$5b2o$5bo$3obo$3o!

Code: Select all

x = 4, y = 4, rule = B3/S23:T16,16
b2o$2b2o$obo$2o!

[Vort]

... All this convinces me that there are patterns out there that live for 10,000 steps, maybe 100,000 non-repeating steps - they are just not accessible to our miners because they are so rare. ...
... I, for one, think we have barely scratched the surface of what's out there on the 16x16 torus...

It was surprising for me to get 1925 gen result with just 12 population.
In case 2290 gen 51 pop result (nice find by the way) can be moved to lower population zone (even with losing some of its lifespan), it will mean there is kinda free space between that mark and optimal 35% density (90 pop) for undiscovered patterns with higher lifespans.
Whether it is going to be 10k/100k or not can be guessed by extrapolation of low population results.

[hash0]

In case 2290 gen 51 pop result (nice find by the way) can be moved to lower population zone (even with losing some of its lifespan)

I thought about this "truncating" technique and a way to prevent this: The unspoken assumption in all these challenges that I published has always been that we start with a random soup and not from a pattern in the midst of its evolutionary sequence. This intuition is correct, but it is not precise enough: What I actually meant by that is that all of our Glyphs should start from "Garden of Eden" patterns, i.e. configurations that have no pre-image under Conway's rules (B3/S23 in our case).

Hence, I'll look into implementing checks in my code that determine whether a Glyphs starts from GoE or if it has a pre-image. Determining pre-images is, of course, an NP hard problem, but it might just be possible to do this brute force in acceptable time for the 16x16 torus.

[Vort]

What I actually meant by that is that all of our Glyphs should start from "Garden of Eden" patterns, i.e. configurations that have no pre-image under Conway's rules (B3/S23 in our case).

It will make impossible to find pop 1 pattern, because dot has lots of predecessors.
Same is true for domino (pop 2), banana spark (pop 3).

[hash0]

It will make impossible to find pop 1 pattern, because dot has lots of predecessors.
Same is true for domino (pop 2), banana spark (pop 3).

That is true and I have to apply some thought to this because I do not want this to be overly restrictive.

Also, the problem of "toroidal isometries" remains and needs solving, i.e. someone submitting a shifted/mirrored/rotated version of an existing pattern.

[Vort]

Also, the problem of "toroidal isometries" remains and needs solving, i.e. someone submitting a shifted/mirrored/rotated version of an existing pattern.

Not for longevity challenge.
All these variations will have the same lifespan and population.

[hash0]

Not for longevity challenge.
All these variations will have the same lifespan and population.

True, but that is majorly important for the HASHWAR weekly competition because then someone can just copy & paste a successful pattern and submit it into the tournament.

[Vort]

Super cool miner! On my rtx4070 its 17MP/s

Thanks.
I made new version which is 15% faster on my hardware.
Can you check if it works for you and if speed improvements are visible on your hardware as well?

TorusLifeCL16_v14.zip

(264.44 KiB) Downloaded 4 times

It has two main changes compared to previous version:
1. OpenCL core is not reporting states for unfinished computations to CPU anymore;
2. Loop detection is now targeted at periods 6 (3, 2, 1) and 64 (32), which catches 99.9997% of cases.
upd: version with P5024 support is available here.

[Vort]

Turns out, it is possible to have P5024 predecessor, which has less cells (13) than P5024 itself (14).

[bobinou]

I made new version which is 15% faster on my hardware.
Can you check if it works for you and if speed improvements are visible on your hardware as well?

It does work yes! Ive reran the old one then the current version and was able to get a performance increase of 18.75%. Good Job!