soup searching an 8x8 grid

[aharbick]

I think I got the "strip search" algorithm implemented, but in running it I don't think it's going to be as fast as my current approach.

But... I'm not entirely sure that I'm comparing apples to apples. We examine 2^32 middle blocks looking at all combinations of unique top and bottom strips. Each unique middle block represents 2^32 total patterns in the 2^64 space, but we can process MANY fewer by looking at only the unique top/bottom combinations (taking advantage of the insights of the algorithm). I am seeing rates as high as ~36billion patterns per second (or about 100 middle blocks every 10-15 seconds)

Here's output showing that:

Code: Select all

aharbick@Conway:~/conway/find-optimal$ ./build/find-optimal -S -r
CUDA devices available: 1
Using 1 GPU with blockSize=1024, threadsPerBlock=1024
Topology: Box/Plane (non-wrapping boundaries)
Not saving results to Google Sheets (--dont-save-results specified)
Strip search mode: blocks 0 to 4294967295
Starting strip search...
Block range: 0 to 4294967295
Total middle blocks to search: 4294967295

timestamp=1765746741, firstBlock=0, lastBlock=99, avgTopStrips=19437, avgBottomStrips=6462, avgCombinations=125578706, bestGenerations=188, bestPattern=7886365897482987432, bestPatternBin=0110110101110010000000000000000000000000001110100110011110101000, patternsPerSec=37274572809
timestamp=1765746755, firstBlock=100, lastBlock=199, avgTopStrips=22297, avgBottomStrips=6471, avgCombinations=144248285, bestGenerations=188, bestPattern=2298806134804251859, bestPatternBin=0001111111100111000000000000000000000000011111110000010011010011, patternsPerSec=36959379097
timestamp=1765746766, firstBlock=200, lastBlock=299, avgTopStrips=19794, avgBottomStrips=6480, avgCombinations=128223794, bestGenerations=188, bestPattern=8711932004188168395, bestPatternBin=0111100011100111000000000000000000000000111111100010000011001011, patternsPerSec=37459220180
timestamp=1765746778, firstBlock=300, lastBlock=399, avgTopStrips=23489, avgBottomStrips=6484, avgCombinations=152250564, bestGenerations=188, bestPattern=7886365897499741905, bestPatternBin=0110110101110010000000000000000000000001001110100000111011010001, patternsPerSec=36888274805
timestamp=1765746792, firstBlock=400, lastBlock=499, avgTopStrips=24833, avgBottomStrips=6481, avgCombinations=160919784, bestGenerations=189, bestPattern=13148540587114890728, bestPatternBin=1011011001111001000000000000000000000001110010100000010111101000, patternsPerSec=36472557334
timestamp=1765746803, firstBlock=500, lastBlock=599, avgTopStrips=20727, avgBottomStrips=6496, avgCombinations=134559967, bestGenerations=188, bestPattern=7886365897516410491, bestPatternBin=0110110101110010000000000000000000000010001110000110011001111011, patternsPerSec=36980986166

However since we can't rule out any symmetries we're still looking at 2^64 / 36B / 86400sec / 365.25days = ~16 years (you can similarly compute the numbers the result from blocks.... 2^32block * .12sec/block / 86400sec / 365.25days)

Whereas my initial solution works against 2^61 and is seeing about 8+billion patterns/sec (~9years)

Further I observe that some blocks have MANY more unique top and bottom strips. I found the middle block that is part of my current known longest generation (213) and I tested a 500 block range that included that to compare to the initial blocks seen above:

Code: Select all

aharbick@Conway:~/conway/find-optimal$ ./build/find-optimal -Srange:72401849:72402349 -r
CUDA devices available: 1
Using 1 GPU with blockSize=1024, threadsPerBlock=1024
Topology: Box/Plane (non-wrapping boundaries)
Not saving results to Google Sheets (--dont-save-results specified)
Strip search mode: blocks 72401849 to 72402349
Starting strip search...
Block range: 72401849 to 72402349
Total middle blocks to search: 500

timestamp=1765746407, firstBlock=72401849, lastBlock=72401948, avgTopStrips=18052, avgBottomStrips=26600, avgCombinations=475893588, bestGenerations=199, bestPattern=7600955016023463364, bestPatternBin=0110100101111100000001000101000011000011110011010101010111000100, patternsPerSec=9472173625
timestamp=1765746453, firstBlock=72401949, lastBlock=72402048, avgTopStrips=22574, avgBottomStrips=25637, avgCombinations=578134435, bestGenerations=201, bestPattern=1547554166893400372, bestPatternBin=0001010101111010000001000101000011000100010110110101000100110100, patternsPerSec=9809096891
timestamp=1765746501, firstBlock=72402049, lastBlock=72402148, avgTopStrips=21963, avgBottomStrips=25715, avgCombinations=563088457, bestGenerations=213, bestPattern=1439186300866781946, bestPatternBin=0001001111111001000001000101000011000100110001011110001011111010, patternsPerSec=9344664109
timestamp=1765746553, firstBlock=72402149, lastBlock=72402248, avgTopStrips=21753, avgBottomStrips=25837, avgCombinations=561374743, bestGenerations=213, bestPattern=1439186300868846330, bestPatternBin=0001001111111001000001000101000011000100111001010110001011111010, patternsPerSec=9222172641
timestamp=1765746601, firstBlock=72402249, lastBlock=72402348, avgTopStrips=23283, avgBottomStrips=25895, avgCombinations=602453320, bestGenerations=198, bestPattern=13157552531296494602, bestPatternBin=1011011010011001000001000101000011000101011110000010010000001010, patternsPerSec=9367637507

Since there are many more top and bottom strips there are roughtly 4x as many top+bottom strip combinations and as a consequence we process such middle blocks about 4x as slowly.

I think it's hard to know what the "typical" number of unique top/bottom strip combinations so it's hard to know what the average would be to predict how long the whole processing will take.

Here's the branch that I used to build the "strip search"... I would love to hear if you think I didn't get it right. https://github.com/aharbick/conway/compare/strip_search

[vilc]

I think I got the "strip search" algorithm implemented, but in running it I don't think it's going to be as fast as my current approach.
[...]
Here's the branch that I used to build the "strip search"... I would love to hear if you think I didn't get it right. https://github.com/aharbick/conway/compare/strip_search

Great to see that the trick works! Fortunately (in a way...), you appear to have missed one step : you don't need to look at all 2^32 middle blocks, only about one in eight.

If you look at the core 4x4 block, you can perform a first reduction. For example, there is no need to consider both of these blocks :

Code: Select all

x = 8, y = 8, rule = LifeHistory:T8,8
8B$8B$2.4D$2.2DCD$2.3DC$2.D3C$8B$8B!

Code: Select all

x = 8, y = 8, rule = LifeHistory:T8,8
8B$8B$2.4D$2.C3D$2.CDCD$2.2C2D$8B$8B!

There are 2^16 = 65536 such 4x4 blocks, but (by Burnside's lemma) only (2^16 + 2^8 + 2^8 + 2^10 + 2^10 + 2^4 + 2^4 + 2^8)/8 = 8548 up to rotations and reflections (4th term in https://oeis.org/A054247). For each of the 8548 unique blocks, you can the add 2^16 different 4x2 "ears" to complete the middle 8x4 block.

You can add a minor amount of reduction if you deduplicate the 8x4 blocks when the current 4x4 block has some symmetry, but I'm not sure if this is worth the effort. For example this 8x4 block

Code: Select all

x = 8, y = 8, rule = LifeHistory:T8,8
8B$8B$2CD2C3D$CDC2DC2D$2DC2DCDC$3D2CD2C$8B$8B!

is the same as this 8x4 block

Code: Select all

x = 8, y = 8, rule = LifeHistory:T8,8
8B$8B$3D2CD2C$2DC2DCDC$CDC2DC2D$2CD2C3D$8B$8B!

[aharbick]

Excellent. Thanks for the coaching. I implemented the D4 center block symmetry reduction (code pushed to https://github.com/aharbick/conway/compare/strip_search)

I then ran it against the "centerIdx" that contains my known longest pattern(s)... Here's a snippet of the output

Code: Select all

timestamp=1765833521, centerIdx=2442, startMiddleIdx=29400, endMiddleIdx=29499, bestGenerations=203, bestPattern=13704713158672020795, bestPatternBin=1011111000110000111011000000000111010011010001000111010100111011, patternsPerSec=101951398714
timestamp=1765833553, centerIdx=2442, startMiddleIdx=29500, endMiddleIdx=29599, bestGenerations=199, bestPattern=5248645206815132361, bestPatternBin=0100100011010110111011110000000111010000010001011100101011001001, patternsPerSec=111275044323
timestamp=1765833584, centerIdx=2442, startMiddleIdx=29600, endMiddleIdx=29699, bestGenerations=199, bestPattern=5248645206815263432, bestPatternBin=0100100011010110111011110000000111010000010001111100101011001000, patternsPerSec=111922541997
timestamp=1765833624, centerIdx=2442, startMiddleIdx=29700, endMiddleIdx=29799, bestGenerations=206, bestPattern=2294915254418975796, bestPatternBin=0001111111011001001011010100001111010001010001001010110000110100, patternsPerSec=86496629692
timestamp=1765833667, centerIdx=2442, startMiddleIdx=29800, endMiddleIdx=29899, bestGenerations=213, bestPattern=14160210314578517907, bestPatternBin=1100010010000011001011000100000111010001010001100101111110010011, patternsPerSec=87307549925
timestamp=1765833706, centerIdx=2442, startMiddleIdx=29900, endMiddleIdx=29999, bestGenerations=213, bestPattern=14160210314578583442, bestPatternBin=1100010010000011001011000100000111010001010001110101111110010010, patternsPerSec=88765450742
timestamp=1765833746, centerIdx=2442, startMiddleIdx=30000, endMiddleIdx=30099, bestGenerations=198, bestPattern=13232539160084325955, bestPatternBin=1011011110100011011011000100000111010001010001011010011001000011, patternsPerSec=87498056877
timestamp=1765833784, centerIdx=2442, startMiddleIdx=30100, endMiddleIdx=30199, bestGenerations=198, bestPattern=6565242486233961635, bestPatternBin=0101101100011100011011010100000111010000010001110001010010100011, patternsPerSec=89903055976

The patternsPerSec is computed as https://github.com/aharbick/conway/blob ... #L322-L327 and we report on 100 distinct middle blocks at a time. Because different middle blocks produce different unique top and bottom strips the performance of processing each middle block has more variation.

I ran it through about 40k of the 65k possible middle blocks given my known centerIdx and observed the following stats for patternsPerSec:

Code: Select all

Minimum: 75,914,398,662
Maximum: 176,967,926,426
Average: 99,897,364,549

Those numbers are reporting against the 2^64 space... So on my current hardware the worse case is 7.7 years (which is faster than my previous solution of about 9 years) and if somehow I got lucky the best case would be 3.3 years... The average from the sample sits at 5.8 years.

That said, I kinda hastily put this together only validating results with some adhoc examples so I need to do some more work to write some tests and validate the results I'm seeing.

But it looks like progress!