A CNN-Based Approach to the Reverse Game of Life Problem
摘要
The Game of Life (GoL) is a cellular automaton characterised by non-linear evolution and emergent complexity. Its global state transition function is non-injective and irreversible, leading to information loss. Consequently, the Reverse GoL, i.e., finding a predecessor that evolves into a given target after a given number of generations, is an NP-complete task. In this paper, we introduce a differentiable GoL transition function within a convolutional neural network-based model to reconstruct the probability distribution, i.e. a heatmap, of a possible initial state associated with the given final board. In this study, the models are validated on \(15\times 15\) boards after one generation by analysing structure-based metrics on the heatmaps of the predicted initial states. In particular, we computed the fuzziness index to measure the degree of binarisation, the Earth Mover’s Distance, to evaluate the accuracy of the spatial mass distribution, and the percentage of high uncertainty cells within a range, to quantify prediction confidence. Our results demonstrate that integrating the differentiable layer reduces the fuzziness index by approximately 40% compared to the baseline approach. Furthermore, the analysis indicate that pixel-wise metrics, such as Mean Squared Error, can be misleading in this context, as they ignore the spatial context of cells. In contrast, the use of structural metrics reveals that the proposed architecture effectively captures the underlying physics and spatial organisation of the automaton.