Conway's Gradient of Life

submited by

Style Pass

2024-10-09 10:00:03

What happens if we start from this configuration and take a single step of the game? Here is a snapshot of the next generation:

Well, let’s start with how it doesn’t work. Reversing Life configurations exactly — the art of “atavising” — is a hard search problem, and doing it at this scale would be computationally infeasible. Imagine searching through $ 2^{239\times200} $ possible configurations! Surely that is hopeless… indeed, the talk I linked shares some clever algorithms that nonetheless take a full 10 minutes to find a predecessor for a tiny 10-by-10 board.

But it turns out that approximately reversing a Life configuration is much easier — instead of a tricky discrete search problem, we have an easy continuous optimization problem for which we can use our favorite algorithm, gradient descent.

Here is the idea: Start with a random board configuration $ b $ and compute $ b^\prime $, the result after one step of Life. Now, for some target image $ t $ compute the derivative $ \frac{\partial}{\partial b} \sum|b^\prime-t| $, which tells us how to change $ b $ to make $ b^\prime $ closer to $ t $. Then take a step of gradient descent, and rinse and repeat!