ConwayLife.com

Forums for Conway's Game of Life
https://conwaylife.com/forums/

Algorithm for reversing the GoL rules

https://conwaylife.com/forums/viewtopic.php?t=5569

Page 1 of 1

Algorithm for reversing the GoL rules

Posted: February 18th, 2022, 3:02 am
by IncJSG
Hello there,

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

Posted: February 18th, 2022, 7:08 am
by hotdogPi
GoL can't be reversed. There are too many options that converge to the same patterns.

Re: Algorithm for reversing the GoL rules

Posted: February 18th, 2022, 7:32 am
by dvgrn
hotdogPi wrote: February 18th, 2022, 7:08 am GoL can't be reversed. There are too many options that converge to the same patterns.
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.

Re: Algorithm for reversing the GoL rules

Posted: February 18th, 2022, 8:19 am
by HartmutHolzwart
In view of the recent development: For a pattern to have many predecessors makes it more likely that one of them is glider constructible. So one heuristic would be to try to stabilize the center into a still life with many predecessors and try to grow that core with every generation, while keeping some minimum number of predecessor limit for sub patches of a certain size. The outcome would be a constructible still life surrounded by some sparks.

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

Posted: February 18th, 2022, 9:35 am
by IncJSG
dvgrn wrote: February 18th, 2022, 7:32 am
hotdogPi wrote: February 18th, 2022, 7:08 am GoL can't be reversed. There are too many options that converge to the same patterns.
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.
Thanks, this is interesting.

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

Posted: February 18th, 2022, 10:40 am
by dvgrn
IncJSG wrote: February 18th, 2022, 9:35 amI'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.
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

Posted: February 18th, 2022, 12:50 pm
by Macbi
dvgrn wrote: February 18th, 2022, 10:40 am
IncJSG wrote: February 18th, 2022, 9:35 amI'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.
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.)
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.
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
The pattern describes cells separated by commas. The line of commas in the middle separates the two generations of the search pattern. The first generation is full of *s, which represent an unknown cell. The second generation is full of 0s and 1s, which represent dead and alive cells respectively. I've included a margin of two dead cells around the 16 by 16 soup, so that the predecessor might be slightly larger than the soup. One easy way to make this search pattern would be to create the soup in Golly and then select it (with the margin) and run this csv_from_selection.py script:

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")
Then open up the pattern.csv file in Excel and add columns above the existing rows and fill them with *s in a rectangle of the same size. Leave a blank row between the two generations. When you save a file in Excel with the .csv filetype it will save it in csv (comma separated value) format, which is what we want. (The line of commas in the above example is an artefact of Excel giving every row the same width. LLS would work equally well if this line was blank.)
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
7) The output should look something like

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!
8) <- Sunglasses dude.
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

Posted: February 18th, 2022, 4:11 pm
by IncJSG
Thanks a lot for those valuable explanations.
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

Posted: February 18th, 2022, 6:18 pm
by dvgrn
Macbi wrote: February 18th, 2022, 12:50 pm [awesome walkthrough]
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
All of the kissat tests succeeded for me, but there was one rather weird compilation message:

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’
Still got the executable, though!

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
to make sure -- and if putting in "python3" produces "Module not found" type errors, and putting in "python2" doesn't, then you don't have the development branch. Another clue is that the "search_patterns" folder doesn't show up.

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 think if you're getting that, it's just another sign that you need to figure out how to switch over to the development branch.

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!
4) On my first try to find a sample predecessor, I got

Code: Select all

Getting search pattern...
Done

Preprocessing...
    Unsatisfiability proved in preprocessing
Done

Time taken: 0 seconds

Unsatisfiable
... which didn't make a whole lot of sense, especially after I tried the exact pattern quoted above.

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

Posted: November 30th, 2024, 6:13 pm
by dvgrn
EDIT 12/29/2024: changed all uses of "backtracking" below to "rewinding", because as confocaloid mentioned, "backtracking search" usually means something else.

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)
But then we need another script to generate a "hollowed-out" predecessor region of the right size, to complete the LLS search pattern. Here's something that works on the output of the above script. I.e., a rectangular area of comma-separated values is presumed to be in the clipboard when the script runs.

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)
ChatGPT wrote almost this entire second script for me. I just added the last six lines. Here is ChatGPT's highly successful effort to port these two scripts to Lua:

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.")
LUA -- hollowing out the center of a predecessor rectangle, with user-configurable margins:

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])
If anyone wants to try a few rewinding searches and provide some feedback as to what doesn't work or what didn't make sense on the first try, that will probably help me figure out what additional detail I could quickly add to the tutorial.

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

Posted: November 30th, 2024, 6:36 pm
by hotdogPi
Sometimes 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.

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!

Re: Algorithm for reversing the GoL rules

Posted: December 1st, 2024, 12:21 am
by dvgrn
hotdogPi wrote: November 30th, 2024, 6:36 pm Sometimes 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.
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.

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!
But one advantage of patterns that expand quickly is that it's more likely that modifications can be made around the edges, that will cause only minor temporary differences -- like removing some of the dot sparks in the above pattern:

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!

Re: Algorithm for reversing the GoL rules

Posted: December 1st, 2024, 1:01 am
by confocaloid
It'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, 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".

Re: Algorithm for reversing the GoL rules

Posted: December 1st, 2024, 8:23 am
by dvgrn
confocaloid wrote: December 1st, 2024, 1:01 am It'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...
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.

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.
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.

Code: Select all

 ...**.*.*.*......
 .................
 *.*.*....*.......
 .....*.*..*.*....
 *..*.**..**......
 .*......**.*..*..
 ...*.*.**...*....
 *..*..........*..
 *...**.*....*...*
 ..*..*.....*...*.
 .....**.*.*..*...
 ......**......*..
 .....*....*.*....
 ....*............
 ...........*.....
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.

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

Code: Select all

x = 6, y = 8
4b2o$4b2o4$2obo$b3o$2bo!
is a much smaller 20-gen predecessor...
--
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.

Code: Select all

........**........
 .....*..*.........
 .....****.........
 ....*.*..**.......
 .........**.......
 ........*....*.*..
 ....*...**.*.*....
 *...***.****...*..
 *.**............*.
 ..............*..*
 .....****..*.*.*..
 **....****..***...
 ..*......***...*..
 ....*......*......
 ...*.*....*.......
 .....*............
 .........**.......
Five generations are not enough to make an object of this size really 'misty' but it was relatively easy again.

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
Historical notes:

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

Posted: December 1st, 2024, 9:52 am
by hotdogPi
I previously posted this in "thread for advanced questions" because I didn't know that this thread existed at the time.

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.
hotdogPi wrote: November 22nd, 2024, 9:30 am I 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.
[hr]

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!

Re: Algorithm for reversing the GoL rules

Posted: December 1st, 2024, 9:54 am
by confocaloid
confocaloid wrote: November 21st, 2024, 12:36 pm
hotdogPi wrote: November 21st, 2024, 12:32 pm This 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".
Related discussions:
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.

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 ]]

Re: Algorithm for reversing the GoL rules

Posted: December 1st, 2024, 11:47 am
by dvgrn
confocaloid wrote: December 1st, 2024, 9:54 am 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.
Some related lines of research that might also be interesting:

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.
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.
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?

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

Posted: December 2nd, 2024, 3:22 pm
by otismo
Greetings IncJSG !

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!
Cheers !

Re: Algorithm for reversing the GoL rules

Posted: December 2nd, 2024, 3:32 pm
by confocaloid
otismo wrote: December 2nd, 2024, 3:22 pmGreetings IncJSG ! [...]
That looks somewhat unnecessary, given that the author of the thread was last active over two years ago.
otismo wrote: December 2nd, 2024, 3:22 pm [...]
especially if Confocaloid says so.
[...]
I'd like to interject to warn against any attempts to twist replies/feedback by other people. Please speak for yourself only.

Re: Algorithm for reversing the GoL rules

Posted: December 31st, 2024, 3:47 pm
by dvgrn
dvgrn wrote: November 22nd, 2024, 6:21 pm In 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.
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.

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!
And I'd like to somehow use LLS to implement some ideas along the lines of hotdogPi's -- add more clauses to outlaw the appearance of very unlikely and "Garden-of-Eden-ish" configurations, once I figure out what those should be. But it seems like I'll have to dig pretty deep into the preprocessing code to do anything like that.

(?)

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

Posted: December 31st, 2024, 11:34 pm
by dvgrn
With what I understand now, my guess is that I could use Logic Life Search to improve on AlphaPhoenix's record, without inventing any new tricks, in about a day. That would mean finding at least a 20-tick space-dust predecessor of this specific pattern

Code: Select all

x = 16, y = 13, rule = B3/S23
3b2o2b2o2b2o$2bobo3bo2bobo$bo12bo$o4bo9bo$2o3bo8b2o$5bo$8b3o$5bo$2o3b
o8b2o$o4bo9bo$bo12bo$2bobo3bo2bobo$3b2o2b2o2b2o!
(without trying to cheat in the obvious way, finding unlimited predecessors via a glider synthesis).

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!
Most of the searches that I ran were ones that finished in a single-digit number of minutes (whether they returned a result or came back with UNSAT).

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.

Re: Algorithm for reversing the GoL rules

Posted: January 10th, 2025, 11:38 pm
by confocaloid
One general idea is "find a general way to rewind every possible pattern with certain properties".

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!
Every tub can be present or absent, without affecting glider-constructibility (I believe).

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 am
confocaloid wrote: November 21st, 2024, 12:36 pm
hotdogPi wrote: November 21st, 2024, 12:32 pm This 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".
Related discussions:
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.
[...]

Re: Algorithm for reversing the GoL rules

Posted: August 1st, 2026, 4:48 am
by mystical
I've been working on implementing an approach to predecessor searching that AFAIK hasn't been tried before, and also I've trying to use this with deep learning to try and choose 'good' predecessors. My experiments were ultimately not as successful as I would've liked, resulting in modest, but not groundbreaking improvements.

The main algorithm's basic idea is to repeatedly split the board in question along the longer side into 2 parts recursively, creating a binary tree like data structure. For example, a 4x4 board would be divided as

Code: Select all

x = 49, y = 19, rule = LifeSuper
.M2.M2.M2.M21.C5.2H5.2H$14.C5.L.L2.L.L3.C6.2H5.2H$.M2.M2.M2.M2.C6.L.L
2.L.L2.6C$12.6C12.6C2.2H5.2H$12.6C2.L.L2.L.L3.C6.2H5.2H$.M2.M2.M2.M2.
C6.L.L2.L.L4.C$14.C23.2C5.2C$.M2.M2.M2.M26.4C3.4C$36.C.2C.C.C.2C.C$
38.2C5.2C$38.2C5.2C$38.2C5.2C2$33.C$24.4A6.C3.2F5.2F$24.4A2.6C2.2F5.
2F$24.4A2.6C2.2F5.2F$24.4A6.C3.2F5.2F$33.C!
We start with the smallest pieces (i.e. 1 × 1 ) and try to enumerate all possible predecessors of this piece among all 3x3 pasts. Once this is done, we begin to merge nodes to calculate the possibilities at higher levels of the tree (so a k × k node would contain all ( k + 2 ) × ( k + 2 ) boards whose core evolves to the desired k × k node).

This results in a huge number of boards to keep track of, which means some of the boards have to be culled to keep the memory usage under control. And information cannot flow from one cell to another till their least common ancestor. To mitigate this issue, the program tries to cull all the boards at each layer of the tree, which it can definitively prove aren’t part of any final solution, by matching with adjacent blocks that aren't part of the same sub-tree. This empirically seems to work quite well.

The should be better than cell-by-cell techniques like JLS, as it is able to figure out and eliminate many local contradictions much earlier. My haphazard tests find that its performance is comparable to SAT solver-based methods on many problems. For example, attaching this to a basic harness that repeatedly tries searches with different predecessors and increasing bounding boxes to find deep predecessors, as an example search, it finds this 15 gen predecessor of the Herschel in ~13 seconds on my system

Code: Select all

x = 22, y = 19, rule = B3/S23
3.2A.A2.A.A3.2A3.A$4.2A3.A.A3.2A2.A$.3A.A.A4.A.2A4.A$3.2A.A.2A2.A.A3.
A2.A$A.A6.A2.3A2.2A$4.A2.2A.2A.A2.A.3A$A.5A.2A2.2A.A.A$3A2.2A.A4.A.A.
A2.2A$.4A8.2A.A$A3.A.A.A2.2A2.A3.2A$2.A3.A.A2.A3.2A$2.2A3.A4.A2.A.A.A
$2A.3A.A2.2A2.A3.4A$2A3.2A4.2A2.3A3.A$.A2.A2.2A.3A5.A$.2A2.A.A3.A2.A
2.A$2.2A.2A2.2A2.A.A3.A$3.A2.A6.A3.A.A$A2.A2.2A8.A4.A!
And on my system, running it on a random 30x30 pattern with a 3 cell width empty buffer proves there are no solutions in ~4s.

I've pushed a basic version of the code here: https://github.com/Aaron-d-k/exhaustive ... r-searcher
It's pretty configurable, with options for custom heuristics (by default it prefers low population predecessors). I've also added a option to enumerate all predecessors (if possible) and to add more flexible constraints (for example, few cells are fixed in the previous gen, some cells in next gen are left unknown, etc, and you can input all this via RLE. I though this might be useful for stuff like trying to find predecessors for glider synthesis or some task where you are looking for predecessors where some part of the object remains unchanged)

Using this, I tried few experiments with deep learning (specifically, I used reinforcement learning, with a variant of soft value iteration). I can post the exact details and code if there is more interest, but in general my results were not very breathtaking. My most realistic experiment was when I tried training a model to find the predecessor of a random 4x4 board embedded in a 16x16 grid, and it averaged out at being able to rewinding by ~13.5 gens, which is better than random. My most successful experiment was related to rewinding a 8x8 board with 2 adjacent unconstrained sides, where a model figured out how to stabilize the predecessors into a still life, achieving infinite rewinding. But this isn't very helpful for predecessor searching, because the way it works is it kinda 'moves out' the problematic area via the unconstrained boundaries, making it useless for a full board.
Here are some examples:
Model trained on all sides dead, 16x16, rewinding a 4x4 pattern

Code: Select all

  depth 13:
gen 0             gen -1            gen -2            gen -3            gen -4            gen -5            gen -6            gen -7            
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ........**......  ........**......  ........*.......  ........*.......  ................  ........**......  
................  .........*......  ................  ........**......  ........**......  .......*.*......  .......***......  .....*..........  
........*.......  ......**........  .......*.*......  .......**.......  ................  ..........*.....  .....***.*......  ......*.*.......  
......***.......  .........*......  ......**.*......  .......*........  ......**........  .....*..........  .......**.*.....  ......*..**.....  
.......*.*......  ......*..*......  ......***.......  .....*..**......  ........*.......  ......***.......  .....*..*.......  .........**.....  
.......**.......  .......**.......  .........*......  .......*........  .....**.*.*.....  .....**.***.....  .....*...*......  ....**...**.*...  
................  ................  ................  .........*......  ..........*.....  ..........*.....  ......*..*.*....  ......*....*....  
................  ................  ................  ................  ................  ................  ................  ......*...*.....  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  
................  ................  ................  ................  ................  ................  ................  ................  

gen -8            gen -9            gen -10           gen -11           gen -12           gen -13           
................  ................  ................  ................  .........**.....  .....**.*.*.*...  
................  ................  ................  .........**.....  ..*..*......*...  ..**......**....  
................  ................  .........*......  .....*......**..  ....*....*......  ..***....***..*.  
................  ........*.......  ....**.*....*...  ......*.*.......  ......*.*...**..  ...*..*...***...  
.....*...*.*....  .....**...*.....  ........*..*....  ...**...*..*....  ..******........  ..***.***...*...  
.......*.**.....  .....***..*.*...  ...*.*....***...  .......*...***..  .....**..*.***..  ............**..  
.....**..**.*...  ......*...*.*...  ....***.*.*.....  ....**....*.....  ..**.*......*...  ..**.*..**..*...  
..........*.....  ........*..*....  ...**.*.*..*....  ....*..*.*.*....  .......*..*.*...  .*.**.*......*..  
.......*....*...  ...*.......**...  ...****..*.*....  ....*..*...*....  .....*.***......  ...**...**.*....  
....**...**.*...  .......****.*...  .....**.***.*...  ...*.*...**.....  ...*.*...**.....  .*.*...*.**.....  
.....**...**....  ....*****..*....  .....*......*...  .....*..*..**...  ..*.**.....*....  .*..**..........  
....*.*..*......  ................  ...*....*.......  ....*.....***...  ....*...**.**...  .....******.*.*.  
................  ....*...**......  ...*.*...*..*...  ...***..****....  ....*...........  .*....*.*...**..  
................  ................  .......*..*.....  ....*...........  ...*.*.*..*.....  ...*.*.*.****...  
................  ................  ................  ....*..**.......  ............*...  .*.***..**..*...  
................  ................  ................  ................  ...*..**.*......  .*.**.**.*......
Output from a model trained on 2 sides dead, 8x8 (this model seems to have learnt something more mysterious than the still life one, I could not figure out what it's trying here)

Code: Select all

gen 0     gen -1    gen -2    gen -3    gen -4    gen -5    gen -6    gen -7    
*....**.  .....**.  .....**.  .*......  .**...*.  *.....*.  *.....*.  .*....*.  
.*......  *.*..*..  .**..*.*  .*..****  .****..*  .***.*.*  *..*.*.*  ...*.*.*  
...*..*.  *...**..  ***.....  **....**  ...*..*.  ...*...*  ..**.**.  ..**.**.  
**..***.  *...**..  ..*.**.*  ...*.**.  .*.*.**.  **.*....  .**..**.  ........  
...*..*.  .*.....*  .**..**.  *.*..*..  ...*.*..  **.****.  .*...*..  **....*.  
*.******  ...**.*.  ..**..*.  ..**....  .....*..  *..*....  ..**....  ..*.*.*.  
..*.....  *..*..*.  **...*..  *...***.  ..**....  ****....  .**.....  .**..***  
*..*..*.  ...**...  *.*....*  ..***...  *....**.  *......*  *......*  *..*.***  

gen -8    gen -9    gen -10   gen -11   gen -12   gen -13   gen -14   gen -15   
.**...*.  .*.*.**.  *.*.**..  *..**...  *...*.*.  *...**..  ....**..  *.*.*...  
*....*.*  *.*....*  ..*...**  ..***.**  *..**.*.  *...***.  .*...*..  ...***..  
****..*.  ..**.*.*  ..**.*.*  ...*.*.*  **.*...*  .**...*.  ..*...*.  ..**..*.  
*..**...  ........  ...*.**.  ........  **...*.*  ....**.*  ..****.*  ...***..  
*...**..  ....*...  ***.**..  ..*.**..  *..*.*..  *......*  *.**..**  *.....**  
..*.*.**  ..***.*.  ***...*.  *.**..*.  .*....*.  ..**.*..  ***..**.  .*.*..*.  
.**.*...  ..*..***  *....**.  ...*.*..  ...**.*.  *......*  *.....*.  *..*..*.  
.......*  ..*...**  **....*.  *.***.*.  ***.....  **.*..*.  .....**.  *.****..  

gen -16   gen -17   gen -18   gen -19   gen -20   gen -21   gen -22   gen -23   
.**.*...  .**.....  **......  *.**....  ...*....  ..*.....  ..*.....  ........  
...****.  ..****..  ..**....  *....*..  **.***..  ...**.*.  .*.*...*  .***...*  
**......  **...**.  *...***.  ..*...*.  ...***..  **.*..*.  ...*.*.*  .**..***  
...*..*.  .*.*.**.  ..**.*..  ...*.*..  ....**..  ***.....  *.*.*...  *.....*.  
**.**.*.  .**.*...  *.......  *..**...  *.......  ..***.*.  .*..***.  *..*.**.  
...****.  .*...*..  .*...*..  .*.**.*.  ..*.*.*.  *.*.....  **...**.  *..*....  
.*......  .**..**.  *....***  *..*....  *..*.**.  ..*..**.  *.*..*..  ..***..*  
....*.*.  ..*****.  .*.**...  .***..**  **.*..**  *...*.*.  **......  ...***..  

gen -24   gen -25   gen -26   gen -27   gen -28   gen -29   gen -30   gen -31   
*.....*.  *....**.  .....**.  .....**.  .....**.  .....*..  ....*...  ...**...  
*..*...*  .......*  *.*...*.  ...*..*.  .*.*..*.  *.*..**.  .*...**.  **...*..  
..*****.  ..*****.  *.*..**.  .*.*.*..  .*.**...  ..*.**..  .*.*.*..  **.***.*  
*..*..*.  *..*....  *..*.*..  .....*..  *..*.*..  .....*..  ......*.  ...**..*  
***.....  **....*.  .*.***..  .*.**...  **.**...  *..*....  ..***...  ...**...  
.**..**.  .*...*..  .**.**..  .**.*...  .*......  .***....  *.......  .*.....*  
...*....  *..***..  ...*....  *.....*.  .....*..  ...**...  .*.....*  .......*  
....*.**  .**.*.**  **....*.  *...*.*.  .*....**  ...**.*.  ******..  *.*..**.  

gen -32   gen -33   gen -34   gen -35   gen -36   gen -37   gen -38   gen -39   
...**...  *..**...  *..**...  *..**...  *..*....  **......  .*......  .*......  
.***.*..  ...*..*.  ...*.*..  ...*.*..  ...**...  *****...  **..*...  **...*..  
.*..*..*  **..*..*  *...***.  *....*..  *...**..  **..*...  ..*.***.  ..**.*..  
......**  **.**.**  **....**  *.....*.  ...**...  ......*.  ....*...  .*....*.  
..*.***.  *.*.**..  ..*.*...  *...*.**  ...**.**  ...**.*.  ...**.*.  ****....  
...*.**.  *.*.....  *.***...  *****.**  .**...*.  ..*..**.  .....**.  *.*.***.  
*.**..*.  *.....**  *..**.**  *.....*.  *....*..  *.**.*..  ..**....  *..*.*..  
*.**.**.  *.**.*..  .*.*.**.  .*...*..  .*.*...*  **.**..*  ...*.*.*  *..*.**.  

gen -40   gen -41   gen -42   gen -43   gen -44   gen -45   gen -46   gen -47   
*.*.*...  *..*....  ..*.*...  ..*.*...  .*.**...  .*.**...  .*.*....  .*......  
.*......  .*.*.*..  .*..*...  .*.**...  .*...*..  **.**...  **.**...  .****...  
.*.***..  .****...  *.....*.  *.*..**.  ..*.....  ..***...  ....*...  .*..*..*  
....**..  .*....*.  .*.**.*.  .*.**.*.  *.*..**.  *....**.  **...**.  ****....  
.**..*..  .**..*..  ..****..  ...*....  ....***.  *.*..*..  ...*.*..  ...***.*  
*.*..**.  .....**.  *.......  *.....*.  **..**..  *...*...  ...*...*  .*...*.*  
*....*..  ...*.*..  .***.*.*  ..*.....  ...**...  ...**...  *.......  ....***.  
*..**..*  **..*..*  .**.***.  ..**.***  ...*****  ....*.**  ...**.*.  *...**..  

gen -48   gen -49   gen -50   
*.**....  ..**....  *.**....  
*....*..  *..***..  ...***..  
...*..*.  ...*..*.  **....*.  
*.*..***  .*.*..*.  ....**..  
.*.*.***  *.....*.  *..***..  
.**.....  ..**..*.  ...**..*  
..***..*  .*......  .*....*.  
***..**.  ....****  *.******
Output from a RL run that discovered the still life heuristic:

Code: Select all

gen 0     gen -1    gen -2    gen -3    gen -4    gen -5    gen -6    gen -7    
.**.*.**  ..*.*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..*.*.*.  *.***.*.  .****.*.  *.***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
....*.*.  .*..*.*.  ......*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
****...*  **...*..  *..*..**  **.**.**  **.**.**  **.**.**  **.**.**  **.**.**  
..*.....  ..*.****  *.*...**  *.*...*.  ..*.*...  ..*.*...  ..*.*...  ..*.*...  
..**.*..  ..**.*..  *.***...  *..**...  *..*.*..  .*..*...  **..*...  **..*...  
***.*...  ........  ......**  .*..*.*.  .**.....  ......*.  ....**..  ....**..  
*...****  *.*.*..*  ***.....  ********  ..**..**  .**....*  ****.**.  ****..*.  

gen -8    gen -9    gen -10   gen -11   gen -12   gen -13   gen -14   gen -15   
....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  
*...*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  
***.*...  .**.*...  *...*...  .*..*...  .*..*...  ....*...  *...*...  *...*...  
....*.*.  ....**..  ...*....  .***....  ..**....  ..**....  ****....  ..**....  
.*.*....  ***..**.  .....**.  *.*...*.  ..*.....  ..*.....  *.*...*.  ..*.....  

gen -16   gen -17   gen -18   gen -19   gen -20   gen -21   gen -22   gen -23   
....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  
.**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  
*...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  
****....  ..**....  ****....  ..**....  ****....  ..**....  ****....  ..**....  
*.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  

gen -24   gen -25   gen -26   gen -27   gen -28   gen -29   gen -30   gen -31   
....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  
.**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  
*...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  
****....  ..**....  ****....  ..**....  ****....  ..**....  ****....  ..**....  
*.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  

gen -32   gen -33   gen -34   gen -35   gen -36   gen -37   gen -38   gen -39   
....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  
.**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  
*...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  
****....  ..**....  ****....  ..**....  ****....  ..**....  ****....  ..**....  
*.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  

gen -40   gen -41   gen -42   gen -43   gen -44   gen -45   gen -46   gen -47   
....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  *..**.**  
.**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  .**.*...  
*...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  *...*...  
****....  ..**....  ****....  ..**....  ****....  ..**....  ****....  ..**....  
*.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  *.*...*.  ..*.....  

gen -48   gen -49   gen -50   
....*.**  ....*.**  ....*.**  
..***.*.  ..***.*.  ..***.*.  
.*....*.  .*....*.  .*....*.  
*..**.**  *..**.**  *..**.**  
.**.*...  .**.*...  .**.*...  
*...*...  *...*...  *...*...  
****....  ..**....  ****....  
*.*...*.  ..*.....  *.*...*.
I'm hoping somebody else can suggest other ideas for RL environments that might lead to interesting results, or even try manual heuristics that can be used with the search program to achieve better results than the current heuristic of preferring low population.

Re: Algorithm for reversing the GoL rules

Posted: August 1st, 2026, 5:10 am
by NNlk05
Very nice! The SL based rewinding is very useful for spaceship synthesises. I believe something like this is needed for a very long time.
All times are UTC-04:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited