On utilizations of the time-space tradeoff

[testitemqlstudop]

Many modern computers have an excessive amount of memory. Unless Chrome is running, most PCs have about 2GB to 6GB of free memory. Many search programs can employ this - the only one I currently know of is zfind, which stores rule transitions in a pre-computed table.

I think apgsearch and other search programs can employ the extra memory. One possible way is to tile the universe with 5x5 tiles (with 1-cell overlap between adjacent tiles), storing the next-generation evolution of every possible 5x5 tile, and applying this transition every generation. This would only use ~830 MB (given optimal data structures).
For incredibly powerful servers, this can be extended to 6x6, which would use ~300 GB.
Of course, this is an incredibly stupid idea, as this will be nothing compared to hashlife/Lifelib algorithms, but it's a start.

Any thoughts on better ways?

[Macbi]

I like this idea. I'm not an expert on these things, but my understanding is that computers these days actually have several types of memory, and that the one that you have lots of is also the one that is slowest to access. So this idea might not help if the slowness of accessing the memory is worse than the extra calculations. Maybe we could make a list of the patterns that occur most commonly in Life soups and store them in the smaller faster memory, so that the computer rarely has to resort to the slower kind of lookup.

[dvgrn]

Maybe we could make a list of the patterns that occur most commonly in Life soups and store them in the smaller faster memory, so that the computer rarely has to resort to the slower kind of lookup.

There's a similar idea involving 5x5 tiles that I've been tinkering with off and on for many years, but have never finished a decent search implementation. If you make in-memory lists of all the 3x3 predecessors of every 5x5 tile, and then sort each list according to how "preferable" each predecessor is (lowest population? looks most like a glider? compatible with being a still life? etc.) then you could maybe use these lists to do a non-exhaustive search for predecessors of a pattern, that might be able to find interesting predecessors faster a lifesrc-type approach.

The most recent effort along these lines is simsim314's experimental code from four years ago, described on the Parallelizable tile-based backtracking thread. If I remember right, the absolute minimum memory use is something like 8GB, but there's some hope that pre-calculating all those lookup tables will allow for a significant speedup... once someone figures out how to do the weighting to explore a reasonable-sized search tree.

I really love the idea of a tile-based backtracking search that starts with something like Sir Robin, and slowly chugs away one backwards tick at a time, with each predecessor having a larger and larger central region of constructible small stable objects, and a narrow ring of activity around the outside that eventually resolves into a big pile of gliders.

Unfortunately I'm not clever enough to come up with nearly enough magical mathematical shortcuts to make anything like this work -- the minimum search space seems to be too big by many, many orders of magnitude. It seems likely to be billions of times easier to run searches to prove that Life is omniperiodic, so probably we ought to work on that first...!