5 ms·

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]. [0] htt

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]. [0] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview https://www.kaggle.com/c/conways-reverse-game-of-life-2020/o... [1] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/discussion/200980 https://www.kaggle.com/c/conways-reverse-game-of-life-2020/d...

bondarchuk 6y ago
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.
- andersource 6y ago
  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.
- UncleOxidant 6y ago
  > 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.
UncleOxidant 6y ago
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.
- adenozine 6y ago
  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.
  - UncleOxidant 6y ago
    > You might be aware of genetic programming? 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.
    - adenozine 6y ago
      Ah, I see. I guess I meant general in the parameterization sense, not necessarily in the abstraction sense. Sorry, that could've been more clear. I've not dug into CGP yet, though I've read mentions of it. Would you perhaps have a good resource for learning? I'm a little weak on the math side.
      - UncleOxidant 6y ago
        > I'm a little weak on the math side. 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. This is the paper that introduced CGP by Julian Miller: https://thelackthereof.org/docs/library/cs/gp/Miller,%20Julian:%20Cartesian%20Genetic%20Programming.pdf https://thelackthereof.org/docs/library/cs/gp/Miller,%20Juli... I found this good survey of CGP here (from 2018): https://link.springer.com/content/pdf/10.1007/s10710-019-09360-6.pdf https://link.springer.com/content/pdf/10.1007/s10710-019-093...

bondarchuk 6y ago

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.

andersource 6y ago
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.
UncleOxidant 6y ago
> 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.

UncleOxidant 6y ago

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.

adenozine 6y ago
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.
- UncleOxidant 6y ago
  > You might be aware of genetic programming? 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.
  - adenozine 6y ago
    Ah, I see. I guess I meant general in the parameterization sense, not necessarily in the abstraction sense. Sorry, that could've been more clear. I've not dug into CGP yet, though I've read mentions of it. Would you perhaps have a good resource for learning? I'm a little weak on the math side.
    - UncleOxidant 6y ago
      > I'm a little weak on the math side. 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. This is the paper that introduced CGP by Julian Miller: https://thelackthereof.org/docs/library/cs/gp/Miller,%20Julian:%20Cartesian%20Genetic%20Programming.pdf https://thelackthereof.org/docs/library/cs/gp/Miller,%20Juli... I found this good survey of CGP here (from 2018): https://link.springer.com/content/pdf/10.1007/s10710-019-09360-6.pdf https://link.springer.com/content/pdf/10.1007/s10710-019-093...