Algorithm for reversing the GoL rules
Algorithm for reversing the GoL rules
I'm a bit new on this forum but, as it seems full of competent people on the GoL subject, it may be a good place for my topic.
I know that discussions are more related to interesting evolving patterns but, in my case, I'm more about working on an algorithm to run the game in reverse. I know this is a NP hard problem and that's not always possible to find a predecessor. But for not too big world grids, it is often definitively possible.
I googled a lot on this subject and the best reference I could find is this one:
https://nbickford.wordpress.com/2012/04 ... nd-profit/
It's lacking a lot of details, and it mentions methods like Wood, Duparc and Quadwood that also seem to lack strong reference in the literature. Anyway, reading between the lines is possible to understand the main idea of its methodology and I could start from there.
Now I would like to go beyond this. So my question is, does someone here knows / heard about any practical algorithm to run the GoL backward ?
Re: Algorithm for reversing the GoL rules
Periods discovered:
All evens up to 128 except 52,58,78,82,92,94,98,104,118,122
5-15,㉕-㉛,㉟㊺,51,63,65,73,75
1㊳㊵㊹㊼㊽,54,56,72,74,80,90,92
217,240,300,486,576
Guns: 20,21,32,54,55,57,114,117,124,126
SKOPs: 32,74,76,102,196
Re: Algorithm for reversing the GoL rules
That's maybe a good general summary, but there are a lot of exceptions that should be mentioned.
In early 2018, Tom Rokicki put together an experimental patch for Golly that allowed it to call a SAT solver (minisat) to run Life backwards for small patterns. It just picked one out of the (often) thousands of possibilities, but it often ran pretty fast, at least up to 30x30 or so. I don't think that experiment was ever put out on GitHub or anywhere public, but I have a copy in an email somewhere if anyone wants to look at it.
Along similar lines, you can set up your average small pattern in JavaLifeSearch or WinLifeSearch, or in LLS (the CA-rule/SAT-solver combination that most people around here use the most), and usually you'll get an answer back near-instantly (for small enough values of "small", anyway).
So it's not that it can't be done, it's just that it's unreliable, and when you iterate back through many generations, you get bigger and bigger patterns that are more and more likely to be Gardens of Eden ... without, most of the time, ever seeing anything but bigger and bigger patches of space dust.
I've been wishing for many years now for a reliable metric that can pick predecessors that are somehow more likely to be glider-constructible -- in my fevered imagination, you would step backward, picking the most glider-constructible option among the available choices at each step, and after a while you'd have a glider synthesis recipe for whatever it was.
People do attempt things along these lines every few years, but coming up with a workable metric is a very very difficult problem. Without a God's algorithm for glider syntheses, you usually can't tell a late-stage glider collision from random space dust.
-
- Posts: 861
- Joined: June 27th, 2009, 10:58 am
- Location: Germany
Re: Algorithm for reversing the GoL rules
Not much different from what‘s already used, but with the additional minimal limit for number of predecessors.
Re: Algorithm for reversing the GoL rules
Thanks, this is interesting.dvgrn wrote: ↑February 18th, 2022, 7:32 amThat's maybe a good general summary, but there are a lot of exceptions that should be mentioned.
In early 2018, Tom Rokicki put together an experimental patch for Golly that allowed it to call a SAT solver (minisat) to run Life backwards for small patterns. It just picked one out of the (often) thousands of possibilities, but it often ran pretty fast, at least up to 30x30 or so. I don't think that experiment was ever put out on GitHub or anywhere public, but I have a copy in an email somewhere if anyone wants to look at it.
Along similar lines, you can set up your average small pattern in JavaLifeSearch or WinLifeSearch, or in LLS (the CA-rule/SAT-solver combination that most people around here use the most), and usually you'll get an answer back near-instantly (for small enough values of "small", anyway).
So it's not that it can't be done, it's just that it's unreliable, and when you iterate back through many generations, you get bigger and bigger patterns that are more and more likely to be Gardens of Eden ... without, most of the time, ever seeing anything but bigger and bigger patches of space dust.
I've been wishing for many years now for a reliable metric that can pick predecessors that are somehow more likely to be glider-constructible -- in my fevered imagination, you would step backward, picking the most glider-constructible option among the available choices at each step, and after a while you'd have a glider synthesis recipe for whatever it was.
People do attempt things along these lines every few years, but coming up with a workable metric is a very very difficult problem. Without a God's algorithm for glider syntheses, you usually can't tell a late-stage glider collision from random space dust.
The argument "this is not reversible" is indeed often used although the point is not to reverse a pattern "mathematically", but instead to just reverse it if it is possible. And in the case you get multiple solutions, you are free to chose one and to repeat the process.
For the metric I could at least provide one with the results I get on 8x8 periodic grids, as I can resolve them almost instantaneously. I never compiled statistics on random grids but most of the time, at least one inverse exists. I will do that asap and come back with some numbers.
I'm pretty confident I could reverse 12x12 grids with some modifications of my software, but what I'm seeking now are new tips to jump on 16x16 grids.
Re: Algorithm for reversing the GoL rules
Would any LLS experts out there care to throw together a quick walkthrough of how to do the setup to find predecessors of 16x16 grids? I suspect LLS would be one of the more useful benchmarks for comparison purposes here.
(I'd like to become an LLS expert this year, and I'm definitely not one now, so that would really help me out if nobody else.)
Re: Algorithm for reversing the GoL rules
1) Go to the source and click the download button and then unzip it once it downloads. There's no particular location where you have to put it. I've linked to the 'develop' branch of the project which is technically not the official version. It's much better than version 0 but I haven't been prioritising releases.dvgrn wrote: ↑February 18th, 2022, 10:40 amWould any LLS experts out there care to throw together a quick walkthrough of how to do the setup to find predecessors of 16x16 grids? I suspect LLS would be one of the more useful benchmarks for comparison purposes here.
(I'd like to become an LLS expert this year, and I'm definitely not one now, so that would really help me out if nobody else.)
2) Download a SAT solver. The best one is kissat. Download and unzip it, then open a terminal window in its build directory and run './configure && make test'. This should compile kissat and create a file called 'kissat' in the build directory. (For me one of the tests fails but this file still appears.) It's this file which is the solver.
3) Drag kissat from that directory to the solvers directory of LLS.
4) Create a 'search pattern' to describe what you want to find. In this case it should look something like this:
Code: Select all
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0
0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,0,0,0
0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,0,0
0,0,0,0,0,1,1,1,0,1,1,0,1,1,1,1,1,0,0,0
0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0
0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,0,1,0,0
0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,1,0,0,0,0
0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,0
0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0
0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0
0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,0,0
0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,0,1,1,0,0
0,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,1,0,0
0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Code: Select all
import golly as g
x, y, width, height = g.getselrect()
grid = [["0"]*width for _ in range(height)]
cells = g.getcells([x, y, width, height])
for i in range(0,len(cells),2):
grid[cells[i + 1] - y][cells[i] - x] = "1"
with open("pattern.csv", "w") as output_file:
output_file.write("\n".join(",".join(row) for row in grid) + "\n")
5) Save this file in the search_patterns directory of LLS, in this example I'll assume the name is pattern.csv.
6) Open the terminal in the logic-life-search directory and run the command
Code: Select all
python lls search_patterns/pattern.csv
Code: Select all
Getting search pattern...
Done
Preprocessing...
Done
Number of undetermined cells: 400
Number of variables: 400
Number of clauses: 31498
Active width: 20
Active height: 20
Active duration: 1
Solving...
Done
Time taken: 0.7751362323760986 seconds
x = 22, y = 22, rule = B3/S23
bbbbbbbbbbbbbbbbbbbbbb$
bobbbbbbbbbobbbobbbbbb$
bbobbbbbobbbbobbbobbbb$
bbbboobbobbbbbooobbbbb$
bbobobbboobobbbobbobbb$
bbbbbbboobboobbbbobbbb$
bbbobbbobbbobobboobbbb$
bbbbbbobbbbobboobboobb$
bbboobbbobobobobbbbbbb$
bbbbbbboobbbbobbbbobob$
bbbbobbobboobobbooobob$
bbobobbbbobooobbboobbb$
bbbobboboobobbobbbbbob$
bbbbobbbbbboobbboooobb$
bbobbooboobbobbbobboob$
bbobbbbbboboboobbbboob$
booobooobobbbbbbobbobb$
booobbobbobobobbobobob$
bbobbbbbbbboooooboobbb$
bbobbboobbbbobbbbbbbob$
bbbbbbbbbbobbobbbbbbbb$
bbbbbbbbbbbbbbbbbbbbbb!

9) Copy the output RLE back into Golly to check that it works.
Note that the hard work of finding the predecessor is done by kissat in just 0.8 seconds. So this approach deals with 16 by 16 soups quite quickly. I tried with a 40 by 40 soup and it returned UNSAT (i.e. no predecessor within the size 2 margin) in less than five seconds.
Re: Algorithm for reversing the GoL rules
It definitively seems very interesting and I will give a look to this.
Is there an easy mean to go for periodic grids (by encoding some kind of special constraint on the borders) ? It would avoid to surround the grid with 0 to deal with its expansion. This is a bit more constrained but solutions are also more elegant.
Re: Algorithm for reversing the GoL rules
Thanks! I've gone through all the steps, and they worked without any serious issues.
However, I ran into a whole bunch of gotchas along the way -- so I'll document them here in case anyone else finds them useful.
1) I used a Cygwin terminal window for both the downloading/cloning steps and the compilation of kissat.
Code: Select all
cd c:/repos
git clone https://github.com/arminbiere/kissat.git
cd kissat
./configure && make test
Code: Select all
gcc -W -Wall -O3 -DNDEBUG -c ../src/substitute.c
../src/substitute.c: In function ‘kissat_substitute’:
../src/substitute.c:592:16: warning: array subscript 3 is above array bounds of ‘unsigned int[3]’ [-Warray-bounds]
592 | c->lits[old_size - 1] = INVALID_LIT;
| ~~~~~~~^~~~~~~~~~~~~~
In file included from ../src/internal.h:10,
from ../src/inlinevector.h:4,
from ../src/inline.h:4,
from ../src/substitute.c:3:
../src/clause.h:35:12: note: while referencing ‘lits’
2) I figured git clone https://gitlab.com/OscarCunningham/logi ... search.git would be the way to go for LLS, too, but apparently even when I'm looking at the development branch on gitlab, that clones the whole repo, which defaults to the "main" (non-development) branch, which is written in Python2 and errors when you run it with Python3 -- the opposite of the development branch, which uses Python3 and errors when you try to run it with Python2.
... Python2 ?! Isn't that a sign that it's maybe high time to make the development branch into the main branch, and save a whole bunch of noobconfusion?
The invocation with just 'python' defaults to python3 on my system, so that works fine. It's okay to use
Code: Select all
python3 ./lls search_patterns/pattern.csv
Running the Python2 version (which was the non-development branch but I didn't realize that yet) I got another weird error after all the Python code seemed like it was going to work:
Code: Select all
File "/cygdrive/c/repos/logic-life-search/src/LLS_SAT_solvers.py", line 86, in use_solver
stdout=subprocess.PIPE, stdin=subprocess.PIPE, stderr=subprocess.PIPE)
File "/usr/lib/python2.7/subprocess.py", line 394, in __init__
errread, errwrite)
File "/usr/lib/python2.7/subprocess.py", line 1047, in _execute_child
raise child_exception
OSError: [Errno 2] No such file or directory
I got around having to switch branches in Git, by just downloading the ZIP file from the above link instead of using Git. That worked fine -- gave me the Python3 development branch, with the search_patterns folder and everything.
3) It might be worth adjusting csv_from_selection.py so that it makes the user choose a save location, so that it doesn't end up in whatever random folder Golly happens to think is the "current directory".
The current directory can be pretty mysterious, at least on Windows -- until I hard-coded a path, the script saved a pattern.csv successfully, but it took a system-wide search to find it (!) It turned up in C:\Users\{username}\AppData\Roaming\Golly, which is a horrible location because the AppData folder is hidden by default -- users mostly just have to know it's there, and navigate there by typing the path in File Explorer. It's not such a good idea to change settings so that you can see that hidden folder, because then it's possible to accidentally delete or move other system folders, which can wreck the operating system...
Third Time Was The Charm
After dodging those various bullets, everything now seems to be working.
I've seen all this kind of thing happen a lot before, so it didn't take me long to sort through it -- but I could imagine that someone who has never ventured outside of the world of Windows might have a tough time with the line-ending gotcha in particular. They probably wouldn't hit the development-branch problem unless they knew just enough about Git to be dangerous (like me).
EDIT: As I hoped, just adding another blank generation and another line of commas made LLS obligingly generate a 2-tick predecessor of my target pattern:
Code: Select all
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*
,,,,,,,,,,,,,,,,,,,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0
0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,0
0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0
0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,0,0
0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Code: Select all
x = 22, y = 22, rule = B3/S23
bbbbbbbbbbbbbbbbbbbbbb$
bobobobobooboobbboobbb$
bbbboooooooobbobobbbbb$
bboboobbobbbobbbboobob$
bbobbbooobbobobobboobb$
bbbbbbbbboboooboboboob$
bboboobbbbbbbbbboobobb$
bbboobbobbbobbbbobbobb$
boobbbbboboobboobobbbb$
boobobbbobbbboobboobbb$
bboboobobbbbboboobobob$
bboobbbobboooooooboobb$
bbbobboobbbbbooboobbob$
bboobbbobbbbbbbbbbbbob$
bbboobbbbbobobobbobbbb$
bbobbobboboboobbbbbbob$
bbboboobbbbbboboobooob$
bbbbbbbobobbbbbbooobbb$
bbboobbooooboobbbbbbbb$
bbbbbobbbbobbbbbbbbobb$
bboobbbbboboobobobbobb$
bbbbbbbbbbbbbbbbbbbbbb!
Code: Select all
Getting search pattern...
Done
Preprocessing...
Unsatisfiability proved in preprocessing
Done
Time taken: 0 seconds
Unsatisfiable
So I re-opened the input pattern in TextPad, saved it with Unix-style newline characters, and tried again. (On a PC you get \r\n, ASCII-13 + ASCII 10, as newline characters by default when you copy, paste, and save text files. If you don't save with Unix newlines -- just \n, ASCII 10 -- LLS will think you're specifying some kind of stripey pattern with every other line blank, and will get very very confused about this.)
I just did my pattern creation by copying and pasting and hand-editing, but when Python runs the csv_from_selection.py script on Windows, it will also use Windows line endings by default, with the same disastrous results.
However, Macbi has since pointed out that I was doing all of this while still accidentally working with main-branch LLS -- the newline problem has since been fixed. I tried it again on the development branch, and Windows line endings worked fine. So this is all just another symptom of using the main branch instead of the development branch.
Re: Algorithm for reversing the GoL rules
My last set of notes for LLS use involved Cygwin. I've now tried out WSL (Windows Subsystem for Linux) in combination with LLS, and it works great.
To see the files that you'll want to adjust -- search-pattern files, mostly -- in the WSL file system, type "\\wsl$" into File Explorer. When you navigate to the search_patterns subfolder, or wherever you decide to keep your template search patterns, you'll end up with a File Explorer path along the lines of
"\\wsl.localhost\Ubuntu\home\{username}\logic-life-search\search_patterns"
I've added a section to the LLS tutorial to describe a very basic setup for an iterative rewinding search. This could probably use a lot more detail.
In the new section, I've linked to Macbi's walkthrough, as a starting point.
For iterative rewinding searches, I think the script that Macbi supplied could be improved quite a bit. There's too much unnecessary manual setup work still needed to get the next backward step in an iterative rewinding search.
My version of Macbi's script, below, operates on a Golly selection as before. It writes directly to the clipboard instead of writing to a file in some unspecified location (Windows can make this file very difficult to find -- search for "current directory" in that link).
PYTHON -- collecting the target pattern from a Golly selection:
Code: Select all
# LLS-format-selection-to-clipboard.py
# Select a pattern in Golly that you want to input to LLS as a target pattern, as described in
# https://conwaylife.com/wiki/Tutorials/LLS#Predecessor_searches_%28rewinding%29
# Include an empty boundary of some appropriate size, to allow the predecessor to be larger than the pattern.
# Run this script, then paste the resulting grid into a Logic Life Search search-pattern text file.
import golly as g
x, y, width, height = g.getselrect()
grid = [["0"]*width for _ in range(height)]
cells = g.getcells([x, y, width, height])
for i in range(0,len(cells),2):
grid[cells[i + 1] - y][cells[i] - x] = "1"
s = "\n".join(",".join(row) for row in grid) + "\n"
g.setclipstr(s)
PYTHON -- hollowing out the center of a predecessor rectangle, with user-configurable margins:
Code: Select all
# LLS-replace-center-with-asterisks.py
# Copy the output of LLS-format-selection-to-clipboard.py to the clipboard,
# then run this script and supply the top, right, bottom, and left margin distances.
# The output Logic Life Search grid will be copied back to the clipboard.
import golly as g
def replace_with_asterisks(top_margin, right_margin, bottom_margin, left_margin):
# Retrieve the clipboard content
grid = g.getclipstr().strip().split("\n")
# Parse the grid into a list of lists
grid = [row.split(",") for row in grid]
rows = len(grid)
cols = len(grid[0])
# Validate margins
if top_margin + bottom_margin >= rows or left_margin + right_margin >= cols:
g.exit("Margins are too large for the grid dimensions.")
# Calculate boundaries for the region to replace with asterisks
start_row = top_margin
end_row = rows - bottom_margin
start_col = left_margin
end_col = cols - right_margin
# Replace specified region with asterisks
for r in range(start_row, end_row):
for c in range(start_col, end_col):
grid[r][c] = "*"
# Convert the grid back into a string
modified_grid = "\n".join([",".join(row) for row in grid])
# Output the modified grid to the clipboard
g.setclipstr(modified_grid)
g.show("Modified grid has been copied to the clipboard.")
s = g.getstring("Enter space-separated margins for top, right, bottom, left", "1 1 1 1")
slist = s.split(" ")
if len(slist) != 4: g.exit("Please supply values for all four margins.")
tp, rt, bt, lf = slist
top_margin, right_margin, bottom_margin, left_margin = int(tp), int(rt), int(bt), int(lf)
replace_with_asterisks(top_margin, right_margin, bottom_margin, left_margin)
LUA -- collecting the target pattern from a Golly selection:
Code: Select all
-- LLS-format-selection-to-clipboard.lua
-- Select a pattern in Golly that you want to input to LLS as a target pattern, as described in
-- https://conwaylife.com/wiki/Tutorials/LLS#Predecessor_searches_%28rewinding%29
-- Include an empty boundary of some appropriate size, to allow the predecessor to be larger than the pattern.
-- Run this script, then paste the resulting grid into a Logic Life Search search-pattern text file.
local g = golly()
-- Get the selection rectangle
local x, y, width, height = table.unpack(g.getselrect())
-- If no selection exists, exit the script
if not x then
g.exit("No selection found. Please select a pattern in Golly.")
end
-- Create an empty grid filled with "0"
local grid = {}
for _ = 1, height do
local row = {}
for _ = 1, width do
table.insert(row, "0")
end
table.insert(grid, row)
end
-- Get live cells in the selection
local cells = g.getcells({x, y, width, height})
-- Populate the grid with "1" for live cells
for i = 1, #cells, 2 do
local cell_x = cells[i]
local cell_y = cells[i + 1]
grid[cell_y - y + 1][cell_x - x + 1] = "1"
end
-- Convert the grid to a string in LLS format
local result = {}
for _, row in ipairs(grid) do
table.insert(result, table.concat(row, ","))
end
local lls_format = table.concat(result, "\n") .. "\n"
-- Copy the result to the clipboard
g.setclipstr(lls_format)
g.show("Grid in LLS format has been copied to the clipboard.")
Code: Select all
-- LLS-replace-center-with-asterisks.lua
-- Copy the output of LLS-format-selection-to-clipboard.lua to the clipboard,
-- then run this script and supply the top, right, bottom, and left margin distances.
-- The output Logic Life Search grid will be copied back to the clipboard.
local g = golly()
function replace_with_asterisks(top_margin, right_margin, bottom_margin, left_margin)
-- Retrieve the clipboard content
local clipboard = g.getclipstr()
if clipboard == "" then
g.exit("Clipboard is empty. Please copy a grid first.")
end
-- Split the clipboard content into lines
local grid = {}
for line in clipboard:gmatch("[^\r\n]+") do
table.insert(grid, line)
end
-- Parse the grid into a table of tables
for i, row in ipairs(grid) do
grid[i] = {}
for cell in row:gmatch("[^,]+") do
table.insert(grid[i], cell)
end
end
local rows = #grid
local cols = #grid[1]
-- Validate margins
if top_margin + bottom_margin >= rows or left_margin + right_margin >= cols then
g.exit("Margins are too large for the grid dimensions.")
end
-- Calculate boundaries for the region to replace with asterisks
local start_row = top_margin + 1
local end_row = rows - bottom_margin
local start_col = left_margin + 1
local end_col = cols - right_margin
-- Replace specified region with asterisks
for r = start_row, end_row do
for c = start_col, end_col do
grid[r][c] = "*"
end
end
-- Convert the grid back into a string
local modified_grid = {}
for _, row in ipairs(grid) do
table.insert(modified_grid, table.concat(row, ","))
end
-- Output the modified grid to the clipboard
g.setclipstr(table.concat(modified_grid, "\n"))
g.show("Modified grid has been copied to the clipboard.")
end
-- Get the margins from the user
local input = g.getstring("Enter space-separated margins for top, right, bottom, left", "1 1 1 1")
local margins = {}
for value in input:gmatch("%S+") do
table.insert(margins, tonumber(value))
end
if #margins ~= 4 then
g.exit("Please supply values for all four margins.")
end
-- Call the function with user-provided margins
replace_with_asterisks(margins[1], margins[2], margins[3], margins[4])
I'm an LLS newbie still myself, though, so even more than that, I could use some advice on how to further improve my rewinding search methods. Is there a way to set a population limit for this kind of search, for example?
Re: Algorithm for reversing the GoL rules
Code: Select all
x = 57, y = 20, rule = B3/S23
4bobo2bo5bobobo19bobo2bo5bobobo$3bo4bo2b2o2bobobo18bo4bo2b2o2bobobo$b
3ob2ob2o3bobobobobo14b3ob2ob2o3bobobobobo$bob2o10b2o4bo14bob2o10b2o4bo
$6bobobo2bo5bo21bobobo2bo5bo$bob2obo2bobo2bob2o18bob2obo2bobo2bob2o$b
2obo5bo2bo4bo17b2obo5bo2bo4bo$3b3ob3o2b3obobobo17b3ob3o2b3obobobo$3bo
3b2o3b2o3bo20bo3b2o3b2o3bo$4bob3ob3o3b2o3bo17bob3ob3o3b2o3bo$4ob2o4bo
7bo15b4ob2o4bo7bo$2b2o10bo4b2o16b2o10bo4b2o$2bo4b2o2b2o2b6o16bo4b2o2b
2o2b6o$4b3o3b4obo2bo20b3o3b4obo2bo$3bob2o3b2obobobo20bob2o3b2obobobo$o
bo3bo8bobo17bobo3bo8bobo$6bob3obob3obob2o19bob3obob3obob2o$b3obo5bo6bo
17b3obo5bo6bo$10b4o2bo2bo25b4o2bo2bo$ob2o2b2obob2obo26b2o2b3obo!
Periods discovered:
All evens up to 128 except 52,58,78,82,92,94,98,104,118,122
5-15,㉕-㉛,㉟㊺,51,63,65,73,75
1㊳㊵㊹㊼㊽,54,56,72,74,80,90,92
217,240,300,486,576
Guns: 20,21,32,54,55,57,114,117,124,126
SKOPs: 32,74,76,102,196
Re: Algorithm for reversing the GoL rules
Yup -- I've been using the scripts above to build a rectangular predecessor template pattern, but then gradually filling in the corners with 0's until I start getting UNSAT results -- and then (when I remember) looking to see if there are any cells that I can remove manually before taking the next backward step.hotdogPi wrote: ↑November 30th, 2024, 6:36 pmSometimes you may find you want to go through a different predecessor. This is an example that dvgrn gave, with the original on the left and my modified version on the right. Only the bottom row changed, with three deleted cells and one cell shifted over one.
It seems like it's maybe a bit easier to find predecessors for patterns that don't have lots of ON cells in the corners.
I haven't started trying to limit population yet, partly because I'm not sure if that will really make it easier to keep the predecessor chain going. Maybe it's more important to avoid some specific structures, at all costs, even if the population is higher.
Back beyond T = -10 -- or rather, above a bounding box size of around 40x40 -- it does seem like Gardens of Eden start showing up, and pretty quickly they get progressively harder to avoid. Smaller patterns, up to 32x32 or so, usually seem to have predecessors with a bounding box only one cell larger in each direction -- so an (x+2) by (y+2) predecessor for an x-by-y pattern. And LLS can find predecessors of that size in less than a minute. But above that point, I've been having to add various tricky constraints to keep the chain going.
At larger sizes it starts to get more common that a (x+2) by (y+2) predecessor centered on the x-by-y target pattern will return UNSAT -- but solutions will show up for (x+4) by (y+4), or even sometimes at (x+6) by (y+6) but not smaller sizes. However, it seems worth avoiding those kinds of quickly-expanding solutions for as long as possible, because they seem to be much more likely to be Gardens of Eden. For example, here's a ten-tick predecessor of the $1.37 target pattern, that shows the deadly high-population areas all around the edges at the T = -10 generation:
Code: Select all
x = 39, y = 37, rule = B3/S23
ob2ob2o2b2ob2ob2ob2ob2ob2ob2obo3b2obo$b29o2b5o$4o2b2ob3obo3bo4bo4bob5o
2bobo$4o5b2o2b2o3b3o2b5obobo3b2o$bobobo3bo2b2ob5obobobo2b2o2bob3obo$b
4o8bo6bo8bob2o4bo$2o3bob3o3b2o3bobobob2o2b2o6b3o$2obo6b2o2b3o2bobo2b2o
3bob2o2b4o$bob3obobo4bobo7bo2bo7b3o$b2o2b2o7bob3o2bo2bo3bo2bo3b2obo$2o
bobo4bo2bo2bob2obo3bob2o3b4o$2o8bob4o2b4o5bo2bob2obo$bo2bob2o2bo3bo3bo
7bo6bo$2ob2obobo3bo4bo3b4obobobo2bo$3o4bo3b2o3b2o2b2o2bo3bo3bo2bo$b3o
8b2ob2obo2bo3b2o2bobobobo$bob2o2b2o3bo2bobob2ob5o2b4obo$4obob2ob2o2bob
obobo3bo3bobo2bo$2o4b2obobobobobobo2bo9bobobo$b2o8b2o3bo3bo2b7obo2bo3b
o$b2o2b2obob3o3b2o8bo2bobo2b4o$2o3b2o4bo3b5o3bo4bo7b3o$3o4b2o4b2o4bo2b
2obo2b2o2b2ob4o$b2o2b2o2bo3bobo3bo2bo2b4o3bo4bo$b2o2b2o2b3obob4o2b3o2b
o6bobo2bo$2o4bobo3b3o2bobobo7b2o2b2o$3obo4bo4bo10b2o3bo3bo$b2obo6b2o2b
2obob2o8bob2o$bobobo3bo6bobob3ob3ob2o3b2o$3o2b2obobob2ob2o4bo3bo4b2ob
2o$2o3b2o2b2o7bo8b4obo$bobob2o2bobob3o4bo2b4o8bo2bo$2obo3bo2b2o3bobo2b
o3bobo3b4o2bo$6o3b2o5b2obo2bo2b3o2b2o2b4o$bob3o4b4ob4o2b3o3b8obobo$bo
2bo4bob18o4bo2bo$3bo2bo6b2ob2ob2o2b2ob2obobo2bo3bo!
Code: Select all
x = 39, y = 37, rule = B3/S23
ob2ob2o2b2ob2ob2ob2ob2ob2ob2obo3b2obo$b29o2b5o$4o2b2ob3obo3bo4bo4bob5o
2bo$4o5b2o2b2o3b3o2b5obobo3b2o$bobobo3bo2b2ob5obobobo2b2o2bob3obo$b4o
8bo6bo8bob2o4bo$2o3bob3o3b2o3bobobob2o2b2o6b3o$2obo6b2o2b3o2bobo2b2o3b
ob2o2b4o$bob3obobo4bobo7bo2bo7b3o$b2o2b2o7bob3o2bo2bo3bo2bo3b2obo$2obo
bo4bo2bo2bob2obo3bob2o3b4o$2o8bob4o2b4o5bo2bob2obo$bo2bob2o2bo3bo3bo7b
o6bo$2ob2obobo3bo4bo3b4obobobo2bo$3o4bo3b2o3b2o2b2o2bo3bo3bo2bo$b3o8b
2ob2obo2bo3b2o2bobobobo$bob2o2b2o3bo2bobob2ob5o2b4obo$4obob2ob2o2bobob
obo3bo3bobo2bo$2o4b2obobobobobobo2bo9bobobo$b2o8b2o3bo3bo2b7obo2bo3bo$
b2o2b2obob3o3b2o8bo2bobo2b4o$2o3b2o4bo3b5o3bo4bo7b3o$3o4b2o4b2o4bo2b2o
bo2b2o2b2ob4o$b2o2b2o2bo3bobo3bo2bo2b4o3bo4bo$b2o2b2o2b3obob4o2b3o2bo
6bobo2bo$2o4bobo3b3o2bobobo7b2o2b2o$3obo4bo4bo10b2o3bo3bo$b2obo6b2o2b
2obob2o8bob2o$bobobo3bo6bobob3ob3ob2o3b2o$3o2b2obobob2ob2o4bo3bo4b2ob
2o$2o3b2o2b2o7bo8b4obo$bobob2o2bobob3o4bo2b4o8bo$2obo3bo2b2o3bobo2bo3b
obo3b4o2bo$6o3b2o5b2obo2bo2b3o2b2o2b4o$bob3o4b4ob4o2b3o3b8obobo$bo2bo
4bob18o4bo2bo$3bo9b2ob2ob2o2b2ob2obobo2bo!
- confocaloid
- Posts: 5479
- Joined: February 8th, 2022, 3:15 pm
- Location: learn to protect yourself against stray gliders and sparks and self-destruct mechanisms
Re: Algorithm for reversing the GoL rules
The label 'backtracking' is incorrect, unless you proceed to describe a search tree and a way of traversing it, as in https://en.wikipedia.org/wiki/Backtracking
The SAT solver software tool in use may or may not (behind the scenes) use some sort of backtracking, but whether and how it does that remains "hidden in a black box".
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Re: Algorithm for reversing the GoL rules
Hmm, interesting point. I definitely do like the term "rewinding" better than "backtracking" -- precisely because "backtracking" gets a lot of use in discussions of backtracking searches, as you point out. I'll change the tutorial header to use "rewinding" instead.confocaloid wrote: ↑December 1st, 2024, 1:01 amIt's called rewinding, rather than backtracking. As written, the tutorial section only describes how to (attempt to) rewind a given pattern a few ticks back in time.
The label 'backtracking' is incorrect...
The claim that the label is incorrect is going a little too far, though. "Backtracking" does usually refer to backtracking searches. But, like many common English words, "backtracking" has multiple possible meanings, all of which are perfectly valid in context.
"Backtrack" is occasionally used as a synonym for "rewind", with no objections from anyone up until now. It looks "rewinding" might have been a term that I came up with around 2007, in naming the "glider-rewinder" script. Before that, people were using other terms for the same concept, including "backtracking" (see David Bell's message at the end of the quote below).
I looked back through old LifeCA emails and found a few interesting examples. Dieter Leithner used the term in the 1990s to talk about "glider advancers and backtrackers" -- i.e., mechanisms that effectively advance or rewind gliders by some number of ticks. Nobody seemed to think that that usage was incorrect. It was clear from context what was meant.
Much more relevant to this thread, here's a discussion from over twenty years ago of some experimentation with rewinding small patterns. This is very much along the same lines as current experiments -- but the rewinding gets carried successfully a lot farther back in time, probably just because the starting pattern was much smaller! It looks like Karel Suhajda also initially used "decomposition" for the process of rewinding patterns, and "mist" as a synonym for "space dust".
Most of what David Bell said about the difficulty of rewinding patterns, and the tendency of predecessors to grow with each backward step, still seems very relevant today.
Historical notes:From: Karel Suhajda
Date: Tue Feb 18, 2003 6:35pm
Subject: Herschel predecessors
Nothing serious in this post. I just tried to find a predecessor with the lowest number of live cells from a randomly picked object (herschel), selected one if there were more of them and repeated the search again. I succeeded to go back 10 generations before the search exceeded my patience but I think I could get relatively far using this technique because it produces a 'mist' which seems to have great predecessor potential.
Here is also a 20-gen herschel predecessor where I used the same technique from -10th generation.Code: Select all
...**.*.*.*...... ................. *.*.*....*....... .....*.*..*.*.... *..*.**..**...... .*......**.*..*.. ...*.*.**...*.... *..*..........*.. *...**.*....*...* ..*..*.....*...*. .....**.*.*..*... ......**......*.. .....*....*.*.... ....*............ ...........*.....
I wonder if this technique can be used to 'decompose' more complicated objects. I'll try it eventually.Code: Select all
...**..*.......... ......*......*.... ...*....*.*.*..... .....*...**.*.*... .*.*.*.*..*..*.... ......*...**...*.. ......*...*..*.... ....**....*....**. **...*..**...*.... ....**.***.......* .**.****.*.*****.. ....*........*.**. .*.*..........**.. ..**..****..*...*. ....***..***....*. .....*.*.....*.... ...**......*...... .......*.......... .......*.......... .....*............
Karel Suhajda
From: David Eppstein
Date: Tue Feb 18, 2003 7:33pm
Subject: Re: Herschel predecessors
On 2/19/03 12:35 AM +0100 Karel Suhajda wrote:
> Here is also a 20-gen herschel predecessor where I used the same technique
> from -10th generation.
Well, ok, but
is a much smaller 20-gen predecessor...Code: Select all
x = 6, y = 8 4b2o$4b2o4$2obo$b3o$2bo!
--
David Eppstein
From: Karel Suhajda
Date: Wed Feb 19, 2003 11:53am
Subject: Re: Herschel predecessors
...
> Well, ok, but
>
> x = 6, y = 8
> 4b2o$4b2o4$2obo$b3o$2bo!
>
> is a much smaller 20-gen predecessor...
Nice one, indeed. But I'm sure you know that I didn't have that one in mind. Here's another 5-gen random object predecessor and I'm sure you can find a smaller one really quickly.
Five generations are not enough to make an object of this size really 'misty' but it was relatively easy again.Code: Select all
........**........ .....*..*......... .....****......... ....*.*..**....... .........**....... ........*....*.*.. ....*...**.*.*.... *...***.****...*.. *.**............*. ..............*..* .....****..*.*.*.. **....****..***... ..*......***...*.. ....*......*...... ...*.*....*....... .....*............ .........**.......
I still intend to do some experiments with this 'mist decomposition' on bigger objects but WLS starts to be quite sluggish even on simple 1-gen predecessor search when the area grows. There is no problem to find _any_ predecessor - there is problem to find a lightweight predecessor.
Karel Suhajda
From: David Bell
Date: Wed Feb 19, 2003 3:45pm
Subject: Re: Re: Herschel predecessors
Finding "mist decomposition" (better known as "space dust") predecessors of common objects is interesting in the knowledge that they exist. The main question about this to me is how far back can such predecessors be found, and how the bounding box needs to grow as you back up.
My guess is that for space dust, a cell's state is influenced at near the speed of light from previous generations, and thus the bounding box must grow at least by one or two cells around the next generation's bounding box. Maybe it grows are few cells faster than this too because the new edge cells need a few extra rows to find a consistent setting for them too.
But perhaps, this backtracking (if not periodic) must eventually stop when a region of space dust appears which is a Garden of Eden. Maybe this will eventually occur for most such backtracking attempts. A Garden of Eden is hard to find and seems rare to us now, but I think with large enough regions of space dust that they should be common and would easily be found.
Maybe it is possible to find space dust predecessors which exhibit wavelike or "spaceship" like behavior which is non-periodic and which can avoid running into a Garden of Eden, but they would be hard to find. This is [beyond] our capabilities now.
Finally, as far as actually finding [predecessors] using a search program, my goal is to find useful [predecessors] which can be synthesised. In particular, I want to construct spaceships such as Dean's smallest c/3 spaceship or my "dart" c/3 spaceship. I have tried to split them up into easier to build parts using lifesrc, but the process is difficult and hard to control.
A new search program needs to be built which looks for "nice" non-space-dust predecessors for objects. That is, the search would automatically select those [predecessors which are separated] by large gaps, or whose parts are composed of nice pieces such as gliders, blocks, and other easy to construct objects, with perhaps a small number of sparks allowed around the edge to help it along. Programming this seems hard, but it should be doable. The question is whether any objects would actually be solved this way.
BCNU,
-dbell-
From: Dave Greene
Date: Thu Feb 20, 2003 9:29am
Subject: Re: Herschel predecessors
> A Garden of Eden is hard to find and seems rare to us now, but I
> think with large enough regions of space dust that they should be
> common and would easily be found.
I'd be inclined to hunt for GoE's in patterns consisting mostly of ON cells -- I think one point of Karel's "mist predecessor" experiments is to stay as far away from GoE's as possible, by keeping the density of ON cells low. It seems as if it might be hard to find even a large misty Garden of Eden.
Are there examples of low-density GOE's out there? The only ones I've ever seen are massively unstable mostly-ON structures, usually constructed by packing together a series of small unlikely patterns. "Unlikely" in this case would mean "having relatively few predecessors" -- many 3x3 patterns with seven or eight ON cells, for example, have only [!] 7000-8000 possible 5x5 parents, and 3o$obo$3o! has the minimum with a mere 5728. Contrariwise, a blank 3x3 pattern has over five million possible parents, and a 3x3 pattern with one ON cell has roughly 500,000-700,000. So there are an awful lot of ways for "misty" patterns to have ancestors.
But I haven't carried the analysis any farther than that. There certainly have to be a huge number of GOE's lurking out there, to make up for the huge number of patterns that have more than one possible ancestor. But intuitively I'd expect all GOE's to include at least one sizeable area of mostly-ON cells.
---------------------
> In particular, I want to construct spaceships such as Dean's
> smallest c/3 spaceship or my "dart" c/3 spaceship.
This has been on my wish list recently, also. Really I want a glider construction of a weekender, but I'm not too sure I'll see one of those until I have a good several-thousand-qubit quantum computer to play with...
> A new search program needs to be built which looks for "nice" non-
> space-dust predecessors for objects. That is, the search would
> automatically select those precessors which are separated by large
> gaps, or whose parts are composed of nice pieces such as gliders,
> blocks, and other easy to construct objects, with perhaps a small
> number of sparks allowed around the edge to help it along.
I've been slowly working on a search engine based on the idea I posted in message #2020, on October 15, 2002: trying to build predecessor patterns by choosing sub-patterns from a list of "preferred" 5x5 patterns, wherever possible -- gliders and small still lifes, let's say, though the preference list could change depending on what you're searching for.
> The question is whether any objects would actually be solved this
> way.
My best guess at this point is that doing a brute-force search with a
preference list _won't_ cut the search tree enough to find anything
new. More complicated pattern-recognition code will probably be
needed, that [for example] looks for medium-sized patterns along the
expanding edge that are descendants of something hitting a beehive or
other small still life, and that actively tries to find predecessors
that split a pattern into widely-separated regions, each of which is
a smaller problem than the original pattern... Kind of a 'dr' search
engine running in reverse -- not a trivial undertaking.
But it's barely possible that a preference list that includes descendants of preferred patterns [not just the still lifes and gliders] might be enough to bias the search in the right direction in some cases, to a point where known technology could finish the construction. No way to know without trying it. I hope to have some preliminary results from a trial of the brute force method ... in about a month, at the rate I'm going.
Keep the cheer,
Dave Greene
I never finished the search program I described above. In 2015 simsim314 did a significant amount of experimentation along these lines, in a thread about "parallelizable tile-based rewinding", but this was before SAT solvers were commonplace, and the experiments quickly got very time-consuming without producing any definitely useful results.
Also, notice how wrong I was, above, about the likelihood of finding a weekender synthesis! But I guess I wasn't necessarily wrong about the likelihood of finding a weekender synthesis with a tile-based rewinding search program.
Re: Algorithm for reversing the GoL rules
Context: I thought there was a page in LifeWiki userspace listing how often each INT transition appears during the R-pentomino's evolution, presumably stopping when it settles so that we don't get infinite numbers of blocks, gliders, etc. affecting things. No such page exists, though.
[hr]hotdogPi wrote: ↑November 22nd, 2024, 9:30 amI might not have been clear enough, especially since the page I thought existed didn't.
Here's an an example from part of what I thought the page looked like, with made up numbers:
S3q — 31415
S3y — 9265
D4a — 35897
D4c — 932
D4e — 3846
D4i — 26433
The R-pentomino that I thought the page had was just to get a representative sample; the exact pattern didn't matter, and I used what I thought already existed.
When searching for a 1-tick predecessor of a pattern, a live cell with "4a" neighbors would have a "cost" of 1/35897, which is low because it's more common, while a live cell with "4c" neighbors would have a much higher cost of 1/932. A predecessor-finding search would therefore try to have fewer of the latter, since it would be more difficult to back it up further.
Dead cells that touch at least one live cell would also contribute to the total. For example, A1e and A1c on the edge of the pattern would contribute to the total, but very little, since they would have high frequency counts.
Starting with a 10-tick predecessor of "NOT EASY", you can shave some cells off. Some of them produce sparks that last past 10 generations, but this is likely easily fixable; there are probably about 20 easily toggleable cells on the left edge, and just based on statistics, it's likely that many of the 2^20 combinations will die out before 10 generations.
Code: Select all
x = 39, y = 37, rule = DoubleB3S23
B.2B.2B2.2B.CB.CB.CBACB.2C.CB.C3.2B.B$.5B3CB20C2.5B$4B2.2C.3C.C3.C4.C
4.C.4CB2.B.B$4B5.2C2.2C3.3C2.5C.C.C3.2B$.B.C.C3.C2.2C.5C.C.C.C2.2C2.C
.C2B.B$.4C8.C6.C8.C.2C4.B$2C3.C.3C3.2C3.C.C.C.2C2.2C6.C2B$2B.C6.2C2.
3C2.C.C2.2C3.C.2C2.2C2B$.B.3C.C.C4.C.C7.C2.C7.2CB$.BC2.2C7.C.3C2.C2.C
3.C2.C3.2C.B$BC.C.C4.C2.C2.C.2C.C3.C.2C3.4C$BC8.C.4C2.4C5.C2.C.2C.C$.
C2.C.2C2.C3.C3.C7.C6.C$BC.2C.C.C3.C4.C3.4C.C.C.C2.C$2BC4.C3.2C3.2C2.
2C2.C3.C3.C2.C$.B2C8.2C.2C.C2.C3.2C2.C.C.C.C2.B$.B.2C2.2C3.C2.C.C.2C.
5C2.4C.C3.B$B3C.C.2C.2C2.C.C.C.C3.C3.C.C2.C$BC4.2C.C.C.C.C.C.C2.C9.C.
C.C$ABC8.2C3.C3.C2.7C.C2.C3.B$.BC2.2C.C.3C3.2C8.C2.C.C2.4C$BC3.2C4.C
3.5C3.C4.C7.2CB$B2C4.2C4.2C4.C2.2C.C2.2C2.2C.3CB$.2C2.2C2.C3.C.C3.C2.
C2.4C3.C4.B$.2C2.2C2.3C.C.4C2.3C2.C6.C.C2.B$BC4.C.C3.3C2.C.C.C7.2C2.
2C$B2C.C4.C4.C10.2C3.C3.C$.2C.C6.2C2.2C.C.2C8.C.2C$.B.C.C3.C6.C.C.3C.
3C.2C3.2C$2BC2.2C.C.C.2C.2C4.C3.C4.2C.2C3.B$2B3.2C2.2C7.C8.4C.C$.B.C.
2C2.C.C.3C4.C2.4C8.B2.B$2B.C3.C2.2C3.C.C2.C3.C.C3.4C2.B$2B4C3.2C5.2C.
C2.C2.3C2.2C2.C3B$.B.3C4.4C.4C2.3C3.6C2B.B.B$.B2.C4.B.5C3B3CB4C2B4.B
2.B$3.B2.B6.2B.2B.2B2.2B.2B.B.B2.B3.B!
Periods discovered:
All evens up to 128 except 52,58,78,82,92,94,98,104,118,122
5-15,㉕-㉛,㉟㊺,51,63,65,73,75
1㊳㊵㊹㊼㊽,54,56,72,74,80,90,92
217,240,300,486,576
Guns: 20,21,32,54,55,57,114,117,124,126
SKOPs: 32,74,76,102,196
- confocaloid
- Posts: 5479
- Joined: February 8th, 2022, 3:15 pm
- Location: learn to protect yourself against stray gliders and sparks and self-destruct mechanisms
Re: Algorithm for reversing the GoL rules
The last two links (replies by vilc and by Goldtiger997, about "growing stable regions") explain what may be the most promising idea. That discussion focused on "stable-to-stable" synthesis components, but the same heuristic of preferring regions that look like parts of still lives could work for rewinding other patterns.confocaloid wrote: ↑November 21st, 2024, 12:36 pmRelated discussions:hotdogPi wrote: ↑November 21st, 2024, 12:32 pmThis has nothing to do with OCA; I'm speaking about Life only. The idea is that we have tools that find predecessors, but we don't currently have any optimized for "is a plausible way to get there from earlier configurations, so that it can easily be backed up further".
- viewtopic.php?f=2&t=3305&p=57416#p57416 how about a sir robin synthesis?
- viewtopic.php?p=105378#p105378 Re: The Past and Future of CGOL
- viewtopic.php?p=192057#p192057 Re: Incomplete search patterns - try to complete
- viewtopic.php?p=192062#p192062 Re: Incomplete search patterns - try to complete
Which of the following two reactions is more likely to be re-found completely automatically by a future script, using a few hundreds of invocations of a SAT solver? Would that conversion from the 14-bitter to the 22-bitter be "harder" or "easier" to rediscover automatically, compared to rewinding that 16-bitter back to those four gliders?
Code: Select all
x = 49, y = 25, rule = B3/S23
47bo$46bo$46b3o18$obo10bo$b2o9b2o$bo6bo3bobo$8b2o$7bobo!
#C [[ THEME Catagolue ZOOM 4 ]]
Code: Select all
x = 117, y = 110, rule = B3/S23
114bo$114bobo$114b2o4$9bo99bo$10bo98bobo$bo6b3o98b2o$2bo$3o2$67bo$67bo
bo$67b2o5$14bo48bo$12bobo48bobo$13b2o48b2o24bobo$89b2o$83bo6bo$2bo78b
2o$3bo78b2o$b3o21$72bo$70bobo$71b2o2$106bo$46b2o58bobo$46bo59b2o$47bo$
44bo3bobo$43bobo3b2o$43bobo$44bo2$47b2o$39b2o2b2o2bo$39b2o3bo3bo2b2o$
43bo3b2o2bobo$43b2o7bo$40bo$39bobo$39bo2bo$40b2o2bo$41bob2o$41bo$40b2o
5$81b2o$80b2o$82bo5$82b3o$82bo$83bo$102b2o$101b2o$103bo6$88bo$87b2o$
87bobo2$80b2o$80bobo$80bo2$18b2o65b2o$19b2o59bo3b2o$18bo60b2o5bo$79bob
o2$18bo$18b2o$17bobo!
#C [[ THEME Catagolue ZOOM 4 ]]
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Re: Algorithm for reversing the GoL rules
Some related lines of research that might also be interesting:confocaloid wrote: ↑December 1st, 2024, 9:54 amThe last two links (replies by vilc and by Goldtiger997, about "growing stable regions") explain what may be the most promising idea. That discussion focused on "stable-to-stable" synthesis components, but the same heuristic of preferring regions that look like parts of still lives could work for rewinding other patterns.
1) Rewind a pattern in such a way that cells in the center remain OFF, and the empty patch grows over time as quickly as possible.
It's not clear if this is really workable. A ring of space dust is probably much easier to find predecessors for, than a solid blob of space dust. But the reason that it's easier would be because there's more surface area in a ring -- and to use that surface area you'd probably have to shrink the empty patch rather than continuing to grow it. Seems like it would be very hard to keep the empty patch growing for any length of (backward) time.
Still, possibly an approach like this could help set records, by giving a few more ticks of workable rewinding before we get back to a huge solid blob of space dust (that is likely to contain a GoE).
2) Rewind a pattern in a way that attempts to break it up into multiple separate blobs separated by a good amount of empty space.
3) Rewind a pattern in a way that's biased toward movement in some particular direction -- e.g., set up searches looking for ways to make the rightmost column permanently empty before some time -T(1), then the next rightmost column permanently empty before time -T(2), etc.
Here again, most likely a predecessor that can "throw" a pattern sideways, or part of a pattern ... will probably end up being bigger and/or more space-dusty than a minimal ancestor without those constraints, so maybe it won't really help with the goal of rewinding an arbitrary pattern as far as possible... not that that's the only goal of rewinding experiments, it's just the one I'm thinking about the most at the moment.
The NOT EASY predecessor challenge pretty much assumes that nobody is going to solve the problem of rewinding arbitrary patterns into clean glider syntheses, any time soon... If a glider synthesis of that specific NOT EASY pattern shows up by the end of 2024, I'll be happy to send out a check for $137 instead of $1.37.
I really like the idea of generating a lot of predecessors at each stage of a rewinding search, and scoring each one somehow according to how likely it is to be further rewindable. Not clear yet on whether there's some good way to tell a SAT solver how to bias its results toward "better" predecessors, or whether it will work better to have the SAT solver generate a series of results, and then figure out the score of each one -- maybe add constraints and re-run some searches to avoid the lowest-scoring sections?hotdogPi wrote: ↑December 1st, 2024, 9:52 amWhen searching for a 1-tick predecessor of a pattern, a live cell with "4a" neighbors would have a "cost" of 1/35897, which is low because it's more common, while a live cell with "4c" neighbors would have a much higher cost of 1/932. A predecessor-finding search would therefore try to have fewer of the latter, since it would be more difficult to back it up further.
Ideas along these lines have been "in the air" for quite a while. I can find wild hand-waving mentions of this kind of thing as far back as October 2002... just went back and added one more message to the end of the quoted LifeCA discussion above, along with a link to simsim314's 2015 experiments involving "parallelizable tile-based rewinding".
Re: Algorithm for reversing the GoL rules
Welcome to our Community !
Reversing CGol looks to be a subject whose time has come -
mainly due to advances in Hardware, in Software and in Thinking about the conundrum.
As you can see, this is the right place to be figuring out how to run CGoL backwards
viewtopic.php?f=12&t=6521&p=196614#p196614
https://youtu.be/g8pjrVbdafY
RLE from the above video
Code: Select all
x = 37, y = 33, rule = B3/S23
13bob2o2b2o2b2o2b2obo$5bob2ob2o2b16o$3bo2b8o2bob2ob2obo2b3obo$bo2b2obo
bo3b2ob2obo4bobo2b2o3bo$2b4o2bo3b2o2bobobo2b2o4b2obo$b2obo3b4ob2o4b2o
5bob3o5bo$b2ob2obobo2bo4b2o3bobo8bo$2bo2bo6bo2bob3o2bobo2bo2b2o$ob4ob
2obobo2bo2bob2o7bob2obo$bob2o3b5o4bobo2bo2bobo2bo5bo$2o7bo3b4o4b2o7b3o
$2o2bo2bo3bobo3bob3o4b4ob2o$b3o5bo2b2obo3bo4bo2bobo2bobo$b3obo2b3o2bob
o2bo2bo2bo3bo3bobo$2o3b3o4bo5b2o3bob2obo2b2o$3obo2bo2b2o2b2o2bo4bo3bo$
b3obo2bo3b3o2bob3o4b3ob5o$3obo2bo2b2o2b2o2bo4bo3bo$2o3b3o4bo5b2o3bob2o
bo2b2o$b3obo2b3o2bobo2bo2bo2bo3bo3bobo$b3o5bo2b2obo3bo4bo2bobo2bobo$2o
2bo2bo3bobo3bob3o4b4ob2o$2o7bo3b4o4b2o7b3o$bob2o3b5o4bobo2bo2bobo2bo5b
o$ob4ob2obobo2bo2bob2o7bob2obo$2bo2bo6bo2bob3o2bobo2bo2b2o$b2ob2obobo
2bo4b2o3bobo8bo$b2obo3b4ob2o4b2o5bob3o5bo$2b4o2bo3b2o2bobobo2b2o4b2obo
$bo2b2obobo3b2ob2obo4bobo2b2o3bo$3bo2b8o2bob2ob2obo2b3obo$5bob2ob2o2b
16o$13bob2o2b2o2b2o2b2obo!
- autonomic writing
forFUN : http://gol.jct.onl
ArtGallery : http://cgolart.onfav.net
VideoWS : http://conway.life
- confocaloid
- Posts: 5479
- Joined: February 8th, 2022, 3:15 pm
- Location: learn to protect yourself against stray gliders and sparks and self-destruct mechanisms
Re: Algorithm for reversing the GoL rules
That looks somewhat unnecessary, given that the author of the thread was last active over two years ago.
I'd like to interject to warn against any attempts to twist replies/feedback by other people. Please speak for yourself only.
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Re: Algorithm for reversing the GoL rules
Only a little over 16 hours to go before the deadline. Any takers? If I'm the one who has posted the longest rewind of the "NOT EASY" pattern, then I don't have to send $1.37 anywhere, of course.dvgrn wrote: ↑November 22nd, 2024, 6:21 pmIn case an actual contest might make the question more interesting, I'll send a check for $1.37 on request, to whoever has posted a great^N grandparent of this pattern, with the highest value of N, as of the end of 2024 (everywhere in the world). If a tie break is needed, lower population wins, then smallest minimum covering polyplet area.
I'm gradually getting to be a little bit less of a newbie at Logic Life Searching, but could still use a lot of help and advice.
For example, I've tried making rewinds with stable centers, and rewinds with empty centers -- but I'm having a hard time to get those centers to keep growing after the first few ticks:
Code: Select all
x = 20, y = 20, rule = B3/S23
6bo8bo$2o2bo2bob2obobo3bo$2bob2o9b2obo$2o5bobo6bo$7bo3bobobo3bo$2bo2b
2o2bo3b4obo$3bo5bob3o3bo$3bobob2o6bobo$b3o2bo5bo2bob2o$o2bo10bob2o$3b
3o9bobo$3bo3bo4bobob2o$obo2b3o2b5o3b2o$o2b2o5bo$9bobo2b2obo$2bobob2o2b
o5b4o$o2b3obobobobobobo$o4b2ob4o2bob2o$4bo5bobo3bo$obo3bo6bo4bo!
(?)
Is there an easy way to limit the population in a given generation of one of these rewinding searches?
Re: Algorithm for reversing the GoL rules
Code: Select all
x = 16, y = 13, rule = B3/S23
3b2o2b2o2b2o$2bobo3bo2bobo$bo12bo$o4bo9bo$2o3bo8b2o$5bo$8b3o$5bo$2o3b
o8b2o$o4bo9bo$bo12bo$2bobo3bo2bobo$3b2o2b2o2b2o!
I spent the day today trying to rewind my own arbitrary "NOT EASY" challenge pattern, which is 16x16 rather than 16x13.
Getting to T = -21 for that pattern would be more of a challenge for me; I think I might be able to do it in about a week of very careful manual searching, or about the same amount of time writing code to build search templates, and then letting searches run automatically for the rest of the week.
Here's my evidence that a day or a week is about the right amount of time needed to set that T=-21 record. Without having to run any particularly long searches, I was able to rewind back to a 44x44 pattern for T=-15:
Code: Select all
x = 44, y = 44, rule = B3/S23
3bo5bobo8b2obob2obo6b2ob2o2b2o$o3b2obobo3b2o4b4ob3obobo4b2ob6o$8b7o4b
5obo6bo3bobo2b2o$ob2o2b3obo2bob4o7b2obobo5bo5bo$obob3o3bobo2bo5b2o8bo
2bobo$bo2bobo5bo5b2obob2obo2bobo4b2o5bo$7b3obo3bo2b2obob3o5b3o2b3o2bo$
2ob2o7b2ob2o2b2o2bo2b2o2bo4bobo3bobo$bo4bobo3b2obobo2bobo4bobobo2b2o3b
o2bo$o2b2o4bo3b2o2bo2b3obo3bobo6bo4b2o$bo3bo4bo3b2o3bo4b2ob2o2bobobo2b
o2bo$bo2b2o3bobo3b2ob2obobob4o4bo5bobo$2bo2bobob2o2b2o2b2obobo3bo3b4o
3bo3bobo$2bo2b2ob2ob2o2bo4bobo4bo5bob2o3bo$ob2obo4bo2bo2bob3o2b2o2bo2b
2o2bo3bo2bo$3bo2bo3bob2ob3ob3o3bobo2bobo2bobob2obo$o3bo2b2o5bo2bo8b3o
2bo5b2obo2bo$2b2o5b2o3bo3b2obo2bo4b3obo3bo2bo$3bobob2ob2o2bo5bo2bob2ob
o2b2ob2obo2bo$7obobob4o2b3o2b4obo3bobo3b2o2bo$b2o9b2obo3b2o8bo2bo3bo6b
o$2bo2b2obobo5bo5bo3b2obob4obobobo$bobobo2bo2bo4b2o3b4obob4o3bo2bob2ob
o$5bob3o2b5ob2o3bo2bo4b3obobo3b2o$2b6o2bob2o2bo2bobo2bobobo3bob2ob2o2b
o$bobo8bobobo3b2obo4b2o6bob2ob2o$bo3b3ob2obobob3o2b2ob2obo4bo4bobo2b2o
$3bo7bo4bo4bobo3bob2o2b2o6b3o$bo3b2o3bo2bo2b2obo2bob2ob4o2b2o3bob3o$2b
2ob4o4bo2b3obo3bo2bo2b2o2bo4b2o2bo$ob3obo2bo2b2o8bo6b3o5b2o2b2o$o7bo2b
2o2bo2bobob2obobo6b3o4b2o$2b3obo2bobob2o2bo2bob3o4bob2o3bob2obo$3bob3o
bo4b2obobo5bo3b2o3bob2o3b3o$2b2o2bo5bo2bob3o2bobo2b2obo3b2o5b3o$ob2ob
2ob3ob2o3b3obob3o7b4o2bo2bo$o5bo3b3o4bo4bo2bob2o2bobo2b5obo$bo2bo4bo2b
o3bo5bo4b2ob2o2bo5bo$2b2obo3bo2bob2o2bobo7b2obo2bo2bobobo$obo2bo5bob3o
3bo3b2o5bo2b3obo5bo$4bo2b5o8bobobo2b2obo3b2o2bo3b2o$2b2o2bo2b2o2b3ob2o
6bo4bobobo3b5o$bo3b2o2b3o2bo2bo2b2obo2bo6b3obo2bo2bo$bo2bo2bobo6bo7bo
6b2ob2obobobo!
Somewhere around 40x40 the odds seemed to go up rather quickly, that any given predecessor found by LSS would be a Garden of Eden.
However, it seemed like it was possible to decrease the odds of generating GoEs at least somewhat, by constraining each search to somewhere close to the smallest circular area that contained solutions. It was important not to allow LLS to fill in around the edges with big instant-death areas -- and usually it turned out that there were alternatives to those that produced the same results, if the template was adjusted to force LLS to find them.
- confocaloid
- Posts: 5479
- Joined: February 8th, 2022, 3:15 pm
- Location: learn to protect yourself against stray gliders and sparks and self-destruct mechanisms
Re: Algorithm for reversing the GoL rules
For example, suppose someone manages to discover a Sir Robin predecessor that looks like this (only larger and with more gliders), if that happens then the game is mostly over:
Code: Select all
x = 126, y = 80, rule = B3/S23
50bo$51bo$49b3o$83bo$84bo$82b3o3$31bo3bo3bo3bo11bo3bo3bo3bo$30bobobobo
bobobobo9bobobobobobobobo$19bo11bo3bo3bo3bo11bo3bo3bo3bo$18bo$18b3o6bo
3bo7bo3bo3bo3bo3bo15bo3bo11bo3bo3bo3bo11bo$26bobobobo5bobobobobobobobo
bobo13bobobobo9bobobobobobobobo9bobo$27bo3bo7bo3bo3bo3bo3bo15bo3bo11bo
3bo3bo3bo11bo2$27bo3bo3bo3bo7bo3bo3bo3bo7bo7bo3bo3bo3bo3bo7bo3bo3bo3bo
11bobo$26bobobobobobobobo5bobobobobobobobo5bobo5bobobobobobobobobobo5b
obobobobobobobo10b2o$27bo3bo3bo3bo7bo3bo3bo3bo7bo7bo3bo3bo3bo3bo7bo3bo
3bo3bo12bo2$27bo3bo3bo3bo3bo3bo3bo7bo3bo7bo3bo3bo3bo3bo3bo3bo3bo3bo3bo
3bo$26bobobobobobobobobobobobobobo5bobobobo5bobobobobobobobobobobobobo
bobobobobobobobobo$27bo3bo3bo3bo3bo3bo3bo7bo3bo7bo3bo3bo3bo3bo3bo3bo3b
o3bo3bo3bo2$7bo3bo3bo3bo7bo11bo3bo7bo3bo3bo3bo3bo7bo3bo3bo3bo3bo3bo3bo
3bo3bo3bo$6bobobobobobobobo5bobo9bobobobo5bobobobobobobobobobo5bobobob
obobobobobobobobobobobobobobobobo$7bo3bo3bo3bo7bo11bo3bo7bo3bo3bo3bo3b
o7bo3bo3bo3bo3bo3bo3bo3bo3bo3bo2$7bo3bo7bo3bo7bo3bo7bo3bo7bo7bo3bo3bo
7bo7bo3bo7bo3bo$6bobobobo5bobobobo5bobobobo5bobobobo5bobo5bobobobobobo
5bobo5bobobobo5bobobobo$7bo3bo7bo3bo7bo3bo7bo3bo7bo7bo3bo3bo7bo7bo3bo
7bo3bo2$11bo3bo3bo3bo3bo3bo7bo3bo3bo3bo3bo7bo11bo3bo3bo7bo3bo7bo3bo$
10bobobobobobobobobobobobo5bobobobobobobobobobo5bobo9bobobobobobo5bobo
bobo5bobobobo$11bo3bo3bo3bo3bo3bo7bo3bo3bo3bo3bo7bo11bo3bo3bo7bo3bo7bo
3bo2$7bo3bo3bo3bo3bo3bo3bo3bo3bo7bo15bo3bo7bo7bo3bo3bo3bo$6bobobobobob
obobobobobobobobobobobobo5bobo13bobobobo5bobo5bobobobobobobobo$7bo3bo
3bo3bo3bo3bo3bo3bo3bo7bo15bo3bo7bo7bo3bo3bo3bo2$7bo3bo7bo3bo7bo15bo7bo
7bo15bo3bo7bo3bo$6bobobobo5bobobobo5bobo13bobo5bobo5bobo13bobobobo5bob
obobo$7bo3bo7bo3bo7bo15bo7bo7bo15bo3bo7bo3bo2$11bo3bo7bo3bo11bo19bo3bo
3bo3bo7bo3bo3bo3bo$10bobobobo5bobobobo9bobo17bobobobobobobobo5bobobobo
bobobobo$11bo3bo7bo3bo11bo19bo3bo3bo3bo7bo3bo3bo3bo$116bo$15bo11bo3bo
11bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo19b2o$14bobo9bobobobo9bobob
obobobobobobobobobobobobobobobobobobobobobobobobobo18bobo$15bo11bo3bo
11bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo2$15bo3bo3bo3bo7bo11bo15bo
3bo11bo3bo7bo3bo$14bobobobobobobobo5bobo9bobo13bobobobo9bobobobo5bobob
obo$15bo3bo3bo3bo7bo11bo15bo3bo11bo3bo7bo3bo$bo$b2o12bo3bo3bo3bo3bo3bo
7bo3bo3bo3bo3bo3bo11bo3bo7bo3bo$obo11bobobobobobobobobobobobo5bobobobo
bobobobobobobobo9bobobobo5bobobobo$15bo3bo3bo3bo3bo3bo7bo3bo3bo3bo3bo
3bo11bo3bo7bo3bo2$15bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo$14bobobo
bobobobobobobobobobobobobobobobobobobobobobobobobo$15bo3bo3bo3bo3bo3bo
3bo3bo3bo3bo3bo3bo3bo3bo2$23bo3bo7bo3bo11bo3bo7bo3bo$22bobobobo5bobobo
bo9bobobobo5bobobobo$23bo3bo7bo3bo11bo3bo7bo3bo2$19bo3bo7bo3bo11bo3bo
7bo3bo$18bobobobo5bobobobo9bobobobo5bobobobo$19bo3bo7bo3bo11bo3bo7bo3b
o2$81b3o$81bo$82bo3$19bo31bo$19b2o30b2o$18bobo29bobo!
The heuristic of "growing stable regions" may be viewed as an approximation of this, with the assumption that the resulting still-life will end up being glider-constructible (which may not be the case, there are non-constructible still-life patterns).
Hence a related question:
What are known glider-constructible classes of dense still-life patterns that can be defined solely via local restrictions/constraints (i.e. without "long-range" restrictions on the pattern) and allow packing a high amount of information into a small region?
confocaloid wrote: ↑December 1st, 2024, 9:54 amThe last two links (replies by vilc and by Goldtiger997, about "growing stable regions") explain what may be the most promising idea. That discussion focused on "stable-to-stable" synthesis components, but the same heuristic of preferring regions that look like parts of still lives could work for rewinding other patterns.confocaloid wrote: ↑November 21st, 2024, 12:36 pmRelated discussions:hotdogPi wrote: ↑November 21st, 2024, 12:32 pmThis has nothing to do with OCA; I'm speaking about Life only. The idea is that we have tools that find predecessors, but we don't currently have any optimized for "is a plausible way to get there from earlier configurations, so that it can easily be backed up further".
- viewtopic.php?f=2&t=3305&p=57416#p57416 how about a sir robin synthesis?
- viewtopic.php?p=105378#p105378 Re: The Past and Future of CGOL
- viewtopic.php?p=192057#p192057 Re: Incomplete search patterns - try to complete
- viewtopic.php?p=192062#p192062 Re: Incomplete search patterns - try to complete
[...]
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.