soup searching an 8x8 grid

[aharbick]

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]

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

[yujh]

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]

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

[dvgrn]

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]

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

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 (110.53 KiB) Viewed 9034 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.

[GUYTU6J]

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.

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.

[dvgrn]

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]

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]

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]

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

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!

[pipsqueek]

you could search all possible 8x8 grids, but there are 18,446,744,073,709,551,616 (2^64) distinct 8x8 patterns. but that also considers rotation and reflection, so not including rotations there are 890,174,523,998 8x8 grids. the actual number is hard to calculate because of rotationally symmetric patterns (so the actual number is larger) but it probably would be big enough to need a lot of time and effort

[dvgrn]

... not including rotations there are 890,174,523,998 8x8 grids. the actual number is hard to calculate because of rotationally symmetric patterns ...

There's something terribly wrong with that second number. It's too small by quite a few orders of magnitude.

The actual number is not all that hard to calculate, thanks to the lemma that is not Burnside's (Wikipedia link). I just read through it and thought that I didn't understand it, but then I did! -- the example involving coloring a cube with three colors was hugely helpful.

(Usually I find mathematical definitions on Wikipedia to be completely opaque -- like, if you read the Wikipedia article on "affine transformation", you'd pretty much never know that they're really just talking about high-school-level math at best, two sets of three equations with three unknowns -- new x = Ax+By+C, new y = Dx+Ey+F. But the example in the Burnside's Lemma article makes the usual abstract treatment a lot more workable.)

So the article says things like

"six 90-degree face rotations, each of which leaves 3^3 of the elements of X unchanged"

... and once you understand why it's exactly 3^3 elements of X that are unchanged -- basically a band of four faces around the middle of the cube have to be all one color, but it can be any of the three colors -- then ... it's not too terribly painful to see how to apply the lemma to the eight transformations of an 8x8 grid.

EDIT: On a first wrong attempt I'm getting 9223372036988993536 = 2^63 + 2^27

or more specifically 1/8 of (1* 2^64 + 4*2^36 + 3*2^64), representing the 1 identity transformation, the 4 reflections, and the 3 rotations.

-- But I feel like that's probably wrong, because I'm not seeing yet how that 3 would divide out to give an integer result for odd-sized squares.

-- Oops, no, I did do it wrong. Hang on a minute. Can't lump the two 90-degree rotations together with the 180-degree rotation, and 2^64 is totally the wrong thing to multiply by anyway. I had that part backwards. Trying again:

3x3:

1/8 of (1* 2^9 + 4*2^6 + 2*2^3 + 1*2^5) for 1 identity, 4 reflections, 2 90-degree rotations, and 1 180-degree rotation. That makes 102, which makes sense.

Furthermore, now that I have that third term, I can look up "2, 6, 102" in the OEIS (this is a very, very useful trick for the mathematically semi-competent) and get the whole story. For 8x8 the correct number is

2,305,843,028,004,192,256

And I can get that number by doing

1/8 of (1* 2^64 + 2*2^32 + 2*2^36 + 2*2^16 + 1*2^32)

First term: identity -- free choice of all 64 bits, this transformation leaves the pattern unchanged in all cases
Second term: axial reflection -- free choice of 32 cells, which is everything on one side of the line of reflection, the others are forced
Third term: diagonal reflection -- free choice of 36 cells, everything on one side of and including the line of reflection. the others are forced
Fourth term: 90-degree reflection -- free choice of 4x4 = 16 cells, the others are forced
Fifth term: 180-degree reflection -- free choice of 8x4 = 32 cells, the others are forced

[pzq_alex]

I'm getting (2^64+2*2^16+2^32+2*2^32+2*2^36)/8 -- one identity, two 90-degree rotations, one 180-degree rotation, two axial reflections, two diagonal reflections. (These are the elements of D_4 grouped by conjugacy classes. )

Usually taking the leading term (identity) gives a good estimate: 2^64/8. The rest of the terms are usually orders of magnitudes smaller.

[dvgrn]

I'm getting (2^64+2*2^16+2^32+2*2^32+2*2^36)/8 -- one identity, two 90-degree rotations, one 180-degree rotation, two axial reflections, two diagonal reflections. (These are the elements of D_4 grouped by conjugacy classes. )

Usually taking the leading term (identity) gives a good estimate: 2^64/8. The rest of the terms are usually orders of magnitudes smaller.

Yup, you got it. I just figured out my last mistake, which was that for even-width squares, I can't lump in the axial reflections with the diagonal reflections -- for the 8x8 case, axial reflections have a free choice of 32 cells, but diagonal reflections have a free choice of 36 cells. For something like 7x7, they could be lumped together because all axes of reflection go through the center of a line of cells.

Side note on what this means on the size of the Exhaustive Testing of All 8x8-Torus Soups Problem: With 2305843028004192256 patterns to test, if we tested one trillion per second (which is a bit of a tall order!) we could be done in 2305843028004192256/1000000000000/365.25/24/60/60 = a little over 73 years.

[dvgrn]

Side note on what this means on the size of the Exhaustive Testing of All 8x8-Torus Soups Problem: With 2305843028004192256 patterns to test, if we tested one trillion per second (which is a bit of a tall order!) we could be done in 2305843028004192256/1000000000000/365.25/24/60/60 = a little over 73 years.

Oops, just remembered: if we're running these on a torus, that means there are more transformations to account for.

I think there will be 2305843028004192256/64 = 36028797312565504 equivalence classes with 64 soups in each class. Did I get that right on the first try, or no?

That means if we can test a little more than a trillion soups per second, we could be done in a year.

[pzq_alex]

I think there will be 2305843028004192256/64 = 36028797312565504 equivalence classes with 64 soups in each class. Did I get that right on the first try, or no?

Not exactly, but close enough (the errors are negligible relative to the size of the number). Usually the full power of Burnside's lemma is not actually needed unless you desperately need the exact number somehow.

[apg]

The last e-mail I sent to Andrew contained a discussion about how to do most symmetry deduplication within the framework of his CUDA approach:

As for taking advantage of rotations/reflections, we'll define a 'frame' to be one of the 2^24 ways to assign 0s and 1s to the following 24 cells marked 'F' in the 8x8 grid below:

FFFooFFF
FFooooFF
FooooooF
oooooooo
oooooooo
FooooooF
FFooooFF
FFFooFFF

Whilst there are 2^24 different frames in total, you can deduplicate the ones that are rotations/reflections of each other -- let's say by only considering those that are lexicographically minimal amongst all rotations/reflections. That should reduce the total number of frames to consider to 2102800 (slightly more than 2^21).

The idea is to split the search into 2102800 tasks, one for each distinct frame, and then (within each task) brute-force the 2^40 different ways to assign 0s and 1s to the 40 cells in the octagon marked 'o'.

There will still be a few patterns that we 'overcount' in multiple orientations, specifically certain patterns with symmetrical frames, but they constitute such a small proportion of the overall set of patterns that it's not worth any further optimisation.

In particular, here are the numbers of patterns that you'd need to search with each of:

no deduplication: 18446744073709551616 (= 2^64)
frame deduplication: 2312053050887372800
full deduplication: 2305843028004192256

That is to say, full deduplication would only reduce the number of patterns to search by a further 0.3% (beyond frame deduplication), but it's a lot more effort to implement than frame deduplication so it's not worthwhile. Frame deduplication has already reduced our workload by a factor of 7.9785.

Anyway, 2^40 (the number of patterns per task) is quite a big number, so we'll split it as follows:

(2^4 kernel invocations per task) * (2^10 blocks per kernel) * (2^10 threads per block) * (2^16 patterns per thread)

in specifically the following way:

FFFKKFFF
FFBBBBFF
FBBBBBBF
PPPPPPPP
PPPPPPPP
FTTTTTTF
FFTTTTFF
FFFKKFFF

(Note that this enumeration strategy enforces the <<<1024, 1024>>> kernel parameters that you were using before; you can no longer adjust blockDim.x and gridDim.x.)

The important property is that the 16 bits corresponding to the 'patterns per thread' occupy 16 consecutive bits in the 64-bit word, so you can advance to the next pattern using a single addition instruction:

pattern += 0x1000000;

To determine your thread's starting pattern, you'll need to define your evaluateRange to accept a single 64-bit integer 'kernel_id' of the following shape, containing both the frame bits and the kernel bits:

FFFKKFFF
FF0000FF
F000000F
00000000
00000000
F000000F
FF0000FF
FFFKKFFF

In other words, you'll have something like this in your host code which launches the 16 kernels for a given task:

for (int i = 0; i < 16; i++) {

ulong64 kernel_id = frame; // this contains the 24 'F' bits
kernel_id += ((ulong64) (i & 3)) << 3; // set the lower pair of 'K' bits
kernel_id += ((ulong64) (i >> 2)) << 59; // set the upper pair of 'K' bits
evaluateRange<<<1024, 1024>>>(kernel_id, other_parameters);

}

(Each loop iteration processes 2^36 patterns, for a total of 2^40.)

Then, at the beginning of your evaluateRange kernel you can incorporate the thread and block bits into the starting pattern:

ulong64 startingPattern = kernel_id;
startingPattern += ((ulong64) (threadIdx.x & 15)) << 10; // set the lower row of 4 'T' bits
startingPattern += ((ulong64) (threadIdx.x >> 4)) << 17; // set the upper row of 6 'T' bits
startingPattern += ((ulong64) (blockIdx.x & 63)) << 41; // set the lower row of 6 'B' bits
startingPattern += ((ulong64) (blockIdx.x >> 6)) << 50; // set the upper row of 4 'B' bits
ulong64 endAt = startingPattern + 0x10000000000ull;

By counting from startingPattern to endAt (excluding the latter endpoint) in increments of 0x1000000 (2^24), you'll iterate over the 2^16 different choices of the middle 16 bits whilst holding the other 48 bits constant.

Very importantly, your main loop condition needs to be:

while (pattern != endAt)

and not:

while (pattern < endAt)

because the following assignment can overflow the 64-bit integer (wrapping round modulo 2^64), thereby causing endAt to be numerically less than startingPattern:

ulong64 endAt = startingPattern + 0x10000000000ull;

Using this technique applied to the final version of the code that we optimised together (by a factor of 100x, from ~500M soups/sec to ~56G soups/sec) it would take 10.4 GPU-years, or 1.3 years on an 8-GPU machine.

10.4 GPU-years is still a vast amount of computation: it's slightly more than Rob Liston (6 GPU-years) and OpenScienceGrid (3 GPU-years) combined.

[apchrkey]

10.4 GPU-years is still a vast amount of computation: it's slightly more than Rob Liston (6 GPU-years) and OpenScienceGrid (3 GPU-years) combined.

It's really not that much. With a couple hundred thousand dollars you could probably rent something to do all of it in less than a few days. With a months worth of federal budget you can do it in a couple minutes.

[aharbick]

After a couple years away I was able to return to this problem and have made a bunch of improvements in code quality, build tooling, tests, performance, and progress-tracking/restartability here https://github.com/aharbick/conway (see the find-optimal subdirectory)

I've got a long running systematic search reporting results to this google sheet: https://docs.google.com/spreadsheets/d/ ... sp=sharing

Before I kicked off the systematic search I randomly stumbled into my current longest pattern; 213 generations:

Code: Select all

#CXRLE Pos=-4,-4
x = 8, y = 8, rule = B3/S23:P8,8
3bo2b2o$5o2bo$5bo$bobo$2o3bo$3o2bobo$5obo$

b2obo2bo!

My recent work has been done on a 5090 laptop edition with ~10k CUDA cores. I implemented the algorithm to eliminate rotations and reflections to reduce the search space to 2^61 (that Adam Goucher detailed in above). I was getting performance of about 5B soups/sec which would take about 14.5 years in my laptop.

The next idea that I played with was precomputing all possible 7x7 soups and using a cache to short-circuit the need to fully compute all generations of a given starting pattern. The idea and algorithm are detailed here: https://github.com/aharbick/conway/blob ... ubgrid.cpp

I computed the 7x7 cache, built an efficient hashtable and integrated the subgrid short-cutting into the core algorithm. With those changes I'm currently able to process 7.5-8.5B soups/sec on my laptop alone. At that rate I should be finished in about 9 years lol. I tried the same code/algorithm on an on-demand H100 from Lamda Labs and saw performance of about 11B soups/sec (but at a cost of $2.50/hour so not worth it). I may upgrade to a 5090 desktop (~$5k) which should double my performance and make the project finishable in less than 5 years.

If anyone has ideas for further performance improvements OR if you want to donate your 5090 cycles hit me up

[vilc]

If anyone has ideas for further performance improvements OR if you want to donate your 5090 cycles hit me up

An idea that seems to have some potential (with many possible variants) is to use the fact that Life is not reversible, meaning that the set of patterns that can arise after one generation is much smaller than the set of all patterns.

Take this partial pattern, where blue cells are set as off, the green cell is on and red cells are unset.

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
A2B5D$3B5D$2B6D$8D$8D$8D$8D$8D!

Whatever you put in the red zone, after one generation it will be the same as if you had started with this pattern :

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
3B5D$3B5D$2B6D$8D$8D$8D$8D$8D!

This can work anytime the state of a cell is irrelevant to the rest of the evolution of the pattern. Solely with the case above, you can save about 1/64th of the total computing time. It might be worthwhile to make an exhaustive search for similar cases for cells in the corners or on the borders, where there are less constraints.

By the way, up in this thread apg mentionned a 56B soups/s performance. Why this discrepancy? Was it on a multi-GPU machine?

There have been discussions on a similar subject but for tori instead of planes last year : see this thread viewtopic.php?f=2&t=6506. In particular, in this post of mine I presented some exhaustive searches, which I conducted on one CPU in about 12 hours (if I remember correcly) but for a 6x6 torus. I was searching at about 1M patterns/s with a very naive algorithm, nowhere near the performance of your optimised GPU algorithm. I you can give it a try, I would be very interested in knowing the maximum lifespan on a 7x7 torus, or even on an 8x8 one. It seems more tractable to run exhaustive searches on tori since they have translation symmetries which vastly reduce the search space.

Edit:
I wrote a quick script to generalise my idea on all 3x3 squares in the upper left corner. The same trick works for 18 of 256 (barring bugs) possible arrangements.

Code: Select all

o..
...
...

 
o..
o..
...


o..
...
o..


oo.
...
...


o..
.o.
...


oo.
oo.
...


o..
...
.o.


oo.
oo.
oo.


o.o
...
...


o..
..o
...


ooo
ooo
...


ooo
ooo
oo.


o..
...
..o


o..
o..
ooo


oo.
oo.
ooo


ooo
..o
..o


ooo
ooo
..o


ooo
ooo
ooo

That's 512-18 = 494 corners to be searched. Without taking symmetries into account, if this reduction is applied on every corner the size of the search space is reduced by a factor of (512/494)^4 = 1.15 (probably less interesting with symmetries, but still worth considering).

Edit 2:
Testing this idea with the 3x8 upper box, looking at changes of the top line which do not affect the first generation there are (barring bugs) only 11,510,370 patterns which produce a distinct output among all 16,777,216 = 2^24, a reduction of the search space by a factor of 1.46, or 2.12 if applied on top and bottom (again, without symmetries).

Edit 3:
I think that I found a variant of the above idea which could reduce the search space by a factor of 14. The splitting that I will present is probably not as well suited for GPUs as apg's design, but perhaps it can be refined.

The first level of iteration is over the middle 4x4 block. After symmetry deduplication, there should be about 2^13 such blocks.
Then iterate over the side 2x4 blocks, again removing symmetrics if needed. This should produce about 2^29 middle 8x4 blocks.

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
8B$8B$8D$8D$8D$8D$8B$8B!

For each 8x4 block, compute separatedly the possible missing 2x8 blocks. Specifically, we want every possible 2-generations outcome for the upper rows to occur exactly once, which requires running each of 2^16 patterns for 2 generations and comparing the 4 top rows for equality. This way we are ensured to iterate over all unique patterns after 2 generations, since there is no interaction with the bottom rows until generation 3. The 4 rows obtained can be kept in two lists, one for the top and one for the bottom, which can then be recombine to form all licit 2-generations pattern. According to statistics that I collected over 10000 starting blocks, only one in 3.8 (or about 17000) of all possibilities are expected to produce a different 2-generations upper-half, or 17000^2 ~ 300M possibilities in total for each block. This makes a total of about 1.6*10^17 patterns to try.
At 10B soups/s, this would reduce the search time to about 185 days. Can someone confirm my logic?

[aharbick]

Thanks for the ideas!

1. Yes the 56B soups/sec is with multiple (8) GPUs. See: https://github.com/aharbick/conway/blob ... ORMANCE.md
(I've been a little all over the place with testing performance because I've been trying on lots of different virtualized or physical hardware... I started off testing on a Jetson Nano 2GB)

2. I made my GPU code work with toruses: https://github.com/aharbick/conway/comm ... 2d4f7880dd and I could generate the "subgrid cache" in what looks to be about 40 days (on my 5090 laptop)

Code: Select all

aharbick@Conway:~/conway/find-optimal$ ./build/find-optimal-torus --compute-subgrid-cache /var/tmp/data.json
CUDA devices available: 1
Using 1 GPU with blockSize=1024, threadsPerBlock=1024
Topology: Torus (wrapping boundaries)
Request queue with directory ""./request-queue"" started processing
Computing 7x7 subgrid cache...
Total 7x7 patterns to process: 562949953421312
Output file: /var/tmp/data.json
Minimum generations to save: 220

Threads per invocation: 1048576
Patterns per invocation: 68719476736
Total batches: 8192

batch=1, range=0 - 68719476736, candidates=7904756, patternsPerSec=172338394, progress=0.01%, estimatedDaysRemaining=37.8
batch=2, range=68719476736 - 137438953472, candidates=16224548, patternsPerSec=172219046, progress=0.02%, estimatedDaysRemaining=37.8
batch=3, range=137438953472 - 206158430208, candidates=24410008, patternsPerSec=168549304, progress=0.04%, estimatedDaysRemaining=38.6
batch=4, range=206158430208 - 274877906944, candidates=33067740, patternsPerSec=163797699, progress=0.05%, estimatedDaysRemaining=39.8

BUT... that's not really what I think you were aiming at with your 7x7 optimality question. Because my cache simulates the four 7x7 subgrids on an 8x8 grid. The longest one in the batches above was this (345 generations):

Code: Select all

#CXRLE Pos=-3,-3
x = 7, y = 6, rule = B3/S23:T8,8
6o$b3ob2o$bobo2bo$obo$obobobo$o!

However that pattern on a 7x7 grid only lasts 24 generations.

Code: Select all

#CXRLE Pos=-3,-3
x = 7, y = 6, rule = B3/S23:T7,7
6o$b3ob2o$bobo2bo$obo$obobobo$o!

I will see what it takes to further modify my code to just simulate 7x7 patterns on a 7x7 grid. Given my experience with the four 7x7 on an 8x8 grid it should be 4x faster to compute and take 1-2days.

3. I need to think harder about your idea for space reduction lol. I haven't wrapped my head around it yet and/or how to implement it.

[vilc]

3. I need to think harder about your idea for space reduction lol. I haven't wrapped my head around it yet and/or how to implement it.

Perhaps it will be clearer with an example. Given the following 8x4 block :

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC!

We first look through the 2^16 possibilities for filling the upper two strips. Some of these will produce an identical result after one or two generations (one in this simple example).

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
BA6B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC!

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2BA5B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC!

We do the same for the bottom strips. Again, there will be some duplicates.

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$2BABA3B!

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$5BABA!

Now, since in Life causality cannot propagate faster than at one cell per generation (the so-called "speed of light"), any combination of two of the above patterns will produce the same outcome after one generation (we could allow for two generations since the two movable regions are four cells apart).

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
BA6B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$2BABA3B!

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2BA5B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$2BABA3B!

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
2BA5B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$5BABA!

Code: Select all

x = 8, y = 8, rule = LifeHistory:P8,8
BA6B$8B$D2C3DCD$DCDCDCDC$4DC2DC$2DCD2CDC$8B$5BABA!

Since we are studying the long-term fate of these patterns, the four soups obtained here are essentially duplicates. So when we look for our upper two strips, we want to keep only one pattern for each possible resulting upper four strips after 2 generations (since only those strips can be affected by our choice given the fact that the middle strips are fixed). The upper strips are causally independant from the bottom strips during the first two generations, so we can perform a separate search for the possible bottom two strips.

This preprocessing step should have a marginal cost and could perhaps be carried on by a CPU (with two threads ideally). When we are done with it, we obtain two lists of possible upper and lower strips (of length 17000 each on average). The core of the computation is to run through all the ~17000^2 elements of the cartesian product, with all patterns obtained after two generations guaranteed to be unique. That should be about 300M patterns instead of 4200M, if I got my testing right.

[aharbick]

Thanks for the details! I'll see if I can improve performance with the ideas.

I got the 7x7 toroidal simulation working. It's not as efficient as the 8x8 version because it has to pack/unpack the 7x7 grid to by byte-aligned so that it works with the Rokicki algorithm.

Here's some sample output:

Code: Select all

timestamp=1764574630, rangeStart=124554051584, rangeEnd=128849018880, bestGenerations=221, bestPattern=126886212025, bestPatternBin=0000000000001110110001011000000011111000110111001, patternsPerSec=1216738449, progress=0.02%
timestamp=1764574634, rangeStart=128849018880, rangeEnd=133143986176, bestGenerations=220, bestPattern=132639362758, bestPatternBin=0000000000001111011100001111011000000111011000110, patternsPerSec=1223207076, progress=0.02%
timestamp=1764574637, rangeStart=133143986176, rangeEnd=137438953472, bestGenerations=219, bestPattern=134508332759, bestPatternBin=0000000000001111101010001010100100100011011010111, patternsPerSec=1230489038, progress=0.02%
timestamp=1764574641, rangeStart=137438953472, rangeEnd=141733920768, bestGenerations=216, bestPattern=141215515804, bestPatternBin=0000000000010000011100001000110011100010010011100, patternsPerSec=1199059704, progress=0.03%
timestamp=1764574645, rangeStart=141733920768, rangeEnd=146028888064, bestGenerations=215, bestPattern=145297528810, bestPatternBin=0000000000010000111010100011010000101011111101010, patternsPerSec=1204162465, progress=0.03%
timestamp=1764574648, rangeStart=146028888064, rangeEnd=150323855360, bestGenerations=221, bestPattern=150181582579, bestPatternBin=0000000000010001011110111100001010001011011110011, patternsPerSec=1230187990, progress=0.03%
timestamp=1764574652, rangeStart=150323855360, rangeEnd=154618822656, bestGenerations=216, bestPattern=151079909116, bestPatternBin=0000000000010001100101101000100000111011011111100, patternsPerSec=1213615344, progress=0.03%
timestamp=1764574655, rangeStart=154618822656, rangeEnd=158913789952, bestGenerations=216, bestPattern=158394336476, bestPatternBin=0000000000010010011100001000010011100010011011100, patternsPerSec=1217677581, progress=0.03%
timestamp=1764574659, rangeStart=158913789952, rangeEnd=163208757248, bestGenerations=221, bestPattern=162820877177, bestPatternBin=0000000000010010111101000111000010110101101111001, patternsPerSec=1225795096, progress=0.03%
timestamp=1764574663, rangeStart=163208757248, rangeEnd=167503724544, bestGenerations=220, bestPattern=163523515489, bestPatternBin=0000000000010011000010010110000101101010001100001, patternsPerSec=1223353079, progress=0.03%
timestamp=1764574666, rangeStart=167503724544, rangeEnd=171798691840, bestGenerations=220, bestPattern=167531422064, bestPatternBin=0000000000010011100000001101001101010000101110000, patternsPerSec=1225036355, progress=0.03%
timestamp=1764574670, rangeStart=171798691840, rangeEnd=176093659136, bestGenerations=217, bestPattern=175147735243, bestPatternBin=0000000000010100011000111100111100101100011001011, patternsPerSec=1187702935, progress=0.03%
timestamp=1764574674, rangeStart=176093659136, rangeEnd=180388626432, bestGenerations=219, bestPattern=176445547573, bestPatternBin=0000000000010100100010100111110010110010000110101, patternsPerSec=1194082520, progress=0.03%
timestamp=1764574677, rangeStart=180388626432, rangeEnd=184683593728, bestGenerations=219, bestPattern=181511087157, bestPatternBin=0000000000010101001000010111001110110010000110101, patternsPerSec=1193613917, progress=0.03%
timestamp=1764574681, rangeStart=184683593728, rangeEnd=188978561024, bestGenerations=219, bestPattern=188335154069, bestPatternBin=0000000000010101111011001101001100110001110010101, patternsPerSec=1206961152, progress=0.03%

It looks like it'll be done in about 6 days

[aharbick]

The 7x7 search ran to completion and the longest pattern was 223 (there were 392 different initial patterns that lasted that long). Here are a few:

Code: Select all

x = 7, y = 7, rule = B3/S23:T7,7
2bob3o$3o$o2b2obo$2b3o$2o$o2bobo$bo2bobo!

Code: Select all

x = 7, y = 7, rule = B3/S23:T7,7
2bob2o$2o2b2o$obo$2o3bo$2b2ob2o$bobo2bo$o3bobo!

Code: Select all

x = 7, y = 7, rule = B3/S23:T7,7
2bob3o$bo2bobo$o2bobo$2o$2b3o$o2b2obo$3o!

This is the entire log... https://www.dropbox.com/scl/fi/zch9i6vw ... 5wo5g&dl=0

NOTE: I didn't look into what happened with the final ~8 batches that it searched (it found no candidates for those which seems sus). I'll look into that another time.