Kaggle recently hosted a very relevant competition - "Conway's Reverse Game of Life" [0]. A write-up of the 1st place might be an interesting read [1].
Very nice! Some states have multiple ancestors, some have none, so these are "dead ends" when going backwards. But when you are just looking for an approximation of the final state, as in TFA, you can probably accept quite some perturbation, which could make it significantly easier to go backwards in a naive way and sometimes miss a few cells in the process.
> Some states have multiple ancestors, some have none
Yeah, this is what I didn't understand about that particular Kaggle competition. It doesn't seem possible that you could learn some general set of rules that would allow you to predict previous states with much accuracy.
Yeah, I think it's very interesting because there's a lot of freedom in measuring the similarity and also other aspects of the process, for example optimizing for a "simple" starting configuration as mentioned in other comments.
I read the writeup where someone applied a genetic algorithm to this problem and I guess what I found disappointing was that it wasn't a general solution that could learn any general cases or rules, it was just very specific for each example provided. It's not like you could train it on a set of examples and then give it a new example and it would be able to do it any quicker or more accurately.
Well, that's sort of the case for genetic algorithms.
You might be aware of genetic programming? There may be papers already out there, but the idea is representing a programs source as a genome, and then performing the familiar processes (mutation, crossover, selection) on those.
Anyhow, that would produce something more general. A genetic algorithm is traditionally a single shot thing.
Actually been playing with Cartesian Genetic Programming (CGP) recently.
> Anyhow, that would produce something more general.
Not really, at least as far as I can tell with CGP. I was evolving a circuit to solve the 8-bit parity problem (kind of the 'Hello world' of CGP - it solves this problem surprisingly quickly). There wasn't any way to use that information to evolve a circuit to solve the 16-bit parity problem - you've gotta start again from scratch. There may be some proposed solutions to this kind of issue in CGP - I'm still reading papers.
In general, I think that tends to one of the advantages of genetic algorithm/programming over neural nets/deep learning - the math is comparatively quite easy.
[0] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/o...
[1] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/d...