soup searching an 8x8 grid

For general discussion about Conway's Game of Life.
Post Reply
aharbick
Posts: 5
Joined: December 11th, 2021, 11:19 am

soup searching an 8x8 grid

Post by aharbick » December 11th, 2021, 1:07 pm

tl;dr Is it tractable in terms of compute power and time to exhaustively search for the longest methusaleh/diehard on a finite 8x8 grid?

I have been a bit obsessed with GOL for the past year. Earlier this year I had the idea to build a physical GOL simulator art project with a 3d printer, arduino, and bunch of servos.

Having completed that rig I thought "I wonder what is the most generations for a non-infinite pattern that fits on my 8x8 grid"... So I built a custom searcher and have been evolving that. On my M1 mac with 8 threads I can search over 300k soups per second. I ported my solution to CUDA and spun up an AWS g5.48xlarge (https://aws.amazon.com/ec2/instance-types/g5/) and ran it long enough to see that I could search about 500m soups per second.

Using that setup I've found a pattern that is 199 generations. Here's what it looks like on my art project: https://youtu.be/GUKUeunvB_Y

After trying a bunch of different things to optimize my solution I stepped back computed that it would take 1169+ years (on a machine that costs $16/hr) to finish an exhaustive search. In other words, my solution is 3-4 orders of magnitude too slow.

I've looked at clever optimizations like hashlife, quicklife, etc. But these solutions seem catered towards large patterns across MANY generations and they don't seem as helpful in my case of a VAST NUMBER of small patterns across a small number of generations. I've also considered ways to prune the search space. For example exhaustively computing a sub-grid in all possible positions (e.g. 4x7 grid in all 10 positions on my 8x8 grid could be cached in ~5GB) and using that cache when evaluating states in my 8x8 grid. Or evaluating only one version of a pattern that is rotatable or reflectable on any axis. But these improvements seem like an order of magnitude or less improvement at best.

I would love to know if someone who has thought about this a lot more thinks this is actually a tractable problem (in terms of compute and time), if there are other clever tricks, if I've under estimated the power of some ideas, or if I'm actually just chasing the white whale.

Here's the code that I've been writing: https://github.com/aharbick/conway

Thanks for your thoughts!

hotdogPi
Posts: 941
Joined: August 12th, 2020, 8:22 pm

Re: soup searching an 8x8 grid

Post by hotdogPi » December 11th, 2021, 1:30 pm

Make sure you keep track of other things, too. Rob's p16 is 8×9 and was discovered via soup search.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉟,㊱,㊳S,㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,70,72,74S,75,76S,80,84,90,96,100,102S,108,110,114G,116,117G,120,126G,128S,138,147,154,156,196S,217,486,576

S: SKOP
G: gun

User avatar
yujh
Posts: 2863
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: soup searching an 8x8 grid

Post by yujh » December 11th, 2021, 1:55 pm

hotdogPi wrote:
December 11th, 2021, 1:30 pm
Make sure you keep track of other things, too. Rob's p16 is 8×9 and was discovered via soup search.
There is a catagolue census for 8x8, I’m sure. If not I can just produce it
Nothing to apgsearch? Try b38s23/C1!

B34kz5e7c8/S23-a4ityz5k!!!

b2n3-q5y6cn7s23-k4c8

B3-kq6cn8/S2-i3-a4ciyz8

B3-kq4z5e7c8/S2-ci3-a4ciq5ek6eik7

Rule modifier

If you need someone to apgsearch, or if you want to search for an explosive rule, contact me on discord!

Bored of Conway's Game of Life? Try Pedestrian Life -- not pedestrian at all!

aharbick
Posts: 5
Joined: December 11th, 2021, 11:19 am

Re: soup searching an 8x8 grid

Post by aharbick » December 11th, 2021, 3:07 pm

There does seem to be this: https://catagolue.hatsya.com/census/b3s23/8x8

But it doesn't seem to be possible to show only bounded 8x8 grids. I'm not sure how to call what I'm trying to do, but Golly seems to call them "planes" http://golly.sourceforge.net/Help/bounded.html and in my case it would be :P8,8.

Also if I'm reading it correctly that catalog isn't complete as it seems to have only searched ~500m soups.

Perhaps there is some other place to look?

Thanks!
Andy

User avatar
dvgrn
Moderator
Posts: 8931
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: soup searching an 8x8 grid

Post by dvgrn » December 11th, 2021, 4:04 pm

I don't think :P8,8 has gotten much of any attention anywhere, no. So much of the space in an 8x8 grid is taken up by weird "boundary effects", objects that can only exist in that particular space -- like, I don't know, things like this but even more specific to being stuck in a universe corner or maybe an 18x18 agar with empty gutters between mirrored 8x8 chunks.

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
2$4b3o2$2bo4bo$2bo4bo$2bo4bo$4b3o!
#C [[ AUTOSTART GPS 3 THUMBNAIL THUMBSIZE 3 ]]
With :T8,8 the stabilizations would be somewhat more transferrable to a larger universe, though again the most interesting stuff might be the agars, espcially in cases where it turns out they can be supported somehow without the infinite repetition.

I thought I remembered Mike Playle doing some searches for asymmetrical agars on toruses, I forget what size, with some interesting higher-period results. All I can find on a search is these two posts. Was that someone else who did those searches, or am I somehow missing the relevant posts?

aharbick
Posts: 5
Joined: December 11th, 2021, 11:19 am

Re: soup searching an 8x8 grid

Post by aharbick » December 11th, 2021, 4:39 pm

I'm not surprised that my particular problem hasn't gotten much/any attention. Frankly I'm amazed at how much thought an effort has gone into all of the myriad other things in this world :D

I really am interested in the P:8,8 driven mostly because of my art project, but also because it's just so fascinating to me conceive of it as a little habitat and wonder how long it can sustain active life.

With the code that I've already done I've found a bunch of interesting patterns... There are thousands of patterns that are active for 100+ generations. I've only found a handful greater than 190. I plotted a histogram of 10m random patterns.
Screen Shot 2021-12-11 at 3.36.48 PM.png
Screen Shot 2021-12-11 at 3.36.48 PM.png (110.53 KiB) Viewed 1205 times
Really makes me want to know how far that long tail extends to the right. But given the computational complexity the huge solution space of even a very small 8x8 world it seems like objectively knowing the answer isn't likely.

User avatar
GUYTU6J
Posts: 1850
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: soup searching an 8x8 grid

Post by GUYTU6J » December 11th, 2021, 10:33 pm

aharbick wrote:
December 11th, 2021, 4:39 pm
I really am interested in the P:8,8 driven mostly because of my art project, but also because it's just so fascinating to me conceive of it as a little habitat and wonder how long it can sustain active life.

With the code that I've already done I've found a bunch of interesting patterns...
Can you share their RLE codes? Draw in Golly, select the pattern with selection tool or crtl+A and copy with ctrl+C, to get the pattern RLE. On the forums, surround the RLE with code tags, which is the fifth button labelled </> above the input box, and then everyone can view these patterns as well.
dvgrn wrote:
December 11th, 2021, 4:04 pm
I don't think :P8,8 has gotten much of any attention anywhere, no. So much of the space in an 8x8 grid is taken up by weird "boundary effects", objects that can only exist in that particular space -- like, I don't know, things like this but even more specific to being stuck in a universe corner or maybe an 18x18 agar with empty gutters between mirrored 8x8 chunks.

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
2$4b3o2$2bo4bo$2bo4bo$2bo4bo$4b3o!
#C [[ AUTOSTART GPS 3 THUMBNAIL THUMBSIZE 3 ]]
...
Isn't the agar-with-gutter 17×17?

Meanwhile, there is another perspective for these CGoL patterns restricted by boundary. There are far more types of boundaries regarding how they affect evolution, as can be shown with the extra states of StateInvestigator. "Plane" in Golly has peripheral eternal OFF cells, which is state 5:

Code: Select all

x = 10, y = 10, rule = StateInvestigator
10E$E8.E$E8.E$E4.3A.E$E8.E$E2.A4.AE$E2.A4.AE$E2.A4.AE$E4.3A.E$10E!
But why not eternal ON cells? That is state 4:

Code: Select all

x = 12, y = 12, rule = StateInvestigator
12E$E10DE$ED8.DE$ED8.DE$ED8.DE$ED8.DE$ED8.DE$ED8.DE$ED8.DE$ED8.DE$E
10DE$12E!
State 8 and 9 turn on all adjacent off cells regardless of their neighbour counts, but state 8 is treated as eternal ON and state 9 is treated as eternal OFF:

Code: Select all

x = 12, y = 12, rule = StateInvestigator
12E$E10HE$EH8.HE$EH8.HE$EH8.HE$EH8.HE$EH8.HE$EH8.HE$EH8.HE$EH8.HE$E
10HE$12E!

Code: Select all

x = 12, y = 12, rule = StateInvestigator
12E$E10IE$EI8.IE$EI8.IE$EI8.IE$EI8.IE$EI8.IE$EI8.IE$EI8.IE$EI8.IE$E
10IE$12E!
There is also a state 14 that always inverts neighbouring cells:

Code: Select all

x = 12, y = 12, rule = StateInvestigator
12E$E10NE$EN2.A5.NE$EN8.NE$EN8.NE$EN8.NE$EN8.NE$EN8.NE$EN8.NE$EN4.2A
2.NE$E10NE$12E!
So what do all of the above exotic examples tell us? Well, these beyond-B3/S23-transition-rule boundaries (more or less including torus/cylinder) are highly artificial and restrictive, making the results hardly applicable in further constructions at larger scale. Looks like this accounts for why there has not been much interest among Life enthusiasts, let alone surviving records.
Why do most natural OCA rules tend to get a diminishing span of interest and go into oblivion, like a lost civilization leaving little records for its beauty and power?

I have been focusing on this rule, now in industrial era:

熠熠种花 - Glimmering Garden

User avatar
dvgrn
Moderator
Posts: 8931
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: soup searching an 8x8 grid

Post by dvgrn » December 11th, 2021, 11:46 pm

GUYTU6J wrote:
December 11th, 2021, 10:33 pm
Isn't the agar-with-gutter 17×17?
Well, sure, in a way, but that still means it's an 18x18 agar:

Code: Select all

x = 18, y = 18, rule = LifeHistory:T18,18
4C9.4C$C2.C9.C2.C$C15.C$2C13.2C$6.2C.2C$7.C.C$4.C2.C.C2.C$4.4C.4C2$4.
4C.4C$4.C2.C.C2.C$7.C.C$6.2C.2C$2C13.2C$C15.C$C2.C9.C2.C$4C9.4C!
EDIT: It would be P17,17, for sure, but it doesn't really make a workable infinite agar unless you add another set of gutters.

MikeP
Posts: 105
Joined: February 7th, 2010, 9:51 am
Location: Ely, Cambridgeshire, UK

Re: soup searching an 8x8 grid

Post by MikeP » December 11th, 2021, 11:59 pm

dvgrn wrote:
December 11th, 2021, 4:04 pm
I thought I remembered Mike Playle doing some searches for asymmetrical agars on toruses, I forget what size, with some interesting higher-period results. All I can find on a search is these two posts. Was that someone else who did those searches, or am I somehow missing the relevant posts?
Yes, that was me. The results are on the Soup Search Results thread; the first one is here.

aharbick
Posts: 5
Joined: December 11th, 2021, 11:19 am

Re: soup searching an 8x8 grid

Post by aharbick » December 12th, 2021, 1:39 pm

GUYTU6J wrote:
December 11th, 2021, 10:33 pm
aharbick wrote:
December 11th, 2021, 4:39 pm
With the code that I've already done I've found a bunch of interesting patterns...
Can you share their RLE codes? ...
Here are some of the patterns with 100 or more generations that die out or end in a stable form...

111 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
obbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$booooooo$bobboboo!
116 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbboo$oooboobo$boboobbb!
125 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbooo$boooboob$bbboobob!
129 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbooob$oooboooo$obbbbobo!
131 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbboooob$ooooobob$bbbbooob!
136 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bboboooo$oobbbooo$bobobbbb!
144 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$boboooob$booboboo$bbobbobo!
145 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bboobbob$obobobbb$oobbbooo$oobobbbo$bbbobobb$bobobbob$obobbbbb$ooobbboo!
147 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bboobobo$oobbbboo$boobbobb$bbbbbbbo$oobbooob$obobooob$bbooooob$booobbbb!
151 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
oobbooob$oboooobb$bobboobb$obbobbbo$oboobbbb$obbbobbb$ooobbbbb$bbbobobo!
166 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbbobbob$obbobobb$oobobboo$oboobbob$obbooooo$obooobob$bobboboo$oboooobo!
167 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bboobbbo$boobbobb$bboooboo$obobobbo$boobooob$obobbbbo$bobobbbo$bobobbbo!
185 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
ooobbobb$boobobbo$oobbboob$boobboob$booboobo$bbobooob$obbobbob$obbobboo!
185 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
oobbboob$bboboobo$ooooobob$obbbbboo$bbooobob$obbobbob$ooboobbb$booooobb!
186 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bobbbboo$oooooobo$booobboo$oobbbboo$boobooob$obbobooo$bbbobobb$oobooboo!
188 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
ooboobob$bboboobo$obobbobb$obbooooo$obobobbo$oobobobo$bbbbobob$booobboo!
190 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
booooobo$bobobbob$ooobooob$obbbbooo$bobbobbo$oboobboo$boobobob$bbbbobbb!
191 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
ooobbooo$booooboo$obobbbbb$boobboob$bobooboo$bbbbbobo$bbobobob$boboboob!
192 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
obbobbob$obbbobbb$bbbobooo$boobobbb$bbbboooo$boboobbo$oobobbbb$bboboobo!
192 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbbbooob$oboooboo$bobobbbo$bbbobboo$bobboobb$bobbboob$oobbobbb$obobbboo!
193 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
oboboobo$obbooobo$bbooobob$ooboobbo$bbbbobbo$bobobobo$bbooboob$bobbbobb!
197 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbbbbbbo$bbobbobo$booobbbo$ooobbbbo$oboobbob$oboobobb$obobobbo$oobobboo!
199 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bboboobb$oobbbbob$obobbbbb$bobbbobb$obobobbo$boobobbo$bbbooooo$oobboobb!
199 generations

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
bbooobbo$bbooobob$bbobbobb$boboboob$oobbbbbo$bbboobob$bbboobbo$obbbobob!

aharbick
Posts: 5
Joined: December 11th, 2021, 11:19 am

Re: soup searching an 8x8 grid

Post by aharbick » January 24th, 2022, 2:36 pm

I got a lot of help from Adam Goucher to move the answer to this question forward. The current code (https://github.com/aharbick/conway/tree ... nd-optimal) running on an AWS g5.48xlarge could hypothetically explore all possible solutions in 10.5 years. I have additional suggestions from Adam to explore that could potentially further reduce that to 1.3 years. So I guess that is to say that the simplest answer to my question of whether it is tractable to exhaustively search an 8x8 grid is kinda :lol:

That said in my explorations I did find a new longest pattern on an 8x8 grid at 209 generations:

Code: Select all

x = 8, y = 8, rule = B3/S23:P8,8
o7b$o2bo2b2o$o2bobo2b$2bo3b2o$o5bob$b2ob2obo$o3b4o$2o2bobob!

Post Reply