soup searching an 8x8 grid
soup searching an 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!
Re: soup searching an 8x8 grid
Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576
S: SKOP
G: gun
- yujh
- Posts: 3068
- 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
There is a catagolue census for 8x8, I’m sure. If not I can just produce it
B34kz5e7c8/S23-a4ityz5k
b2n3-q5y6cn7s23-k4c8
B3-kq6cn8/S2-i3-a4ciyz8
B3-kq4z5e7c8/S2-ci3-a4ciq5ek6eik7
Bored of Conway's Game of Life? Try Pedestrian Life -- not pedestrian at all!
Re: soup searching an 8x8 grid
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
Re: soup searching an 8x8 grid
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 ]]
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?
Re: soup searching an 8x8 grid
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.
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.
-
- Posts: 2200
- Joined: August 5th, 2016, 10:27 am
- Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
- Contact:
Re: soup searching an 8x8 grid
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.aharbick wrote: ↑December 11th, 2021, 4:39 pmI 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...
Isn't the agar-with-gutter 17×17?dvgrn wrote: ↑December 11th, 2021, 4:04 pmI 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 ]]
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!
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!
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!
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!
Harvest Moon
2-engine p45 gliderless HWSS gun
Small p2070 glider gun
Forgive me if I withhold my enthusiasm.
Re: soup searching an 8x8 grid
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!
Re: soup searching an 8x8 grid
Yes, that was me. The results are on the Soup Search Results thread; the first one is here.dvgrn wrote: ↑December 11th, 2021, 4:04 pmI 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?
Re: soup searching an 8x8 grid
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!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbboo$oooboobo$boboobbb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbooo$boooboob$bbboobob!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbooob$oooboooo$obbbbobo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbboooob$ooooobob$bbbbooob!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bboboooo$oobbbooo$bobobbbb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbobbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$bbbbbbbb$boboooob$booboboo$bbobbobo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bboobbob$obobobbb$oobbbooo$oobobbbo$bbbobobb$bobobbob$obobbbbb$ooobbboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bboobobo$oobbbboo$boobbobb$bbbbbbbo$oobbooob$obobooob$bbooooob$booobbbb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
oobbooob$oboooobb$bobboobb$obbobbbo$oboobbbb$obbbobbb$ooobbbbb$bbbobobo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbbobbob$obbobobb$oobobboo$oboobbob$obbooooo$obooobob$bobboboo$oboooobo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bboobbbo$boobbobb$bboooboo$obobobbo$boobooob$obobbbbo$bobobbbo$bobobbbo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
ooobbobb$boobobbo$oobbboob$boobboob$booboobo$bbobooob$obbobbob$obbobboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
oobbboob$bboboobo$ooooobob$obbbbboo$bbooobob$obbobbob$ooboobbb$booooobb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bobbbboo$oooooobo$booobboo$oobbbboo$boobooob$obbobooo$bbbobobb$oobooboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
ooboobob$bboboobo$obobbobb$obbooooo$obobobbo$oobobobo$bbbbobob$booobboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
booooobo$bobobbob$ooobooob$obbbbooo$bobbobbo$oboobboo$boobobob$bbbbobbb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
ooobbooo$booooboo$obobbbbb$boobboob$bobooboo$bbbbbobo$bbobobob$boboboob!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
obbobbob$obbbobbb$bbbobooo$boobobbb$bbbboooo$boboobbo$oobobbbb$bboboobo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbbbooob$oboooboo$bobobbbo$bbbobboo$bobboobb$bobbboob$oobbobbb$obobbboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
oboboobo$obbooobo$bbooobob$ooboobbo$bbbbobbo$bobobobo$bbooboob$bobbbobb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbbbbbbo$bbobbobo$booobbbo$ooobbbbo$oboobbob$oboobobb$obobobbo$oobobboo!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bboboobb$oobbbbob$obobbbbb$bobbbobb$obobobbo$boobobbo$bbbooooo$oobboobb!
Code: Select all
x = 8, y = 8, rule = B3/S23:P8,8
bbooobbo$bbooobob$bbobbobb$boboboob$oobbbbbo$bbboobob$bbboobbo$obbbobob!
Re: soup searching an 8x8 grid
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!
Re: soup searching an 8x8 grid
Code: Select all
x=17,y=16,rule=B3/S23
3bo3bobo2bob2o$bobo4bo4b4o$bobo5bobo2b3o$b2obob2o3b2o$3o4b2ob2o2b2o$4b
o4bo$4b2obobob2ob3o$3ob3o2b2o$b3o2bobobo5bo$o3b2o3bobo2b2o$4bo3bob2o3b
o$2obo2bobobo2b2o$3b3o5bo2b2o$2obo4bo2bob2o$o3bob2obo3b2o$2bo8bobobo![[ STOP 3 GPS 4 ]]
Re: soup searching an 8x8 grid
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
Re: soup searching an 8x8 grid
Usually taking the leading term (identity) gives a good estimate: 2^64/8. The rest of the terms are usually orders of magnitudes smaller.
How much of current CA technology can I redevelop "on a desert island"?
Re: soup searching an 8x8 grid
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.pzq_alex wrote: ↑October 22nd, 2022, 11:57 pmI'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.
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.
Re: soup searching an 8x8 grid
Oops, just remembered: if we're running these on a torus, that means there are more transformations to account for.dvgrn wrote: ↑October 23rd, 2022, 12:15 amSide 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.
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.
Re: soup searching an 8x8 grid
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.
How much of current CA technology can I redevelop "on a desert island"?
Re: soup searching an 8x8 grid
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.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;
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.
Re: soup searching an 8x8 grid
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.