It surprises me a little that there hasn’t been more work on working backwards in Life. Perhaps it’s just too hard/not useful given the number of possible X-1 time slices.
With the smiley face example, there could be a very large number of combinations for the squares outside the smiley face at X-1 which result in the same empty grid space (i.e. many possible self-destructing patterns).
I’m unreasonably fond of brute forcing problems like these. I don’t know if I’d have anything useful to say on this topic that I haven’t already, but I’m interested to follow this work. I think this is a fascinating analogy for the control problem.
Edit—It just occurred to me, thanks to a friend, that instead of reverse engineering the desired state, it might be easier to just randomise the inputs until you get the outcome you want (not sure why this didn’t occur to me). Still very intensive, but perhaps easier.
Well, there are programs like Logic Life Search that can solve reasonably small instances of backwards search. This problem is quite hard in general. Part of the reason is that you have to consider sparks in the search. The pattern in question could have evolved from small predecessor pattern, but the reaction could have moved from the starting point and a several dying sparks could have been emitted all around. So you have to somehow figure the exact location, timing and nature of these sparks to successfully evolve the pattern backwards. Otherwise, it quite quickly devolves into bigger and bigger blob of seemingly random dust.
In practice, backwards search is regularly applied to find smaller predecessors in terms of bounding box and/or population. See, for example, Max page. And the number of ticks backwards is quite small, we are talking about a single-digit number here.
It surprises me a little that there hasn’t been more work on working backwards in Life. Perhaps it’s just too hard/not useful given the number of possible X-1 time slices.
With the smiley face example, there could be a very large number of combinations for the squares outside the smiley face at X-1 which result in the same empty grid space (i.e. many possible self-destructing patterns).
I’m unreasonably fond of brute forcing problems like these. I don’t know if I’d have anything useful to say on this topic that I haven’t already, but I’m interested to follow this work. I think this is a fascinating analogy for the control problem.
Edit—It just occurred to me, thanks to a friend, that instead of reverse engineering the desired state, it might be easier to just randomise the inputs until you get the outcome you want (not sure why this didn’t occur to me). Still very intensive, but perhaps easier.
Well, there are programs like Logic Life Search that can solve reasonably small instances of backwards search. This problem is quite hard in general. Part of the reason is that you have to consider sparks in the search. The pattern in question could have evolved from small predecessor pattern, but the reaction could have moved from the starting point and a several dying sparks could have been emitted all around. So you have to somehow figure the exact location, timing and nature of these sparks to successfully evolve the pattern backwards. Otherwise, it quite quickly devolves into bigger and bigger blob of seemingly random dust. In practice, backwards search is regularly applied to find smaller predecessors in terms of bounding box and/or population. See, for example, Max page. And the number of ticks backwards is quite small, we are talking about a single-digit number here.