Feels to me like there is no need for backpropagation. I think you can just iteratively grab a random pixel and flip it of that would bring you closer to the target after one step.
It would probably work even better if you tweak the loss function with some kind of averaging/blurring filter.
This is just the brute force solution. I'm pretty sure that's no more efficient than guessing all pixels at once and trying to check of that worked or not.
It's the trivial solution. It's significantly more efficient than using backprop. It's much simpler and leads to practically the same result.
This makes me wonder why you would use backprop to do this. It feels like a waste of time, and I'm not sure why this post generates so much attention on HN.
Guessing all pixels at once and then checking is massively worse, since it's basically the first step of GP's proposed approach -- which then iteratively changes things in a way that never makes it worse.
It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future. Everything will have a 50/50 probability of being "correct" based on any given scenario. What you're saying is somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip, or even 20 of the last flips in a row. I'm actually not a great statistician myself, but I think I'm right on this one. :)
>It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future.
It's true that a "good" decision now might turn out to be "bad" later, but whether it's effective in improving a solution depends on the fraction of times that happens, which is almost certainly not 50%. Hill-climbing methods like this are used everywhere in optimisation when you want a decent solution quickly and don't require optimality.
>somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip
I'm no statistician either, but this is not analogous at all.
What you described wasn't Hill Climbing at all tho. You have to be able to take the derivative of a function to do that. The derivative is what tells you how to "go uphill" (or down)
Well you're right there's infinite variations of algos that all can legitimately be called hill-climb. It's about as generic as the term "curve fitting".
I just mean with the known complexity and nature of Game of Life, trying to guess things based on an objective function, when going back in time, seems no more efficient than trying to guess coin flips, based on prior flips. There's probably some Logic Theorem (sorry I don't know it) that describes why objective functions cannot be used to help solve the backwards Game of Life problem.
It's a complexity problem like which butterfly "caused" a tornado, or which initial clumping of rocks "caused" a black hole, because there are infinite numbers of solutions. Like how many initial GoL boards are there that result in a particular final state? I say for any final state there will be infinite possible starting states that can lead up to it.
It would probably work even better if you tweak the loss function with some kind of averaging/blurring filter.