soup searching an 8x8 grid

aharbick · 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 · 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.

yujh · 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

aharbick · 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

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.