ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Oscillator-searching method with SAT

For general discussion about Conway's Game of Life.

Oscillator-searching method with SAT

Postby testitemqlstudop » March 13th, 2019, 11:17 am

This might sound ridiculous, but I think that there is a feasible method for row-by-row (wide and high period) oscillator searching with SAT solvers.

Specifically, given the first two rows (in all phases), we want to find the all possible collection of phases for the next row such that the evolution sequence for the previous row is correct.

For example, if we are searching for a p4 (mold):
......   ....o.   ...oo.   ..o.o.
...ooo   ..oo.o   ..ooo.   .....o
.o.ooo   .o....   .o.oo.   .o..o.
abcdef   ghijkl   mnopqr   stuvwx

we want to find sets {a-x} such that
...ooo
.o.ooo
abcdef

evolves into
??????
..oo.o
??????

and
.....o
.o..o.
stuvwx

evolves into
??????
.o.ooo
??????

and so on.
This is where the SAT solvers come into play. For wide/high-period oscillators there may be too many variables to try with standard methods. we can construct a SAT problem where the variables are the phases of the next row and the clauses ensure the correct evolution sequence.

Is this a feasible method or is it impossible?
User avatar
testitemqlstudop
 
Posts: 736
Joined: July 21st, 2016, 11:45 am
Location: very very very very boats

Re: Oscillator-searching method with SAT

Postby Bullet51 » March 15th, 2019, 6:50 am

I have done some experiments on it, and it certainly works in P3 and P4.
Still drifting.
Bullet51
 
Posts: 521
Joined: July 21st, 2014, 4:35 am

Re: Oscillator-searching method with SAT

Postby testitemqlstudop » March 15th, 2019, 11:24 am

I think that this will especially be helpful with higher periods, and it can also help to find oscillators with special properties , particularly noticeable sparks from the top (i.e. t-nosed, pipsquirter, etc.)

Any ideas on efficient implementation?
User avatar
testitemqlstudop
 
Posts: 736
Joined: July 21st, 2016, 11:45 am
Location: very very very very boats


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 2 guests